数据结构-栈和队列

张

张建站

2026/6/14 2:05:55

10分钟阅读

目录栈栈的概念及结构栈的实现接口动态栈支持扩容的结构定义1. 初始化栈2. 入栈3. 出栈4. 获取栈顶元素5. 获取栈中有效元素个数6. 检测栈是否为空7. 销毁栈代码总队列队列的概念及结构队列的实现接口1. 初始化队列2. 队尾入队列3. 队头出队列4. 获取队列头部元素5. 获取队列队尾元素6. 获取队列中有效元素个数7. 检测队列是否为空8. 销毁队列代码总循环队列为什么需要循环队列循环队列的结构数组实现区分队空和队满方法一牺牲一个存储单元方法二增加一个 size 变量循环队列的基本操作以牺牲一个单元的方法为例1. 初始化循环队列2. 判断队列是否为空3. 判断队列是否已满4. 入队5. 出队6. 获取队头元素7. 获取队尾元素8. 获取队列中元素个数9. 销毁队列代码总栈和队列面试题概念选择题栈栈的概念及结构栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶另一端称为栈底。栈中的数据元素遵守后进先出LIFOLast In First Out的原则。压栈栈的插入操作叫做进栈/压栈/入栈入数据在栈顶。出栈栈的删除操作叫做出栈。出数据也在栈顶栈的实现栈的实现一般可以使用数组或者链表实现相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小接口//下面是定长的静态栈的结构实际中一般不实用所以我们主要实现下面的支持动态增长的栈 typedef int STDataType; #define N 10 typedef struct Stack { STDataType _a[N]; int _top; // 栈顶 }Stack; // 支持动态增长的栈 typedef int STDataType; typedef struct Stack { STDataType* _a; int _top; // 栈顶 int _capacity; // 容量 }Stack; // 初始化栈 void StackInit(Stack* ps); // 入栈 void StackPush(Stack* ps, STDataType data); // 出栈 void StackPop(Stack* ps); // 获取栈顶元素 STDataType StackTop(Stack* ps); // 获取栈中有效元素个数 int StackSize(Stack* ps); // 检测栈是否为空如果为空返回非零结果如果不为空返回0 int StackEmpty(Stack* ps); // 销毁栈 void StackDestroy(Stack* ps);动态栈支持扩容的结构定义_top表示下一个可以存放元素的位置即栈中元素个数。初始化时_top 0入栈时先放入再_top出栈时直接_top--。_capacity表示数组最多能容纳的元素个数。当_top _capacity时需要扩容通常 2 倍增长。typedef int STDataType; // 栈中元素类型可修改 typedef struct Stack { STDataType* _a; // 指向动态开辟的数组 int _top; // 栈顶位置通常指向栈顶元素的下一个位置 int _capacity; // 当前已分配的容量 } Stack;1. 初始化栈解释将栈结构体的指针、容量、栈顶都初始化为 0。注意_a先置为 NULL后续第一次入栈时再动态分配。时间复杂度 O(1)。// 初始化栈 void StackInit(Stack* ps) { assert(ps ! NULL); ps-_a NULL; ps-_top 0; // 栈顶初始为 0表示没有元素 ps-_capacity 0; }2. 入栈解释将数据压入栈顶。先检查是否需要扩容若_top _capacity则扩容原容量为 0 时分配 4 个空间否则翻倍。然后在_a[_top]处放入数据_top。// 入栈 void StackPush(Stack* ps, STDataType data) { assert(ps ! NULL); // 检查容量满了就扩容 if (ps-_top ps-_capacity) { int newCapacity (ps-_capacity 0) ? 4 : ps-_capacity * 2; STDataType* tmp (STDataType*)realloc(ps-_a, newCapacity * sizeof(STDataType)); if (tmp NULL) { perror(realloc fail); return; } ps-_a tmp; ps-_capacity newCapacity; } // 放入数据 ps-_a[ps-_top] data; ps-_top; }3. 出栈解释删除栈顶元素。只需将_top--即可逻辑删除。前提是栈非空需断言检查。// 出栈 void StackPop(Stack* ps) { assert(ps ! NULL); assert(ps-_top 0); // 栈不能为空 ps-_top--; }4. 获取栈顶元素解释返回栈顶元素的值不是删除。由于_top指向栈顶元素的下一个位置栈顶元素下标为_top - 1。需确保栈非空。// 获取栈顶元素 STDataType StackTop(Stack* ps) { assert(ps ! NULL); assert(ps-_top 0); return ps-_a[ps-_top - 1]; }5. 获取栈中有效元素个数解释直接返回_top的值即栈中元素个数。// 获取栈中有效元素个数 int StackSize(Stack* ps) { assert(ps ! NULL); return ps-_top; }6. 检测栈是否为空解释如果栈为空返回非零常用 1如果不为空返回 0。实现上直接返回_top 0的结果。// 检测栈是否为空如果为空返回非零结果如果不为空返回0 int StackEmpty(Stack* ps) { assert(ps ! NULL); return ps-_top 0 ? 1 : 0; // 空返回1非空返回0 }7. 销毁栈解释释放动态申请的数组内存并将指针置为 NULL同时重置_top和_capacity。防止内存泄漏。// 销毁栈 void StackDestroy(Stack* ps) { assert(ps ! NULL); if (ps-_a ! NULL) { free(ps-_a); ps-_a NULL; } ps-_top 0; ps-_capacity 0; }代码总#include stdio.h #include stdlib.h #include assert.h typedef int QDataType; // 队列结点 typedef struct QListNode { struct QListNode* _pNext; QDataType _data; } QNode; // 队列结构含头尾指针和元素个数 typedef struct Queue { QNode* _front; // 队头指针 QNode* _rear; // 队尾指针 int _size; // 队列中元素个数 } Queue; // 初始化队列 void QueueInit(Queue* q) { assert(q ! NULL); q-_front NULL; q-_rear NULL; q-_size 0; } // 队尾入队列 void QueuePush(Queue* q, QDataType data) { assert(q ! NULL); QNode* newNode (QNode*)malloc(sizeof(QNode)); if (newNode NULL) { perror(malloc fail); return; } newNode-_data data; newNode-_pNext NULL; if (q-_front NULL) // 空队列 { q-_front newNode; q-_rear newNode; } else { q-_rear-_pNext newNode; q-_rear newNode; } q-_size; } // 队头出队列 void QueuePop(Queue* q) { assert(q ! NULL); assert(q-_front ! NULL); // 队列非空 QNode* del q-_front; q-_front q-_front-_pNext; if (q-_front NULL) // 删除后队列为空 q-_rear NULL; free(del); q-_size--; } // 获取队列头部元素 QDataType QueueFront(Queue* q) { assert(q ! NULL); assert(q-_front ! NULL); return q-_front-_data; } // 获取队列队尾元素 QDataType QueueBack(Queue* q) { assert(q ! NULL); assert(q-_rear ! NULL); return q-_rear-_data; } // 获取队列中有效元素个数 int QueueSize(Queue* q) { assert(q ! NULL); return q-_size; } // 检测队列是否为空如果为空返回非零结果如果非空返回0 int QueueEmpty(Queue* q) { assert(q ! NULL); return q-_front NULL ? 1 : 0; } // 销毁队列 void QueueDestroy(Queue* q) { assert(q ! NULL); QNode* cur q-_front; while (cur ! NULL) { QNode* next cur-_pNext; free(cur); cur next; } q-_front NULL; q-_rear NULL; q-_size 0; } // 测试入口 int main() { Queue q; QueueInit(q); printf(入队 10, 20, 30\n); QueuePush(q, 10); QueuePush(q, 20); QueuePush(q, 30); printf(队头: %d, 队尾: %d, 大小: %d\n, QueueFront(q), QueueBack(q), QueueSize(q)); // 队头: 10, 队尾: 30, 大小: 3 printf(出队\n); QueuePop(q); printf(队头: %d, 队尾: %d, 大小: %d\n, QueueFront(q), QueueBack(q), QueueSize(q)); // 队头: 20, 队尾: 30, 大小: 2 printf(再入队 40, 50\n); QueuePush(q, 40); QueuePush(q, 50); printf(当前队列: ); while (!QueueEmpty(q)) { printf(%d , QueueFront(q)); QueuePop(q); } printf(\n); printf(队列空: %s\n, QueueEmpty(q) ? 是 : 否); // 队列空: 是 QueueDestroy(q); return 0; }队列队列的概念及结构队列只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出 FIFO(First In First Out)入队列进行插入操作的一端称为队尾出队列进行删除操作的一端称为队头队列的实现队列也可以数组和链表的结构实现使用链表的结构实现更优一些因为如果使用数组的结构出队列在数组头上出数据效率会比较低。接口typedef int QDataType; // 队列结点 typedef struct QListNode { struct QListNode* _pNext; QDataType _data; } QNode; // 队列结构含头尾指针和元素个数 typedef struct Queue { QNode* _front; // 队头指针 QNode* _rear; // 队尾指针 int _size; // 队列中元素个数 } Queue; // 初始化队列 void QueueInit(Queue* q); // 队尾入队列 void QueuePush(Queue* q, QDataType data); // 队头出队列 void QueuePop(Queue* q); // 获取队列头部元素 QDataType QueueFront(Queue* q); // 获取队列队尾元素 QDataType QueueBack(Queue* q); // 获取队列中有效元素个数 int QueueSize(Queue* q); // 检测队列是否为空如果为空返回非零结果如果非空返回0 int QueueEmpty(Queue* q); // 销毁队列 void QueueDestroy(Queue* q);1. 初始化队列解释将队列的头尾指针置为NULL元素个数置为 0。void QueueInit(Queue* q) { assert(q ! NULL); q-_front NULL; q-_rear NULL; q-_size 0; }2. 队尾入队列解释在链表尾部插入新结点。先动态申请新结点赋值。如果队列为空_front NULL则头尾都指向新结点否则将当前尾结点的_pNext指向新结点再更新_rear指向新结点。最后_size。void QueuePush(Queue* q, QDataType data) { assert(q ! NULL); QNode* newNode (QNode*)malloc(sizeof(QNode)); if (newNode NULL) { perror(malloc fail); return; } newNode-_data data; newNode-_pNext NULL; if (q-_front NULL) // 空队列 { q-_front newNode; q-_rear newNode; } else { q-_rear-_pNext newNode; q-_rear newNode; } q-_size; }3. 队头出队列解释删除队头结点。需保证队列非空。保存队头结点将_front指向下一个结点。如果队头成为NULL即队列变空则_rear也要置为NULL。释放原队头结点_size--。void QueuePop(Queue* q) { assert(q ! NULL); assert(q-_front ! NULL); // 队列非空 QNode* del q-_front; q-_front q-_front-_pNext; if (q-_front NULL) // 删除后队列为空 q-_rear NULL; free(del); q-_size--; }4. 获取队列头部元素解释返回队头结点的数据但不删除。需保证队列非空。QDataType QueueFront(Queue* q) { assert(q ! NULL); assert(q-_front ! NULL); return q-_front-_data; }5. 获取队列队尾元素解释返回队尾结点的数据。需保证队列非空。QDataType QueueBack(Queue* q) { assert(q ! NULL); assert(q-_rear ! NULL); return q-_rear-_data; }6. 获取队列中有效元素个数解释直接返回_size字段的值。int QueueSize(Queue* q) { assert(q ! NULL); return q-_size; }7. 检测队列是否为空解释如果队列为空返回非零通常 1否则返回 0。可以判断_front NULL或_size 0。int QueueEmpty(Queue* q) { assert(q ! NULL); return q-_front NULL ? 1 : 0; }8. 销毁队列解释释放链表中所有结点防止内存泄漏。遍历链表依次free每个结点最后将头尾指针置NULL大小置 0。void QueueDestroy(Queue* q) { assert(q ! NULL); QNode* cur q-_front; while (cur ! NULL) { QNode* next cur-_pNext; free(cur); cur next; } q-_front NULL; q-_rear NULL; q-_size 0; }代码总#include stdio.h #include stdlib.h #include assert.h typedef int QDataType; typedef struct QListNode { struct QListNode* _pNext; QDataType _data; } QNode; typedef struct Queue { QNode* _front; QNode* _rear; int _size; } Queue; void QueueInit(Queue* q); void QueuePush(Queue* q, QDataType data); void QueuePop(Queue* q); QDataType QueueFront(Queue* q); QDataType QueueBack(Queue* q); int QueueSize(Queue* q); int QueueEmpty(Queue* q); void QueueDestroy(Queue* q); // 实现部分 int main() { Queue q; QueueInit(q); printf(入队 10, 20, 30\n); QueuePush(q, 10); QueuePush(q, 20); QueuePush(q, 30); printf(队头: %d, 队尾: %d, 大小: %d\n, QueueFront(q), QueueBack(q), QueueSize(q)); // 队头: 10, 队尾: 30, 大小: 3 printf(出队\n); QueuePop(q); printf(队头: %d, 队尾: %d, 大小: %d\n, QueueFront(q), QueueBack(q), QueueSize(q)); // 队头: 20, 队尾: 30, 大小: 2 printf(再入队 40, 50\n); QueuePush(q, 40); QueuePush(q, 50); printf(当前队列: ); while (!QueueEmpty(q)) { printf(%d , QueueFront(q)); QueuePop(q); } printf(\n); printf(队列空: %s\n, QueueEmpty(q) ? 是 : 否); // 队列空: 是 QueueDestroy(q); return 0; }循环队列扩展了解一下实际中我们有时还会使用一种队列叫循环队列。Linux中的生产者消费者模型就会使用循环队列。环形队列可以使用数组实现也可以使用循环链表实现。为什么需要循环队列普通队列顺序存储如果用数组实现入队时rear后移出队时front后移。但经过多次出队后数组前面会出现无法再利用的空闲位置造成“假溢出”——数组还有空位但rear已经指向末尾无法再入队。循环队列将数组的首尾逻辑上连接起来当rear到达数组末尾时下一步就回到开头从而复用空闲空间。循环队列的结构数组实现一个固定大小的数组data[0..k-1]两个整型下标front指向队头元素的位置rear指向队尾元素的下一个位置或指向队尾元素具体取决于实现初始状态front rear 0队列为空常用约定入队将元素放入rear位置rear (rear 1) % capacity出队取出front位置元素front (front 1) % capacity区分队空和队满若使用front rear表示空那么满时也会出现front rear因为绕一圈回来了造成冲突。解决方法二选一方法一牺牲一个存储单元约定当(rear 1) % capacity front时认为队列已满。此时数组中还有一个空位但不使用用于区分空和满。队列中最多存放capacity - 1个元素。方法二增加一个size变量在结构体中增加一个int size入队时size出队时size--。判断空size 0判断满size capacity。优点不浪费空间缺点多维护一个变量。循环队列的基本操作以牺牲一个单元的方法为例数据结构定义typedef struct { int* data; // 动态数组 int front; // 队头下标指向队头元素 int rear; // 队尾下标指向队尾元素的下一个位置 int capacity; // 数组总长度实际容量 capacity - 1 } CircularQueue;1. 初始化循环队列解释创建一个大小为k的循环队列用户期望最多存放k个元素。为了区分空和满实际数组长度需要k1。动态分配数组空间将front和rear均初始化为 0。void cqInit(CircularQueue* q, int k) { // 分配 k1 个整型空间多一个用于判满 q-data (int*)malloc(sizeof(int) * (k 1)); // 初始时队头和队尾重合队列为空 q-front 0; q-rear 0; // 记录数组总长度 q-capacity k 1; }2. 判断队列是否为空解释当front rear时队列中没有元素。int cqIsEmpty(CircularQueue* q) { // 队头与队尾重合表示空队列 return q-front q-rear; }3. 判断队列是否已满解释当(rear 1) % capacity front时队列已满。此时如果再入队会覆盖未出队的元素因此不允许入队。int cqIsFull(CircularQueue* q) { // 队尾的下一个位置是队头则队列已满牺牲一个单元 return (q-rear 1) % q-capacity q-front; }4. 入队解释若队列已满则操作失败。否则将元素放入data[rear]位置然后rear后移一位取模。int cqEnQueue(CircularQueue* q, int value) { // 先检查队列是否已满 if (cqIsFull(q)) return -1; // 入队失败 // 将新元素放到当前 rear 位置 q-data[q-rear] value; // rear 后移一位如果到末尾则绕回开头取模 q-rear (q-rear 1) % q-capacity; return 0; // 入队成功 }5. 出队解释若队列为空则操作失败。否则取出data[front]的值通过输出参数返回然后front后移一位取模。int cqDeQueue(CircularQueue* q, int* out) { // 先检查队列是否为空 if (cqIsEmpty(q)) return -1; // 出队失败 // 取出队头元素 *out q-data[q-front]; // front 后移一位取模实现环形 q-front (q-front 1) % q-capacity; return 0; // 出队成功 }6. 获取队头元素解释只读取队头元素的值不出队。需保证队列非空。int cqFront(CircularQueue* q, int* out) { // 队列为空则无法获取 if (cqIsEmpty(q)) return -1; // 将队头元素通过输出参数返回 *out q-data[q-front]; return 0; }7. 获取队尾元素解释队尾元素位于rear的前一个位置因为rear指向下一个空位。需要处理rear为 0 时的回绕情况。int cqRear(CircularQueue* q, int* out) { // 队列为空则无法获取 if (cqIsEmpty(q)) return -1; // 计算队尾下标 (rear - 1 capacity) % capacity int tailIndex (q-rear - 1 q-capacity) % q-capacity; *out q-data[tailIndex]; return 0; }8. 获取队列中元素个数解释由于队列是环形的元素个数计算公式为(rear - front capacity) % capacity。int cqSize(CircularQueue* q) { // 环形队列长度计算公式 return (q-rear - q-front q-capacity) % q-capacity; }9. 销毁队列解释释放动态数组内存并将指针置空相关变量归零防止内存泄漏。void cqDestroy(CircularQueue* q) { // 释放数组内存 free(q-data); // 将指针置空避免野指针 q-data NULL; // 重置其他成员 q-front 0; q-rear 0; q-capacity 0; }代码总#include stdio.h #include stdlib.h // 循环队列结构定义牺牲一个单元判满 typedef struct { int* data; // 动态数组 int front; // 队头下标指向队头元素 int rear; // 队尾下标指向队尾元素的下一个位置 int capacity; // 数组总长度实际有效容量 capacity - 1 } CircularQueue; // 初始化循环队列 void cqInit(CircularQueue* q, int k) { // 分配 k1 个空间留一个用于判满 q-data (int*)malloc(sizeof(int) * (k 1)); q-front 0; q-rear 0; q-capacity k 1; } // 判断队列是否为空 int cqIsEmpty(CircularQueue* q) { return q-front q-rear; } // 判断队列是否已满 int cqIsFull(CircularQueue* q) { return (q-rear 1) % q-capacity q-front; } // 入队 int cqEnQueue(CircularQueue* q, int value) { if (cqIsFull(q)) { return -1; // 队列已满入队失败 } q-data[q-rear] value; q-rear (q-rear 1) % q-capacity; return 0; } // 出队 int cqDeQueue(CircularQueue* q, int* out) { if (cqIsEmpty(q)) { return -1; // 队列为空出队失败 } *out q-data[q-front]; q-front (q-front 1) % q-capacity; return 0; } // 获取队头元素不出队 int cqFront(CircularQueue* q, int* out) { if (cqIsEmpty(q)) { return -1; } *out q-data[q-front]; return 0; } // 获取队尾元素不删除 int cqRear(CircularQueue* q, int* out) { if (cqIsEmpty(q)) { return -1; } // 队尾元素在 rear 的前一个位置处理绕回 int tailIndex (q-rear - 1 q-capacity) % q-capacity; *out q-data[tailIndex]; return 0; } // 返回队列中实际元素个数 int cqSize(CircularQueue* q) { return (q-rear - q-front q-capacity) % q-capacity; } // 销毁队列释放内存 void cqDestroy(CircularQueue* q) { free(q-data); q-data NULL; q-front q-rear q-capacity 0; } // 测试入口 int main() { CircularQueue q; cqInit(q, 3); // 最多存放 3 个元素 printf(入队 1, 2, 3\n); cqEnQueue(q, 1); cqEnQueue(q, 2); cqEnQueue(q, 3); int val; cqFront(q, val); printf(队头: %d, 队尾: %d, 大小: %d\n, val, (cqRear(q, val), val), cqSize(q)); // 队头: 1, 队尾: 3, 大小: 3 printf(再入队 4应失败\n); int ret cqEnQueue(q, 4); printf(入队结果: %d\n, ret); // 入队结果: -1 printf(出队\n); cqDeQueue(q, val); printf(出队元素: %d\n, val); // 出队元素: 1 cqFront(q, val); printf(新队头: %d, 大小: %d\n, val, cqSize(q)); // 新队头: 2, 大小: 2 printf(再入队 4\n); cqEnQueue(q, 4); cqRear(q, val); printf(队尾: %d, 大小: %d\n, val, cqSize(q)); // 队尾: 4, 大小: 3 printf(队列元素依次出队: ); while (!cqIsEmpty(q)) { cqDeQueue(q, val); printf(%d , val); } printf(\n); // 输出: 2 3 4 cqDestroy(q); return 0; }栈和队列面试题1. 括号匹配问题。20. 有效的括号 - 力扣LeetCode2. 用队列实现栈。225. 用队列实现栈 - 力扣LeetCode3. 用栈实现队列。232. 用栈实现队列 - 力扣LeetCode4. 设计循环队列。622. 设计循环队列 - 力扣LeetCode概念选择题1.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈然后再依次出栈则元素出栈的顺序是。A 12345ABCDEB EDCBA54321C ABCDE12345D 54321EDCBA2.若进栈序列为 1,2,3,4进栈过程中可以出栈则下列不可能的一个出栈序列是。A 1,4,3,2B 2,3,4,1C 3,1,4,2D 3,4,2,13.循环队列的存储空间为 Q(1:100)初始状态为 frontrear100。经过一系列正常的入队与退队操作后frontrear99则循环队列中的元素个数为。A 1B 2C 99D 0 或者 1004.以下不是队列的基本运算A 从队尾插入一个新元素B 从队列中删除第1个元素C 判断一个队列是否为空D 读取队头元素的值5.现有一循环队列其队头指针为 front队尾指针为 rear循环队列长度为 N。其队内有效长度为假设队头不存放数据A (rear - front N) % N 1B (rear - front N) % NC (rear - front) % (N 1)D (rear - front N) % (N - 1)