# 数据结构-栈的应用和实现

本文原文链接 (opens new window)

栈是线性结构的常见应用，是一种可以实现"先进后出"的存储结构，🌰：让我们想一下箱子📦，往📦里面放东西，最先放入📦中的东西被放在底部，后放入的反而在上面，假设我们从上至下的拿东西，那么就是先放入的后出，后放入的先出，即这就是一个"先入后出"的存储结构。

栈的应用非常的广泛：函数调用、中断、表达式求值、内存分配、缓存、迷宫都有应用栈的知识。

栈和队列实现虽然不同，但都可以通过数组和链表实现，栈分为静态栈和动态栈，静态栈有数组构成，动态栈有链表构成。

其中的核心操作就是：压栈和出栈。压栈就是放入栈中，出栈就是拿出栈中。下面我们看看栈的基本结构：

  栈顶Top                       栈底Bottom
    👇                             👇
[data|next]——>[data|next]——>[data=NULL|next]——> NULL

1
2
3

确认一个栈只需要两个参数，栈顶Top和栈底Bottom，初始创建时，栈顶Top等于栈底Bottom；压栈时，栈顶Top移动；出栈时，还是栈顶Top移动。

# C语言栈实现

首先我们先来做好初始化的准备：

// 链表元素结构体
typedef struct Node {
    int data;
    struct Node * next;
}Node, *pNode;

// 栈的参数
typedef struct Stack {
    pNode pTop;         // 栈顶
    pNode pBottom;      // 栈底
}Stack, *pStack;

// 初始化
void initStack(pStack s);
// 压栈
void pushStack(pStack s, int value);
// 遍历
void traverseStack(pStack s);
// 出栈
bool popStack(pStack s);

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

以上就是栈的基本操作，下面是函数的实现

// 初始化
void initStack(pStack s) {
    s->pTop = (pNode)malloc(sizeof(Node));
    if(s->pTop == NULL) {
        printf("内存分配失败");
        exit(-1);
    }
    s->pBottom = s->pTop;
    s->pTop->next = NULL;
}
// 压栈
void pushStack(pStack s, int value){
    pNode pNew = (pNode)malloc(sizeof(Node));
    if(pNew == NULL) {
        printf("内存分配失败");
        exit(-1);
    }
    s->pTop = pNew;
    pNew->data = value;
    pNew->next = s->pBottom;
}
// 遍历
void traverseStack(pStack s){
    pNode top = s->pTop;
    while(top->next != NULL){
        peintf("%d\n", top->data);
        top = top->next;
    }
}
// 出栈
bool popStack(pStack s){
    pNode node = s->pTop;
    if(node->next != NULL){
        return false;s
    }
    s->pTop = s->pTop->next;
    free(node);
    retrun 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
30
31
32
33
34
35
36
37
38
39

main函数中创建调用栈：

int main() {
    // 创建栈
    Stack s;
    
    initStack(&s);
    pushStack(&s, 1);
    pushStack(&s, 2);
    pushStack(&s, 3);
    pushStack(&s, 4);
    traverseStack(&s);
    popStack(&s);
    traverseStack(&s);
    
    return 0;
}