博客

一、栈的基本概念
1.栈的定义
只允许在一端进行插入或删除操作的线性表。也称为后进先出的线性表。
栈顶：线性表允许进行插入和删除的那一端。
栈底：固定的，不允许进行插入和删除的另一端。
空栈：不含任何元素的空表。

二、栈的顺序存储结构
1.顺序栈的实现
利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针（top）指示当前栈顶的位置。
栈的顺序存储类型可描述为

#define MaxSize 50
typedef struct
{
    Elemtype data[MaxSize];
    int top;
}SqStack;

栈顶指针：S.top，初始时设置S.top=-1；栈顶元素：S.data[S.top]
进栈操作：栈不满时，栈顶指针先加1，再送值到栈顶元素。
出栈操作：栈非空时，先取栈顶元素值，再将栈顶指针减1。
栈空条件：S.top=-1；栈满条件：S.top=MaxSize-1；栈长：S.top+1

需要注意的是，当为空栈时top指针的状态。
2.顺序栈的基本运算
（1）初始化

void InitStack(&S)
{
    s.top=-1;
}

（2）判栈空

bool StackEmpty(S)
{
    if(s.top==-1)
        return true;
    else
        return false;
}

（3）进栈

bool push(SqStack &S,ElemType x)
{
    if(S.top==MaxSize-1)
        return false;
    S.data[++S.top]=x;
    return true;
}

（4）出栈

bool Pop(SqStack &S,ElemType &x)
{
    if(S.top==-1)
        return false;
    x=S.data[S.top--];
    return true;
}

（5）读栈顶元素

bool GetTop(SqStack S,ElemType &x)
{
    if(S.top==-1)
        return false;
    x=S.data[S.top];
    return true;
}

3.共享栈
利用栈底位置相对不变的特性，可以让两个顺序栈共享一个一维数据空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸：

两个栈的栈顶指针都指向栈顶元素，top0=-1时0号栈为空，top1=MaxSize时1号栈为空；仅当两个栈顶指针相邻（top1-top0=1）时，判断为栈满。
当0号栈进栈时top0先加1再赋值，1号栈进栈时投票先减1再赋值。

三、栈的链式存储结构
链栈的优点是便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。规定链栈没有头结点，Lhead指向栈顶元素。
栈的链式存储类型可以描述为：

typedef struct
{
    ElemType data;
    struct LinkNode *next;
}LinkNode;
typedef struct
{
    LinkNode *top;
    int count;
}*LiStack;

1.栈的基本操作
（1）初始化

void InitStack(LiStack &S)
{
    S->top==NULL;
    S->count=0;
}

（2）判栈空

bool EmStack(LiStack S)
{
    if(S->top==NULL)
        return true;
    else
        return false;
}

（3）插入元素

bool Push(LiStack &S,ElemType x)
{
    p=(LinkNode *)malloc(sizeof(LinkNode));
    if(p==NULL)
        return false;
    p->data=x;
    p->next=NULL;
    p->next=s->top;
    s->top=p;
    s->count++;
    return true;
}

（4）删除元素

bool Pop(LiStack &S,ElemType &x)
{
    LinkNode *p;
    if(s->top=NULL)
        return false;
    p=S->top;
    *x=p->data;
    S->top=p->next;
    free(p);
    return true;
}