数据结构：栈

• 顺序栈
  • 类型定义
  • 基本运算
    • 初始化顺序栈
    • 销毁顺序栈
    • 判断是否为空栈
    • 进栈
    • 出栈
    • 获取栈顶元素值
• 链栈
  • 类型定义
  • 基本运算
    • 初始化链栈
    • 销毁链栈
    • 判断是否为空栈
    • 进栈
    • 出栈
    • 获取栈顶元素

栈（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
}

销毁顺序栈

// 销毁顺序栈
void destroyStack(SqStack *&s)
{
    free(s);
}

判断是否为空栈

// 判断是否为空栈
bool isEmpty(SqStack *s)
{
    return s->top == -1;    // 栈顶指针指向-1表示栈为空
}

进栈

在栈不满的条件下，先将栈指针增$1$，然后在该位置上插入元素$e$。

// 进栈
bool push(SqStack *&s, ElemType e)
{
    if (s->top == MaxSize - 1) return false;    // 栈满的情况, 即栈上溢出
    s->top++;                                   // 栈顶指针增1
    s->data[s->top] = e;                        // 元素e放在栈顶指针处
    return true;
}

出栈

在栈不为空的条件下，先将栈顶元素赋给$e$，然后将栈指针减$1$。

// 出栈
bool pop(SqStack *&s, ElemType &e)
{
    if (s->top == -1) return false;     // 栈为空的情况, 即栈下溢出
    e = s->data[s->top];                // 取栈顶指针元素的元素
    s->top--;                           // 栈顶指针减1
    return true;
}

获取栈顶元素值

在栈不为空的条件下，将栈顶元素赋给$e$。

// 获取栈顶元素
bool getTop(SqStack *s, ElemType &e)
{
    if (s->top == -1) return false;     // 栈为空的情况, 即栈下溢出
    e = s->data[s->top];                // 取栈顶指针处的元素
    return true;
}

链栈

栈的链式存储结构称为链栈，采用单链表实现。链栈的优点是不存在栈满上溢的情况。这里规定栈的所有操作都是在单链表的表头进行的。用带头结点的单链表表示链栈，第一个数据结点是栈顶结点，最后一个结点是栈底结点。

栈中元素自栈顶到栈底依次是$a1,a2,…a_n$。

链栈的四个要素：

• 栈空条件：s->next == NULL
• 栈满条件：不考虑
• 进栈操作：将包含e的结点插入到头结点之后
• 出栈操作：取出头结点之后结点的元素并删除

类型定义

#define ElemType int        // 元素类型
typedef struct LStNode
{
    ElemType data;          // 数据域
    struct LStNode *next;   // 指针域
} LinkStNode;

基本运算

初始化链栈

建立一个空栈$s$。实际上是创建链栈的头结点，并将其next域置为NULL。

// 初始化链栈
void initStack(LinkStNode *&s)
{
    s = (LinkStNode *) malloc(sizeof(LinkStNode));
    s->next = NULL;
}

销毁链栈

// 销毁链栈
void destroyStack(LinkStNode *&s)
{
    LinkStNode *pre = s, *p = s->next;
    while (p != NULL)   // 遍历子节点并释放其空间
    {
        free(pre);
        pre = p;
        p = pre->next;
    }
    free(pre);          // 此时p指向尾结点, 释放其空间
}

判断是否为空栈

// 判断是否为空栈
bool isEmpty(LinkStNode *s)
{
    return s->next == NULL;    // 头结点之后无子结点表示栈为空
}

进栈

将新数据结点插入到头结点之后。

// 进栈
void push(LinkStNode *&s, ElemType e)
{
    LinkStNode *p = (LinkStNode *) malloc(sizeof(LinkStNode));
    p->data = e;        // 将要进栈的元素e放入新建结点p的数据域中
    p->next = s->next;  // 将结点p插入到表头
    s->next = p;
}

出栈

在栈不为空的条件下，将头结点的后继（栈顶）结点的数据域赋给$e$，然后将其删除。

// 出栈
bool pop(LinkStNode *&s, ElemType &e)
{
    if (s->next == NULL) return false;  // 栈空的情况
    LinkStNode *p = s->next;            // p指向表头栈顶结点
    e = p->data;
    s->next = p->next;                  // 删除p结点
    free(p);                            // 释放p结点
    return true;
}

获取栈顶元素

在栈不为空的条件下，将头结点后继（栈顶）结点的数据域赋给$e$。

// 获取栈顶元素
bool getTop(LinkStNode *s, ElemType &e)
{
    if (s->next == NULL) return false;  // 栈空的情况
    e = s->next->data;
    return true;
}