栈ADT

栈 Stack ADT
一、前提条件：栈是一种线性表。

它的特点是：只能在一端插入和删除。

这一端叫：栈顶 top

另一端叫：栈底 bottom

二、核心概念

栈的规则是：后进先出 LIFO

也就是：Last In First Out

例如依次入栈：
1
2
3

栈内逻辑是：
栈顶
↓
3
2
1

先进的扔到栈底，后进的在栈顶

出栈顺序是：
3 -> 2 -> 1

三、基本操作

栈 ADT 常见操作：

InitStack 初始化栈
Push 入栈
Pop 出栈
GetTop 取栈顶元素
IsEmpty 判空
IsFull 判满

四、顺序栈

1. 存储结构：用数组实现。

#define MAXSIZE 100

struct Stack {
int data[MAXSIZE];
int top;
};

这里：
data 存元素
top 表示栈顶下标

2. top 的定义

常见写法：top = -1 表示空栈

如果压入第一个元素：

top = 0

栈：

data[0]

如果再压入一个：

top = 1

栈：

data[0], data[1]

所以：top 永远指向当前栈顶元素。

五、顺序栈 C 语言模板

1. 初始化
   void InitStack(struct Stack* s)
   {
   s->top = -1;
   }

2. 判空
   int IsEmpty(struct Stack* s)
   {
   return s->top == -1;
   }

3. 判满
   int IsFull(struct Stack* s)
   {
   return s->top == MAXSIZE - 1;
   }

4. 入栈 Push
   int Push(struct Stack* s, int x)
   {
   if (IsFull(s)) {
   return 0;
   }

   s->top++;
   s->data[s->top] = x;

   return 1;
   }

也可以写成：
s->data[++s->top] = x;

5. 出栈 Pop
   int Pop(struct Stack* s, int* x)
   {
   if (IsEmpty(s)) {
   return 0;
   }

   *x = s->data[s->top];
   s->top--;

   return 1;
   }

这里用：int* x

是为了把出栈元素带回去。

6. 读取栈顶 GetTop
   int GetTop(struct Stack* s, int* x)
   {
   if (IsEmpty(s)) {
   return 0;
   }

   *x = s->data[s->top];

   return 1;
   }

注意：

GetTop 只读取，不删除。
Pop 读取并删除。

六、顺序栈完整代码
#define MAXSIZE 100

struct Stack {
int data[MAXSIZE];
int top;
};

void InitStack(struct Stack* s)
{
s->top = -1;
}

int IsEmpty(struct Stack* s)
{
return s->top == -1;
}

int IsFull(struct Stack* s)
{
return s->top == MAXSIZE - 1;
}

int Push(struct Stack* s, int x)
{
if (IsFull(s)) {
return 0;
}

s->top++;
s->data[s->top] = x;

return 1;

}

int Pop(struct Stack* s, int* x)
{
if (IsEmpty(s)) {
return 0;
}

*x = s->data[s->top];
s->top--;

return 1;

}

int GetTop(struct Stack* s, int* x)
{
if (IsEmpty(s)) {
return 0;
}

*x = s->data[s->top];

return 1;

}
七、顺序栈例子

初始：top = -1
栈为空

执行：Push(&s, 10);

变成：
data[0] = 10
top = 0

执行：Push(&s, 20);

变成：

data[0] = 10
data[1] = 20
top = 1

栈顶是：20

执行：Pop(&s, &x);

得到：

x = 20
top = 0

栈里剩：10

八、链式栈

顺序栈用数组，有最大容量限制。

链式栈用链表，没有固定容量限制。

1. 存储结构

struct Node {
int data;
struct Node* next;
};

struct LinkedStack {
struct Node* top;
};

这里：top 指向链表第一个节点。

也就是：链表头部就是栈顶。

九、链式栈 C 语言模板

1. 初始化
   void InitLinkedStack(struct LinkedStack* s)
   {
   s->top = NULL;
   }
2. 判空
   int IsLinkedStackEmpty(struct LinkedStack* s)
   {
   return s->top == NULL;
   }
3. 入栈 Push

链式栈入栈本质是：

头插法
#include <stdlib.h>

int PushLinkedStack(struct LinkedStack* s, int x)
{
struct Node* node =
malloc(sizeof(struct Node));

if (node == NULL) {
    return 0;
}

node->data = x;
node->next = s->top;
s->top = node;

//这里相当于是把node的next赋NULL，之后把top指向node，每次头插进之后，top都指向新的node，
return 1;
}

4. 出栈 Pop

链式栈出栈本质是：

删除头节点
int PopLinkedStack(struct LinkedStack* s, int* x)
{
if (IsLinkedStackEmpty(s)) {
return 0;
}

struct Node* p = s->top;

*x = p->data;

s->top = p->next;

//相当于就是把top对应的值返回给x，然后top去取next的值，这样相当于把原节点跳过
free(p);

return 1;

}

5. 读取栈顶
   int GetLinkedStackTop(struct LinkedStack* s, int* x)
   {
   if (IsLinkedStackEmpty(s)) {
   return 0;
   }

   *x = s->top->data;

   return 1;
   }

十、链式栈完整代码
#include <stdlib.h>

struct Node {
int data;
struct Node* next;
};

struct LinkedStack {
struct Node* top;
};

void InitLinkedStack(struct LinkedStack* s)
{
s->top = NULL;
}

int IsLinkedStackEmpty(struct LinkedStack* s)
{
return s->top == NULL;
}

int PushLinkedStack(struct LinkedStack* s, int x)//入栈
{
struct Node* node =
malloc(sizeof(struct Node));

if (node == NULL) {
    return 0;
}

node->data = x;
node->next = s->top;
s->top = node;

return 1;

}

int PopLinkedStack(struct LinkedStack* s, int* x)//出栈
{
if (IsLinkedStackEmpty(s)) {
return 0;
}

struct Node* p = s->top;

*x = p->data;

s->top = p->next;

free(p);

return 1;

}

int GetLinkedStackTop(struct LinkedStack* s, int* x)//查看栈顶
{
if (IsLinkedStackEmpty(s)) {
return 0;
}

*x = s->top->data;

return 1;

}

十一、链式栈例子

初始：top = NULL

入栈 10：

top
↓
10 -> NULL

入栈 20：

top
↓
20 -> 10 -> NULL

入栈 30：

top
↓
30 -> 20 -> 10 -> NULL

出栈：

弹出 30
top 指向 20

变成：

top
↓
20 -> 10 -> NULL

十二、顺序栈和链式栈
类型 存储方式 优点 缺点
顺序栈 数组 简单、访问快 容量固定

链式栈 链表 容量灵活 需要 malloc/free

栈的常见算法题

栈常用于：

1. 括号匹配
2. 表达式求值
3. 单调栈
4. 递归转非递归
5. DFS
6. 函数调用栈
7. 浏览器前进后退
8. 字符串消除

顺序栈优点：
简单，速度快。

顺序栈缺点：
容量固定。

链式栈优点：
容量灵活。

链式栈缺点：
需要动态申请和释放内存。

栈就是只能在一端操作的线性表，规则是后进先出。