数据结构-栈

栈（Stack）是一种只能在一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶（Top），另一端称为栈底（Bottom）。当栈中没有数据元素时，称为空栈。栈的插入操作通常称为进栈或入栈（Push），栈的删除操作通常称为退栈或出栈（Pop）。栈的进栈和出栈操作的时间复杂度均为O(1)。

栈顶的当前位置是动态的，由一个称为栈顶指针的位置指示器来指示。栈的主要特点是「后进先出」，即后进栈的元素先出栈。所以栈也被称为后进先出表。

顺序栈

顺序栈是栈的顺序存储结构，把元素按照其进栈顺序依次存储到从计算机存储器中指定存储位置开始的一块连续的存储空间中。

顺序栈的四个要素：

• 栈空条件：s->top == -1
• 栈满条件：s->top == MaxSize - 1
• 进栈操作：s->top++;并将要进栈的元素e放在s->top处
• 出栈操作：从s->top处取出要出栈的元素e ，并且s->top--;

栈空时仍进行出栈操作，称为下溢。栈满时仍进行进栈操作，称为上溢。

类型定义

#define ElemType int               // 元素类型#define MaxSize 10                 // 最大长度typedef struct{    ElemType data[MaxSize];    int top;                       // 栈顶指针} SqStack;

基本运算

初始化顺序栈

建立一个新的空栈s，将栈顶指针指向 − 1。

// 初始化顺序栈void initStack(SqStack *&s){    s = (SqStack *) malloc(sizeof(SqStack));    s->top = -1;    // 将栈顶指针置为-1}