堆栈是一种数据项按序排列的数据结构，只能在一端（称为栈顶(top)）对数据项进行插入和删除。

简单地说，堆栈可以看作一个箱子，只能在一端放和取，所以其主要操作有：

  • 插入数据：入栈（Push）
  • 删除数据：出栈（Pop）

而只能一端存取，也形成了其最主要的特性：

  • 后入先出：Last In First Out（LIFO）

类型名称：堆栈（Stack）

数据对象集：一个有0个或多个元素的有穷线性表

操作集：长度为 MaxSize 的堆栈 S 属于 Stack ， 堆栈元素 item 属于 ElementType

1
2
3
4
5
1. Stack CreateStack  ()						生成空堆栈
2. int IsFull (Stack S)							判断堆栈S是否已满
3. void Push (Stack PtrS, ElementType item)		 将元素item压入堆栈
4. int IsEmpty (Stack S)					    判断堆栈S是否为空
5. ElementType Pop (Stack PtrS)					删除堆栈并返回栈顶元素

栈的顺序储存实现

所谓顺序存储，也就是利用数组来实现栈的相关操作，那么根据之前的叙述，我们可以写出栈库的头文件 Stack.h

C语言代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#ifndef DATA_STRUCTURE_STACK_H
#define DATA_STRUCTURE_STACK_H


#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef int elementType;
typedef struct SNode* stack;
struct SNode{
    int* stack;	// 栈元素所在的数组
    int allocLength;	// 栈的大小
    int top;	// 栈顶下标
};

stack createStack();
void push (stack s, int val);
elementType pop (stack s);
bool isFull(stack s);
bool isEmpty(stack s);

#endif //DATA_STRUCTURE_STACK_H
  • 说明： 栈所在结构体，为了使其大小可扩展，所以将 stack[] 数组以指针的方式替换，同时增加了一个用于保存栈大小的元素，即 allocLength

接下来在 Stack.c 中实现所定义的函数。

C语言代码：

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
30
31
32
33
34
35
/*
 * Created by wenmang on 2019/7/22.
 */

#include <assert.h>
#include "Stack.h"

stack createStack() {
    stack s =  (stack) malloc(sizeof(struct SNode));
    s->allocLength = 8;	// 栈初始空间分配为 8
    s->top = 0;
    s->stack = (elementType*) malloc(sizeof(elementType) * s->allocLength);
    return s;
}

void push (stack s, int val) {
    if (isFull(s)) {
        s->allocLength *= 2;
        s->stack = (elementType*) realloc(s->stack, sizeof(elementType) * s->allocLength);
    }
    s->stack[s->top++] = val;
}

elementType pop (stack s) {
    assert(s->top >= 0);
    return s->stack[s->top--];
}

bool isFull(stack s) {
    return s->top == s->allocLength-1;
}

bool isEmpty(stack s) {
    return s->top < 0;
}

思考

问：一个数组实现两个堆栈

  1. 数组对半分之后分别从左向右储存

    缺点：对半分之后，如果右边的数组放满之后左边却未放满，即有空间却无法再储存，就会造成空间浪费

  2. 一个从左向右，一个从右向左（改进方法）

对应栈的结构体如下：

1
2
3
4
5
6
7
8
typedef struct SNode *Stack;
struct DStack{
    ElementType Data[MaxSize];
    int Top1;
    int Top2;    // 表示栈中元素的下标
}S;
S.Top1 = -1;	// 栈1的初始下标为-1
S.Top2 = MaxSize;	//栈2的初始下标为MaxSise

压栈

1
2
3
4
5
6
7
8
9
10
11
void Push(struct DStack *ParS, ElementType item, int Tag){  // 压栈操作
    /* Tag 为区分两个堆栈的标志 取值为1和2 */
    if (PtrS->Top2 - PtrS->Top1 == 1){
        printf("堆栈满");
        return;
    }
    if (Tag == 1)   // 压入第一个堆栈
        PtrS->Data[++(PtrS->Top1)] = item;
    else    // 压入第二个堆栈
        PtrS->Data[--(PtrS->Top1)] = item;
}

弹栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
ElementType Pop(struct DStack *ParS, int Tag){  // 弹栈操作 两个栈分别考虑
    /* Tag 为区分两个堆栈的标志 取值为1和2 */
    if (Tag == 1){
        if (PtrS->Top1 == -1){
            printf("堆栈1为空");
            return;
        } else
            return PtrS-Data[(PtrS->Top1)--];
    } else {
        if (PtrS->Top2 == MaxSize){
            printf("堆栈2为空");
            return NULL;
        } else
            return PtrS->Data[(PtrS->Top2)++];
    }
}

堆栈的链式储存实现

链式存储其实我认为就栈而言，并不占什么优势，所以一般顺序实现即可，链式存储的 Stack.h 如下：

C语言代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#ifndef DATA_STRUCTURE_STACK_H
#define DATA_STRUCTURE_STACK_H


#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct LNode* lStack;
struct LNode{   // 链式存储的栈
    elementType data;
    struct LNode* next;
};

lStack createLStack();
void pushL (lStack s, int val);
int popL (lStack s);
bool isLEmpty(lStack s);

#endif //DATA_STRUCTURE_STACK_H

函数实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
lStack createLStack(){
    lStack s = (lStack) malloc(sizeof(struct LNode));
    s->next = NULL;
    return s;
}

void pushL (lStack s, int val) {
    struct LNode* tmp = (lStack) malloc(sizeof(struct LNode));
    tmp->data = val;
    tmp->next = s->next;
    s->next = tmp;
}

elementType popL (lStack s) {
    assert(s->next != NULL);
    int tmp = s->next->data;
    s->next = s->next->next;
    return tmp;
}

bool isLEmpty(lStack s) {
    return s->next == NULL;
}

说明： 链式存储的栈，为方便操作，是带有头指针的。

学习的数据结构就是拿来用的，而如今的许多高级语言，已经将绝大多数数据结构以库的形式封装起来，在使用的时候，我们只需要直接调用即可，而不需要自己再写一个栈。例如 Java 中的 Stack 类，我们在使用的时候如果不熟，则可以查看文档，然后直接调用即可。

在熟悉构成之后，便可以进行应用，比如刷LeetCode