栈

栈的基本概念

定义

  只允许在一端进行插入或删除操作的线性表。首先，栈是一种线性表，但限定这种线性表只能在某一段进行插入和删除操作。

  栈顶（Top）：线性表允许进行插入和删除的一端。

  栈底（Bottom）：固定的，不允许进行插入和删除的另一端。

  空栈：不含任何元素。

  如上图：a1为栈底元素，an为栈顶元素。由于栈只能在栈顶进行插入和删除操作，故进栈次序依次为a1，a2，... ,an 而出栈次序为an，...，a2，a1。栈的明显的操作特征为后进先出（Last In First Out，LIFO）,故又称 后进先出的线性表。

栈的基本操作

  1）InitStack（&S）：初始化空栈S

  2）StackEmpty（S）：判断一个栈是否为空

  3）Push（&S，x）：进栈，若栈未满，则将x加入使之成为新栈顶

  4）Pop（&S，&x）：出栈，若栈非空，则将栈顶元素，并用x返回

  5）GetTop(S，&x)：读栈顶元素，若栈顶元素非空，则用x返回栈顶元素

  6）DestroyStack(&S)：销毁栈，并释放栈S占用的存储空间

栈的顺序存储结构

顺序栈的实现

  采用顺序存储的栈称为顺序栈，它是利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针（top）指示当前栈顶的位置。

  栈的顺序存储类型可以用以下表示：

#define MAXSIZE 100            //栈中元素的最大个数
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

顺序栈的基本运算

初始化

void InitStack(SqStack& S){
    S.top = -1;                //初始化栈顶指针
}

判栈空

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

进栈

bool Push(SqStack& S, ElemType x){
    if( S.top == MAXSIZE - 1 ){    //栈满，报错
        return false;        
    }
    S.top ++ ;                    //栈顶指针加1
    S.data[S.top] = x;            //入栈
    return true;
}

出栈

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

读栈顶元素

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

  注意：若栈顶指针初始化为S.top = 0，即栈顶指针指向栈顶元素的下一个位置，则入栈操作变为S.data[S.top++]，出栈操作为x = S.data[--S.top]。因为栈顶指针若初始化为 0 时，则栈顶指针始终指向顺序栈将要入栈的位置，也就是栈顶指针的下标就是入栈元素的下标。

共享栈

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

  两个栈的栈顶指针都指向栈顶元素，top1 = -1 时，stack1 为空，top2 = MAXSIZE - 1 时，stack2 为空；仅当两个栈顶指针相邻（top1 - top2 == 1)时，判断栈满。当stack1进栈时top1先加1再赋值，stack2进栈时top2先减1再赋值；出栈正好相反。

  共享栈是为了更有效地利用存储空间，两个栈的空间正好互相调节，只有在整个存储空间被占满时才发生上溢。存取数据的时间复杂度均为O(1)，所以对存取效率没有什么影响。

栈的链式存储结构

  采用链式存储的栈称为链栈，链栈的优点是便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。通常采用单链表实现，并规定所有操作都是在单链表的表头进行的。这里规定链栈没有头结点，top指向栈顶元素，

  链栈的存储类型可描述为：

typedef struct LinkNode{
    ElemType data;
    struct LinkNode* next;
}LinkNode, *LinkStack;