【数据结构】栈和队列——栈
目录
- 栈和队列
- 栈
- 栈的基本概念
- 栈的顺序存储实现
- 栈的定义与初始化
- 入栈操作
- 出栈操作
- 读取栈顶元素
- 判空和判满操作
- 栈的销毁操作
- 操作集合
栈和队列
栈
栈的基本概念
栈的定义：
- 栈（Stack） 是一种线性表，它限定了数据元素的插入和删除操作只能在表的一端进行。
- 允许操作的一端称为 栈顶（Top），另一端称为 栈底（Bottom）。
所以，栈就是 “先进后出（FILO, First In Last Out）” 的数据结构。
栈的特点：
- 受限性：只能在栈顶进行插入（push）和删除（pop）。
- 线性结构：元素有先后次序。
- FILO 特性：最先入栈的元素最后出栈。
形象理解：就像一摞盘子，先放进去的盘子在最下面，拿的时候只能从最上面一个个拿走。
栈的基本操作：
- Push（入栈）：在栈顶插入一个新元素。
- Pop（出栈）：删除栈顶元素，并返回该元素。
- GetTop（读栈顶元素）：仅仅读取栈顶元素，不删除。
- InitStack（初始化栈）：建立一个空栈。
- StackEmpty（判空）：检查栈是否为空。
- StackFull（判满，顺序栈时需要）：判断栈是否已满。
栈的存储结构：
- 顺序栈：
- 用数组存储栈元素。
- 优点：实现简单，存取快。
- 缺点：容量固定，可能溢出（上溢/下溢）。
- 链式栈
- 用链表存储，栈顶一般在链表的表头。
- 优点：容量不受限制。
- 缺点：需要额外指针，操作相对慢。
栈的顺序存储实现
栈的定义与初始化
顺序栈是栈的一种顺序存储结构，用数组（连续内存）来存放数据元素。特点：
- 栈顶指针（top）指向栈顶元素的位置（或空元素的下一个位置）。
- 栈容量固定（静态）或可扩展（动态）。
- 支持的基本操作：
- 初始化栈
InitStack - 入栈
Push - 出栈
Pop - 判空
IsEmpty - 获取栈顶元素
GetTop
- 初始化栈
顺序栈top 指针的指向在不同教材中有差异：
- top 指向栈顶元素（经典写法，大部分算法书和面试中用的）
top是数组下标- 空栈时：
top = -1 - 入栈：先
top++，再存元素 - 出栈：取
data[top]，再top-- - 特点：top 总是指向有效元素的位置
- top 指向栈顶下一个空位（部分教材/视频中用）
top是指针- 空栈时：
top = 0 - 入栈：直接存到
data[top]，然后top++ - 出栈：先
top--，再取data[top] - 特点：top 表示栈中元素数量，也就是下一个可用位置
两种方法逻辑不同，但功能一样，只是 top 的含义不同。
静态顺序栈：
- 定义：
#define MAXSIZE 100 typedef int SElemType; // 假设存储 int 类型typedef struct {SElemType *base; // 栈底指针，指向数组首地址SElemType *top; // 栈顶指针，指向栈顶元素的下一个位置int stacksize; // 栈容量 } SqStack; - 初始化：
特点：// 初始化 void InitStack(SqStack *S) {S->base = data; // base 指向数组首地址S->top = S->base; // 空栈，top 指向第一个空位S->stacksize = MAXSIZE; }- 容量固定，无法扩容
- top 指向栈顶元素的下一个位置
- 入栈/出栈时用
*(S->top++) = e/*e = *(--S->top)
动态顺序栈： 动态顺序栈可以在栈满时自动扩容。
- 定义：
typedef int SElemType;typedef struct {SElemType *base; // 栈底指针SElemType *top; // 栈顶指针，指向栈顶元素的下一个位置int stacksize; // 当前容量 } SqStack; - 初始化：
// 初始化 int InitStack(SqStack *S, int initSize) {S->base = (SElemType *)malloc(initSize * sizeof(SElemType));if (!S->base) return 0; // 分配失败S->top = S->base; // 空栈S->stacksize = initSize;return 1; }
动态顺序栈可以在
Push时判断容量是否够，如果不够就 realloc 扩容。#include <stdio.h> #include <stdlib.h>typedef int SElemType; // 统一元素类型typedef struct {SElemType *base; // 栈底指针SElemType *top; // 栈顶指针（指向栈顶元素的下一个位置）int stacksize; // 当前容量 } SqStack;// 初始化栈 int InitStack(SqStack *S, int initSize) {S->base = (SElemType *)malloc(initSize * sizeof(SElemType));if (!S->base) return 0; // 分配失败S->top = S->base; // 空栈：栈顶=栈底S->stacksize = initSize;return 1; }// 入栈 int Push(SqStack *S, SElemType x) {// 判断栈满，需要扩容if (S->top - S->base >= S->stacksize) {int newSize = S->stacksize * 2;SElemType *newBase = (SElemType *)realloc(S->base, newSize * sizeof(SElemType));if (!newBase) return 0; // 扩容失败// 更新指针和容量S->top = newBase + (S->top - S->base); // 调整栈顶指针（原偏移量不变）S->base = newBase;S->stacksize = newSize;printf("栈扩容到 %d\n", newSize);}*(S->top++) = x; // 先赋值，再移动栈顶指针return 1; }// 出栈（将栈顶元素存入e，成功返回1，失败返回0） int Pop(SqStack *S, SElemType *e) {if (S->top == S->base) return 0; // 空栈*e = *(--S->top); // 先移动栈顶指针，再取值return 1; }int main() {SqStack S;if (!InitStack(&S, 3)) { // 初始容量3printf("栈初始化失败\n");return 1;}// 入栈10个元素（测试扩容）for (int i = 1; i <= 10; i++) {if (Push(&S, i)) {printf("入栈: %d, 当前元素数: %d\n", i, S.top - S.base);} else {printf("入栈 %d 失败\n", i);}}// 出栈所有元素SElemType e;printf("\n出栈顺序：\n");while (Pop(&S, &e)) {printf("出栈: %d\n", e);}free(S.base); // 释放堆内存return 0; }
入栈操作
入栈（Push） 就是把一个新元素压入栈顶的操作。
核心逻辑：
- 判断栈是否已满（静态栈）或是否需要扩容（动态栈）。
- 栈顶指针
top上移（或计算位置）。 - 将元素放到栈顶位置。
- 更新
top（或数组索引）。
栈遵循 后进先出（LIFO） 原则，所以新元素总是放在栈顶。
静态顺序栈入栈：
void Push(SqStack *S, int e) {// 判断是否栈满if (S->top - S->base >= S->stacksize) {return 0; // 入栈失败}*(S->top) = e; // 把元素放到 top 指向的位置S->top++; // top 后移，指向下一个空位return 1; // 入栈成功
}
- 空栈时：
top == base。 - 入栈成功后：
top始终指向“栈顶元素的下一个位置”。 - 栈满条件：
top - base == stacksize。 - 栈顶元素：
*(top - 1)。
动态顺序栈入栈：
// 入栈
void Push(SqStack *S, int e) {if (S->top - S->base >= S->stacksize) { // 栈满，需要扩容S->base = (ElemType *)realloc(S->base, (S->stacksize + STACKINCREMENT) * sizeof(ElemType));if (!S->base) exit(0); // 内存不足S->top = S->base + S->stacksize; // 重新定位 topS->stacksize += STACKINCREMENT; // 更新容量}*(S->top) = e; // 把元素放到栈顶S->top++; // top 指针上移
}
动态顺序栈入栈图示：
初始栈（容量=3） 入栈扩容后（容量=6）
+----+----+----+ +----+----+----+----+----+----+
| 10 | 20 | 30 | | 10 | 20 | 30 | 40 | | |
+----+----+----+ +----+----+----+----+----+----+↑ ↑top top
出栈操作
// 出栈操作：将栈顶元素弹出并返回给 e
int Pop(SqStack *S, int *e) {if (S->top == S->base) return 0; // 栈空S->top--; // 指针下移*e = *(S->top); // 取出元素return 1;
}
S->top--; 和 *e = *(S->top); 可以合并为 *e = *(--S->top);
有道例题：写出下列程序段的输出结果
void main(){Stack S;InitStack(S);x='c'; y='k';Push(S,x); Push(S,'a'); Push(S,y);Pop(S,x); Push(S,'t'); Push(S,x);Pop(S,x); Push(S,'s');While(!StackEmpty(S)) {Pop(S,y); printf(y);}printf(x);
}
Pop 会将出栈的数据返回，在这题中的重点是 Pop 操作会改变原来 x 中的数据
读取栈顶元素
核心思想：
- 栈顶元素位于
top的前一个位置（因为top指向栈顶元素的下一个空位）。 - 不改变
top指针的值，只是返回栈顶元素。
// 取栈顶元素，不出栈
int GetTop(SqStack S, int *e) {if (S.top == S.base) return ERROR; // 空栈*e = *(S.top - 1); // 栈顶元素return 1;
}
top指向栈顶元素的下一个位置；- 栈顶元素是
*(top - 1)； GetTop不改变栈结构，只返回栈顶元素；
判空和判满操作
- 判空操作：
核心思想：栈空时，top == base，因为没有元素，栈顶指针就在栈底。// 判空 int StackEmpty(SqStack S) {if (S.top == S.base) return 1; // 栈空else return 0; // 栈非空 } - 判满操作
核心思想：栈满时，top - base == stacksize，因为栈顶指针指向下一个空位，减去栈底得到元素个数等于容量。// 判满 int StackFull(SqStack S) {if (S.top - S.base == S.stacksize)return 1; // 栈满elsereturn 0; // 栈未满 }
栈的销毁操作
核心思想：
- 栈底指针
base是动态分配的，所以只需要free(base)。 - 销毁后，将
base和top置为NULL，stacksize置为 0，防止野指针。
Status DestroyStack(SqStack *S) {if (S->base) {free(S->base); // 释放动态分配的内存S->base = NULL;S->top = NULL;S->stacksize = 0;return OK;}return ERROR; // 栈本身为空或未初始化
}
- 栈使用
malloc分配内存后，必须用free释放，否则会 内存泄漏。 - 销毁后把
base和top置为NULL，stacksize置 0，避免野指针。 - 对静态顺序栈（数组固定分配）则不需要销毁操作，因为数组在栈上分配，程序结束自动释放。
操作集合
#include <stdio.h>
#include <stdlib.h>#define MAXSIZE 100
#define OK 1
#define ERROR 0typedef int Status;
typedef int SElemType;// 顺序栈定义（老师写法）
typedef struct {SElemType *base; // 栈底指针SElemType *top; // 栈顶指针（指向下一个空位）int stacksize; // 栈容量
} SqStack;// 初始化栈
Status InitStack(SqStack *S) {S->base = (SElemType *)malloc(MAXSIZE * sizeof(SElemType));if (!S->base) return ERROR;S->top = S->base;S->stacksize = MAXSIZE;return OK;
}// 入栈
Status Push(SqStack *S, SElemType e) {if (S->top - S->base == S->stacksize) return ERROR; // 栈满*(S->top) = e;S->top++;return OK;
}// 出栈
Status Pop(SqStack *S, SElemType *e) {if (S->top == S->base) return ERROR; // 空栈S->top--;*e = *(S->top);return OK;
}// 取栈顶元素（不出栈）
Status GetTop(SqStack S, SElemType *e) {if (S.top == S.base) return ERROR; // 空栈*e = *(S.top - 1);return OK;
}// 判空
Status StackEmpty(SqStack S) {return S.top == S.base ? 1 : 0;
}// 判满
Status StackFull(SqStack S) {return (S.top - S.base == S.stacksize) ? 1 : 0;
}// 销毁栈
Status DestroyStack(SqStack *S) {if (S->base) {free(S->base);S->base = NULL;S->top = NULL;S->stacksize = 0;return OK;}return ERROR;
}// 打印栈内元素（从栈底到栈顶）
void PrintStack(SqStack S) {SElemType *p = S.base;while (p < S.top) {printf("%d ", *p);p++;}printf("\n");
}// 测试顺序栈操作
int main() {SqStack S;if (InitStack(&S) == ERROR) {printf("栈初始化失败！\n");return 0;}printf("栈是否为空: %d\n", StackEmpty(S));// 入栈for (int i = 1; i <= 5; i++) {Push(&S, i);printf("入栈: %d, 栈顶元素: %d\n", i, *(S.top - 1));}printf("当前栈: ");PrintStack(S);printf("栈是否已满: %d\n", StackFull(S));// 取栈顶元素SElemType e;if (GetTop(S, &e) == OK) {printf("栈顶元素: %d\n", e);}// 出栈while (!StackEmpty(S)) {Pop(&S, &e);printf("出栈元素: %d\n", e);}printf("栈是否为空: %d\n", StackEmpty(S));// 销毁栈DestroyStack(&S);printf("销毁栈后, 栈容量: %d, base指针: %p\n", S.stacksize, S.base);return 0;
}
程序运行结果如下：
