栈的基本概念

数据结构的三要素 – 逻辑结构、数据运算、存储结构 。
(存储结构存储结构不同，运算的实现方式不同。)

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

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

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

空栈：不包含任何元素的栈。

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

栈的数学性质： $n$个不同元素进栈，出栈元素不同排列的个数为$\frac1{n+1}C^n_{2n}$。上述公式称为卡特兰（Catalan）数，可采用数学归纳法证明。

栈道基本操作：

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

顺序栈的定义

1
2
3
4
5
#define MaxSize 10 //栈中元素最大个数
typedef struct {
    int data[MaxSize]; //静态数组存放栈中元素
    int top; //栈顶
}SequenceStack;

栈的初始化：

1
2
3
4
5
6
7
8
/*** 
 * @description: 初始化栈
 * @param {SequenceStack&} S 输入栈
 * @return {*}
 */
void InitStack(SequenceStack& S) {
    S.top = -1; //初始化栈顶
}

栈的判空：

1
2
3
4
5
6
7
8
9
10
11
12
13
/*** 
 * @description: 栈判空
 * @param {SequenceStack} S
 * @return {*}
 */
bool isEmpty(SequenceStack S) {
    if (S.top = -1) {
        return true;
    }
    else {
        return false;
    }
}

入栈：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*** 
 * @description: 入栈操作
 * @param {SequenceStack&} S 顺序栈
 * @param {int} e 入栈元素
 * @return {*}
 */
bool Push(SequenceStack& S, int e) {
    if (S.top == MaxSize - 1) {
        printf("栈已满");
        return false;
    }
    S.top += 1; //调整栈顶位置
    S.data[S.top] = e; //新元素入栈
    //等价于 S.data[++S.top] = e;
    return true;
}

出栈：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*** 
 * @description: 出栈
 * @param {SequenceStack&} S 顺序栈
 * @param {int&} e 出栈元素
 * @return {*}
 */
bool Pop(SequenceStack& S, int& e) {
    if (S.top = -1) {
        printf("栈已空，无元素返回");
        return false;
    }
    e = S.data[S.top]; //栈顶元素先出栈
    S.top -= 1; //调整栈顶位置
    //等价于 e = S.data[S.top--];
    return true; 
}

获取栈顶元素：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*** 
 * @description: 获取栈顶元素
 * @param {SequenceStack} S 顺序栈
 * @param {int&} e 栈顶元素
 * @return {*}
 */
bool GetTop(SequenceStack S, int& e) {
    if (S.top == -1) {
        printf("栈已空，无元素返回");
        return false;
    }
    e = S.data[S.top]; //返回栈顶元素
    return true;
}

由静态数组定义的栈空间，使用结束后系统会自动回收。

共享栈的定义

1
2
3
4
5
6
#define MaxSize 10 //栈容量
typedef struct {
    int data[MaxSize];
    int top0; //0号栈顶
    int top1; //1号栈顶
}ShareStack;

共享栈的初始化：

1
2
3
4
5
6
7
8
9
/*** 
 * @description: 初始化共享栈
 * @param {ShareStack&} S
 * @return {*}
 */
void InitStack(ShareStack& S) {
    S.top0 = -1; //初始化0号栈顶
    S.top1 = MaxSize; //初始化1号栈顶
}

共享栈判空:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*** 
 * @description: 共享栈判空
 * @param {ShareStack} S 共享栈
 * @param {int} type 共享栈类型(0号还是1号)
 * @return {*}
 */
bool isEmpty(ShareStack S, int type) {
    if (type == 0) { //0号栈
        if (S.top0 == -1) {
            return true;
        }
    }
    if (type == 1) { //1号栈
        if (S.top1 == MaxSize) {
            return true;
        }
    }
    return false;
}

共享栈入栈:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/*** 
 * @description: 共享栈入栈
 * @param {ShareStack&} S 共享栈
 * @param {int} type 共享栈类型
 * @param {int} e 入栈元素
 * @return {*}
 */
bool Push(ShareStack& S,int type, int e) {
    if (type == 0) { //0号栈
        if (S.top0 + 1 == S.top1 ) {
            printf("共享栈已满");
            return false;
        }
        S.top0++;
        S.data[S.top0] = e;
        return true;

    }
    if (type == 1) { //1号栈
        if (S.top0 + 1 == S.top1 ) {
            printf("共享栈已满");
            return false;
        }
        S.data[S.top1] = e;
        S.top1--;
        return true;
    }
    return false;
}

共享栈出栈:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/*** 
 * @description: 共享栈出栈
 * @param {ShareStack&} S 共享栈
 * @param {int} type 共享栈类型
 * @param {int&} e 出栈元素
 * @return {*}
 */
bool Pop(ShareStack& S, int type, int& e) {
    if (type == 0) { //0号栈
        if (S.top0 == -1 ) {
            printf("共享栈为空");
            return false;
        }
        e = S.data[S.top0];
        S.top0--;
        return true;

    }
    if (type == 1) { //1号栈
        if (S.top1 == MaxSize) {
            printf("共享栈为空");
            return false;
        }
        e = S.data[--S.top1];
        return true;
    }
    return false;
}

由静态数组定义的栈空间，使用结束后系统会自动回收。

链式存储的栈

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

链栈的定义:

1
2
3
4
typedef struct Linknode{
  int data;
  struct Linknode *next;
}*LinkStack;

采用链式存储，便于结点的插入与删除。链栈道操作与链表类似，入栈和出栈的操作都在链表的表头进行（头插法）。

需要注意的是不带头节点和带头节点的链栈道具体实现会有所不同。