目录
栈
栈的概念及结构
栈的实现
接口
动态栈（支持扩容）的结构定义
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. 销毁队列
代码总
栈和队列面试题
概念选择题
栈
栈的概念及结构
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端 称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last 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个元素）。为了区分空和满，实际数组长度需要k+1。
动态分配数组空间，将front和rear均初始化为 0。
void cqInit(CircularQueue* q, int k) { // 分配 k+1 个整型空间（多一个用于判满） 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) { // 分配 k+1 个空间，留一个用于判满 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. 有效的括号 - 力扣（LeetCode）
2. 用队列实现栈。225. 用队列实现栈 - 力扣（LeetCode）
3. 用栈实现队列。232. 用栈实现队列 - 力扣（LeetCode）
4. 设计循环队列。622. 设计循环队列 - 力扣（LeetCode）
概念选择题
1.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是（ ）。
A 12345ABCDE
B EDCBA54321
C ABCDE12345
D 54321EDCBA
2.若进栈序列为 1,2,3,4，进栈过程中可以出栈，则下列不可能的一个出栈序列是（ ）。
A 1,4,3,2
B 2,3,4,1
C 3,1,4,2
D 3,4,2,1
3.循环队列的存储空间为 Q(1:100)，初始状态为 front=rear=100。经过一系列正常的入队与退队操作后，front=rear=99，则循环队列中的元素个数为（ ）。
A 1
B 2
C 99
D 0 或者 100
4.以下（ ）不是队列的基本运算？
A 从队尾插入一个新元素
B 从队列中删除第1个元素
C 判断一个队列是否为空
D 读取队头元素的值
5.现有一循环队列，其队头指针为 front，队尾指针为 rear；循环队列长度为 N。其队内有效长度为？（假设队头不存放数据）
A (rear - front + N) % N + 1
B (rear - front + N) % N
C (rear - front) % (N + 1)
D (rear - front + N) % (N - 1)
