栈的基本概念

栈的定义

栈（Stack）是只允许在一端进行插入或删除操作的线性表。

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

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

空栈。不含任何元素的空表。

栈的操作特性：后进先出（Last In First Out，LIFO）。

栈的基本操作

InitStack(&S)：初始化一个空栈S。
StackEmpty(S)：判断一个栈是否为空，若栈S为空则返回true，否则返回false。
Push(&S, x)：进栈，若栈S未满，则将x加入使之成为新栈顶。
Pop(&S, &x)：出栈，若栈S非空，则弹出栈顶元素，并用x返回。
GetTop(S, &x)：读栈顶元素，若栈S非空，则用x返回栈顶元素。
DestroyStack(&S)：销毁栈，并释放栈S所占用的存储空间。

栈的顺序存储结构

顺序栈的实现

采用顺序存储的栈称为顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针（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。

顺序栈的基本操作的实现

初始化

1
2
3

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

判栈空

bool StackEmpty(SqStack S) {
    if (S.top == -1) { // 栈空
        return true;
    }
    else {             // 栈不空
        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--;           // 指针再减1
    return true;
}

读栈顶元素

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

仅仅是读取栈顶元素，并没有出栈的操作，因此原栈顶元素依然保留在栈中。

栈的链式存储结构

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

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

typedef struct LinkNode {
    Elemtype data;         // 数据域
    struct LinkNode *next; // 指针域
} *LinkStack;                // 栈类型定义

入栈和出栈的操作都在链表的表头进行。

王理庚的博客

数据结构-栈