网硕互联帮助中心LeetCode 算 法 实 战 – – – 有 效 的 括 号、用 队 列 实 现 栈、用 栈 实 现 队 列 和 设 计 循 环 队 列
- 第 一 题 – – – 有 效 的 括 号
-
- 栈
- 第 二 题 – – – 用 队 列 实 现 栈
-
- 两 个 队 列
- 第 三 题 – – – 用 栈 实 现 队 列
-
- 两 个 栈
- 第 四 题 – – – 设 计 循 环 队 列
-
- 循 环 队 列
- 总 结
💻作 者 简 介：曾 与 你 一 样 迷 茫，现 以 经 验 助 你 入 门 数据 结 构。 💡个 人 主 页：@笑口常开xpr 的 个 人 主 页 📚系 列 专 栏：硬 核 数 据 结 构 与 算 法 ✨代 码 趣 语：在 小 程 序 可 以 完 成 任 务 的 情 况 下，我 们 就 没 必 要 编 写 大 程 序。 💪代 码 千 行，始 于 坚 持，每 日 敲 码，进 阶 编 程 之 路。 📦gitee 链 接：gitee
在 数 据 结 构 的 世 界 里，每 一 种 设 计 都 可 能 孕 育 出 惊 人 的 效 率 变 革。你 是 否 深 思 过，一 组 精 心 组 织 的 数 据 究 竟 能 创 造 怎 样 的 奇 迹？每 一 次 挖 掘 底 层 原 理，都 是 与 计 算 机 智 慧 的 巅 峰 对 话；每 一 次 剖 析 存 储 模 式，都 在 破 解 数 据 世 界 的 终 极 密 码。准 备 好 迎 接 这 场 盛 宴 了 吗？让 我 们 一 同 探 寻 栈 和 队 列 的 无 尽 奥 秘，见 证 它 如 何 重 塑 数 字 时 代 的 运 行 法 则！
第 一 题 – – – 有 效 的 括 号
有 效 的 括 号
描 述 ：给 定 一 个 只 包 括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的 字 符 串 s，判 断 字 符 串 是 否 有 效。
有 效 字 符 串 需 满 足：
左 括 号 必 须 用 相 同 类 型 的 右 括 号 闭 合。 左 括 号 必 须 以 正 确 的 顺 序 闭 合。 每 个 右 括 号 都 有 一 个 对 应 的 相 同 类 型 的 左 括 号。
示 例 1： 输 入：s = “()” 输 出：true
示 例 2： 输 入：s = “()[]{}” 输 出：true
示 例 3： 输 入：s = “(]” 输 出：false
示 例 4： 输 入：s = “([])” 输 出：true
提 示： 1 <= s.length <= 104 s 仅 由 括 号 ‘()[]{}’ 组 成
栈
思 路 分 析 遇 到 左 括 号：直 接 入 栈。
遇 到 右 括 号： 若 栈 为 空，说 明 右 括 号 没 有 对 应 的 左 括 号，匹 配 失 败。 若 栈 顶 元 素 与 当 前 右 括 号 不 匹 配（如 ] 对 应 [ ），匹 配 失 败。 若 匹 配 成 功，则 弹 出 栈 顶 元 素。
遍 历 结 束 后：若 栈 为 空，说 明 所 有 括 号 都 匹 配 成 功；否 则 匹 配 失 败。
温 馨 提 示：读 者 们 ，先 自 己 写 代 码，这 是 提 升 编 程 能 力 的 好 机 会。若 未 达 要 求 ，别 气 馁 ，参 考 下 文 解 释 会 有 新 收 获。
下 面 展 示代 码 示 例。
typedef char STDataType;
typedef struct Stack {
STDataType* a;
int top;
int capacity; // 容量
} ST;
// 初始化
void STInit(ST* ps);
void STDestroy(ST* ps);
// 只能在一端插入,即栈顶
void STPush(ST* ps, STDataType x);
void STPop(ST* ps);
int STSize(ST* ps);
bool STEmpty(ST* ps);
// 访问栈顶元素
STDataType STTop(ST* ps);
void STInit(ST* ps) {
assert(ps);
ps–>a = (STDataType*)malloc(sizeof(STDataType) * 4);
if (ps–>a == NULL) {
perror("ps->a");
return;
}
ps–>capacity = 4;
ps–>top = 0; // top是栈顶元素的下一个位置
// ps->top = -1; //top是栈顶元素
}
void STDestroy(ST* ps) {
assert(ps);
free(ps–>a);
ps–>a = NULL;
ps–>top = 0;
ps–>capacity = 0;
}
void STPush(ST* ps, STDataType x) {
assert(ps);
if (ps–>top == ps–>capacity) {
STDataType* tmp =
(STDataType*)realloc(ps–>a, sizeof(STDataType) * ps–>capacity * 2);
if (tmp == NULL) {
perror("realloc fail");
return;
}
ps–>a = tmp;
ps–>capacity *= 2;
}
ps–>a[ps–>top] = x;
ps–>top++;
}
void STPop(ST* ps) {
assert(ps);
assert(!STEmpty(ps));
ps–>top—;
}
int STSize(ST* ps) {
assert(ps);
return ps–>top;
}
bool STEmpty(ST* ps) {
assert(ps);
return ps–>top == 0;
}
STDataType STTop(ST* ps) {
assert(ps);
assert(!STEmpty(ps));
return ps–>a[ps–>top – 1];
}
bool isValid(char* s) {
ST st;
STInit(&st);
while(*s)
{
if(*s=='('||*s=='['||*s=='{')
{
//入栈
STPush(&st,*s);
}
else
{
//出栈
if(STEmpty(&st))
{
STDestroy(&st);
return false;
}
char top = STTop(&st);
STPop(&st);
if((*s==')'&&top!='(')
||(*s==']'&&top!='[')
||(*s=='}'&&top!='{'))
{
STDestroy(&st);
return false;
}
}
s++;
}
bool ret = STEmpty(&st);
STDestroy(&st);
return ret;
}
代 码 分 析
1、栈 的 实 现 创 建 栈：使 用 动 态 数 组 实 现 栈，包 含 指 针 a、栈 顶 索 引 top 和 容 量 capacity。 初 始 化：分 配 初 始 容 量（4），top 初 始 化 为 0（表 示 栈 顶 的 下 一 个 位 置）。 入 栈（Push）：检 查 是 否 需 要 扩 容，然 后 将 元 素 添 加 到 栈 顶。 出 栈（Pop）：直 接 减 小 top 索 引，不 实 际 删 除 元 素。 获 取 栈 顶 元 素（Top）：返 回 a[top-1]。 销 毁 栈：释 放 动 态 数 组 内 存，重 置 参 数。
2、括 号 匹 配 遍 历 字 符 串： 若 为 左 括 号（(, [, {），入 栈。 若 为 右 括 号： 若 栈 为 空，返 回 false。 弹 出 栈 顶 元 素，检 查 是 否 与 当 前 右 括 号 匹 配。若 不 匹 配 ，返 回 false。 结 束 条 件 遍 历 完 成 后，若 栈 为 空，返 回 true；否 则 返 回 false。
复 杂 度 分 析 时 间 复 杂 度：O(n)，其 中 n 是 字 符 串 长 度。每 个 字 符 仅 遍 历 一 次，栈 操 作 的 时 间 复 杂 度 为 O(1)。 空 间 复 杂 度：O(n)，最 坏 情 况 下 所 有 左 括 号 入 栈，栈 的 深 度 为 n。
第 二 题 – – – 用 队 列 实 现 栈
用 队 列 实 现 栈
描 述 请 你 仅 使 用 两 个 队 列 实 现 一 个 后 入 先 出（LIFO）的 栈，并 支 持 普 通 栈 的 全 部 四 种 操 作（push、top、pop 和 empty）。
实 现 MyStack 类： void push(int x) 将 元 素 x 压 入 栈 顶。 int pop() 移 除 并 返 回 栈 顶 元 素。 int top() 返 回 栈 顶 元 素。 boolean empty() 如 果 栈 是 空 的，返 回 true；否 则，返 回 false。
注 意： 你 只 能 使 用 队 列 的 标 准 操 作 —— 也 就 是 push to back、peek/pop from front、size 和 is empty 这 些 操 作。 你 所 使 用 的 语 言 也 许 不 支 持 队 列。你 可 以 使 用 list （列 表）或 者 deque（双 端 队 列）来 模 拟 一 个 队 列，只 要 是 标 准 的 队 列 操 作 即 可。
示 例： 输 入： [“MyStack”, “push”, “push”, “top”, “pop”, “empty”] [[], [1], [2], [], [], []] 输 出： [null, null, null, 2, 2, false] 解 释： MyStack myStack = new MyStack(); myStack.push(1); myStack.push(2); myStack.top(); //返 回 2 myStack.pop(); //返 回 2 myStack.empty(); //返 回 False
提 示： 1 <= x <= 9 最 多 调 用 100 次 push、pop、top 和 empty 每 次 调 用 pop 和 top 都 保 证 栈 不 为 空
两 个 队 列
思 路 分 析 1、核 心 设 计 思 路 使 用 两 个 队 列 模 拟 栈 的 关 键 在 于 出 栈 操 作 入 栈：直 接 将 元 素 添 加 到 非 空 队 列。 出 栈：将 非 空 队 列 的 前 n – 1 个 元 素 转 移 到 另 一 个 空 队 列。弹 出 原 非 空 队 列 的 最 后 一 个 元 素（即 栈 顶）。时 间 复 杂 度 O(n)，其 中 n 是 栈 的 大 小。
2、为 什 么 需 要 两 个 队 列？ 栈 的 核 心 是 后 进 先 出，而 队 列 是 先 进 先 出。假 设 仅 用 一 个 队 列，无 法 直 接 访 问 队 尾 元 素（栈 顶）。通 过 两 个 队 列 的 交 替 使 用，可 以 在 出 栈 时 将 前 n – 1 个 元 素 暂 存 到 另 一 个 队 列，从 而 暴 露 栈 顶 元 素。
3、状 态 转 移 示 例 假 设 栈 中 已 有 元 素 [1, 2, 3]（栈 顶 为 3），存 储 在 q1 中： q1: [1, 2, 3] q2: [ ] 出 栈 操 作：将 q1 的 前 两 个 元 素（1, 2）转 移 到 q2： q1: [3] q2: [1, 2] 弹 出 q1 的 最 后 一 个 元 素 3，得 到 栈 顶。此 时 q2 成 为 非 空 队 列，用 于 后 续 操 作。
温 馨 提 示：读 者 们 ，先 自 己 写 代 码，这 是 提 升 编 程 能 力 的 好 机 会。若 未 达 要 求 ，别 气 馁 ，参 考 下 文 解 释 会 有 新 收 获。
下 面 展 示代 码 示 例。
typedef int QDataType;
typedef struct QueueNode {
struct QueueNode* next;
QDataType data;
} QNode;
typedef struct Queue {
QNode* head;
QNode* tail;
int size;
} Queue;
// 初始化队列
void QueueInit(Queue* pq);
// 销毁队列
void QueueDestory(Queue* pq);
// 队尾入队列
void QueuePush(Queue* pq, QDataType x);
// 队头出队列
void QueuePop(Queue* pq);
// 获取队列中有效元素个数
int QueueSize(Queue* pq);
// 检查队列是否为空
bool QueueEmpty(Queue* pq);
// 取出队头的数据
QDataType QueueFront(Queue* pq);
// 取出队尾的数据
QDataType QueueBack(Queue* pq);
void QueueInit(Queue* pq) {
assert(pq);
pq–>head = pq–>tail = NULL;
pq–>size = 0;
}
void QueueDestory(Queue* pq) {
assert(pq);
QNode* cur = pq–>head;
while (cur) {
QNode* next = cur–>next;
free(cur);
cur = next;
}
pq–>head = pq–>tail = NULL;
pq–>size = 0;
}
void QueuePush(Queue* pq, QDataType x) {
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL) {
perror("newnode");
return;
}
newnode–>data = x;
newnode–>next = NULL;
if (pq–>head == NULL) {
assert(pq–>tail == NULL);
pq–>head = pq–>tail = newnode;
} else {
pq–>tail–>next = newnode;
pq–>tail = newnode;
}
pq–>size++;
}
void QueuePop(Queue* pq) {
assert(pq);
assert(pq–>head != NULL);
// 方法1
// QNode* next = pq->head->next;
// free(pq->head);
// pq->head = next;
// if (pq->head == NULL)
//{
//pq->tail = NULL;
// }
// 方法2
if (pq–>head–>next == NULL) {
free(pq–>head);
pq–>tail = pq–>head = NULL;
} else {
QNode* next = pq–>head–>next;
free(pq–>head);
pq–>head = next;
}
pq–>size—;
}
int QueueSize(Queue* pq) {
assert(pq);
return pq–>size;
}
bool QueueEmpty(Queue* pq) {
assert(pq);
// return pq->size == 0;
return pq–>head == NULL && pq–>tail == NULL;
}
QDataType QueueFront(Queue* pq) {
assert(pq);
assert(!QueueEmpty(pq));
return pq–>head–>data;
}
QDataType QueueBack(Queue* pq) {
assert(pq);
assert(!QueueEmpty(pq));
return pq–>tail–>data;
}
typedef struct {
Queue q1;
Queue q2;
} MyStack;
MyStack* myStackCreate() {
MyStack* tmp = (MyStack*)malloc(sizeof(MyStack));
if (tmp == NULL) {
perror("malloc fail");
return NULL;
}
QueueInit(&tmp–>q1);
QueueInit(&tmp–>q2);
return tmp;
}
void myStackPush(MyStack* obj, int x) {
if (!QueueEmpty(&obj–>q1)) {
QueuePush(&obj–>q1, x);
} else {
QueuePush(&obj–>q2, x);
}
}
int myStackPop(MyStack* obj) {
Queue* emptyQ = &obj–>q1; // 假定q1为空,q2不为空
Queue* nonemptyQ = &obj–>q2;
if (!QueueEmpty(&obj–>q1)) {
emptyQ = &obj–>q2;
nonemptyQ = &obj–>q1;
}
while (QueueSize(nonemptyQ) > 1) {
QueuePush(emptyQ, QueueFront(nonemptyQ));
QueuePop(nonemptyQ);
}
int top = QueueFront(nonemptyQ);
QueuePop(nonemptyQ);
return top;
}
int myStackTop(MyStack* obj) {
if (!QueueEmpty(&obj–>q1)) {
return QueueBack(&obj–>q1);
} else {
return QueueBack(&obj–>q2);
}
}
bool myStackEmpty(MyStack* obj) {
return QueueEmpty(&obj–>q1) && QueueEmpty(&obj–>q2);
}
void myStackFree(MyStack* obj) {
QueueDestory(&obj–>q1);
QueueDestory(&obj–>q2);
free(obj);
}
/**
* Your MyStack struct will be instantiated and called as such:
* MyStack* obj = myStackCreate();
* myStackPush(obj, x);
* int param_2 = myStackPop(obj);
* int param_3 = myStackTop(obj);
* bool param_4 = myStackEmpty(obj);
* myStackFree(obj);
*/
代 码 分 析 1、队 列 的 实 现 队 列 采 用 链 表 结 构，包 含 头 指 针（head）、尾 指 针（tail） 和 大 小 计 数 器（size）： 初 始 化：QueueInit 将 头 尾 指 针 置 为 NULL，size 置 为 0。 入 队：QueuePush 创 建 新 节 点，若 队 列 为 空 则 同 时 更 新 头 尾 指 针；否 则 仅 更 新 尾 指 针。 出 队：QueuePop 删 除 头 节 点，若 队 列 仅 有 一 个 元 素 则 同 时 置 空 头 尾 指 针。 辅 助 操 作：QueueSize、QueueEmpty、QueueFront、QueueBack 提 供 状 态 查 询。
2、栈 的 实 现（使 用 两 个 队 列） 栈 的 核 心 是 后 进 先 出，而 队 列 是 先 进 先 出。为 模 拟 栈 的 行 为，使 用 两 个 队 列 q1 和 q2： 初 始 化：myStackCreate 分 配 内 存 并 初 始 化 两 个 队 列。 入 栈：myStackPush 将 元 素 添 加 到 非 空 队 列（若 都 为 空 则 默 认 选 q1）。 出 栈：myStackPop 将 非 空 队 列 的 前 n – 1 个 元 素 转 移 到 空 队 列，最 后 弹 出 剩 余 的 队 尾 元 素（即 栈 顶）。 获 取 栈 顶：myStackTop 直 接 返 回 非 空 队 列 的 队 尾 元 素。 判 空 与 释 放：myStackEmpty 检 查 两 个 队 列 是 否 都 为 空，myStackFree 释 放 队 列 内 存。
复 杂 度 分 析 入 栈（Push）：O(1)，直 接 添 加 到 队 列 尾 部。 出 栈（Pop）：O(n)，需 转 移 n – 1 个 元 素。 获 取 栈 顶（Top）：O(1)，直 接 访 问 队 列 尾 部。 空 间 复 杂 度：O(n)，存 储 所 有 元 素。
第 三 题 – – – 用 栈 实 现 队 列
用 栈 实 现 队 列
描 述：请 你 仅 使 用 两 个 栈 实 现 先 入 先 出 队 列。队 列 应 当 支 持 一 般 队 列支 持 的 所 有 操 作（push、pop、peek、empty）：
实 现 MyQueue 类： void push(int x) ：将 元 素 x 推 到 队 列 的 末 尾。 int pop()：从 队 列 的 开 头 移 除 并 返 回 元 素。 int peek()：返 回 队 列 开 头 的 元 素。 boolean empty()：如 果 队 列 为 空，返 回 true；否 则，返 回 false
说 明： 你 只 能 使 用 标 准 的 栈 操 作 —— 也 就 是 只 有 push to top, peek/pop from top, size, 和 is empty 操 作 是 合 法 的。 你 所 使 用 的 语 言 也 许 不 支 持 栈。你 可 以 使 用 list 或 者 deque（双 端 队 列）来 模 拟 一 个 栈，只 要 是 标 准 的 栈 操 作 即 可。
示 例 1： 输 入： [“MyQueue”, “push”, “push”, “peek”, “pop”, “empty”] [[], [1], [2], [], [], []] 输 出： [null, null, null, 1, 1, false] 解 释： MyQueue myQueue = new MyQueue(); myQueue.push(1); // queue is: [1] myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue) myQueue.peek(); // return 1 myQueue.pop(); // return 1, queue is [2] myQueue.empty(); // return false
提 示： 1 <= x <= 9 最 多 调 用 100 次 push、pop、peek 和 empty 假 设 所 有 操 作 都 是 有 效 的（例 如，一 个 空 的 队 列 不 会 调 用 pop 或 者 peek 操 作）
两 个 栈
思 路 分 析 1、核 心 设 计 思 想 队 列 的 特 点 是 先 进 先 出，而 栈 是 后 进 先 出。为 了 用 两 个 栈 模 拟 队 列，需 要： 入 队（Push）：元 素 直 接 压 入 pushst 栈。 出 队（Pop）：从 popst 栈 弹 出 元 素。若 popst 为 空，则 将 pushst 的 所 有 元 素 倒 序 压 入 popst，再 弹 出 栈 顶。
2、双 栈 的 协 同 工 作 方 式 pushst：专 门 用 于 入 队 操 作，新 元 素 始 终 压 入 此 栈。popst：专 门 用 于 出 队 操 作，若 为 空 则 从 pushst 导 入 所 有 元 素（此 时 元 素 顺 序 被 反 转，符 合 队 列 的 FIFO 特性）。
3、关 键 操 作 步 骤 入 队（Push）：时 间 复 杂 度 O(1)，直 接 压 栈。 出 队（Pop）： 若 popst 非 空，直 接 弹 出 栈 顶。 若 popst 为 空，将 pushst 的 所 有 元 素 倒 入 popst，再 弹 出。平 均 时 间 复 杂 度 O(1)（每 个 元 素 最 多 被 倒 腾 两 次）。 获 取 队 头 （Peek）：与 Pop 逻 辑 相 同，但 不 弹 出 元 素。
温 馨 提 示：读 者 们 ，先 自 己 写 代 码，这 是 提 升 编 程 能 力 的 好 机 会。若 未 达 要 求 ，别 气 馁 ，参 考 下 文 解 释 会 有 新 收 获。
下 面 展 示代 码 示 例。
typedef int STDataType;
typedef struct Stack {
STDataType* a;
int top;
int capacity; // 容量
} ST;
// 初始化
void STInit(ST* ps);
void STDestroy(ST* ps);
// 只能在一端插入,即栈顶
void STPush(ST* ps, STDataType x);
void STPop(ST* ps);
int STSize(ST* ps);
bool STEmpty(ST* ps);
// 访问栈顶元素
STDataType STTop(ST* ps);
void STInit(ST* ps) {
assert(ps);
ps–>a = (STDataType*)malloc(sizeof(STDataType) * 4);
if (ps–>a == NULL) {
perror("ps->a");
return;
}
ps–>capacity = 4;
ps–>top = 0; // top是栈顶元素的下一个位置
// ps->top = -1; //top是栈顶元素
}
void STDestroy(ST* ps) {
assert(ps);
free(ps–>a);
ps–>a = NULL;
ps–>top = 0;
ps–>capacity = 0;
}
void STPush(ST* ps, STDataType x) {
assert(ps);
if (ps–>top == ps–>capacity) {
STDataType* tmp =
(STDataType*)realloc(ps–>a, sizeof(STDataType) * ps–>capacity * 2);
if (tmp == NULL) {
perror("realloc fail");
return;
}
ps–>a = tmp;
ps–>capacity *= 2;
}
ps–>a[ps–>top] = x;
ps–>top++;
}
void STPop(ST* ps) {
assert(ps);
assert(!STEmpty(ps));
ps–>top—;
}
int STSize(ST* ps) {
assert(ps);
return ps–>top;
}
bool STEmpty(ST* ps) {
assert(ps);
return ps–>top == 0;
}
STDataType STTop(ST* ps) {
assert(ps);
assert(!STEmpty(ps));
return ps–>a[ps–>top – 1];
}
typedef struct {
ST pushst;
ST popst;
} MyQueue;
MyQueue* myQueueCreate() {
MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
if (obj == NULL) {
perror("malloc fail");
return NULL;
}
STInit(&obj–>pushst);
STInit(&obj–>popst);
return obj;
}
void myQueuePush(MyQueue* obj, int x) { STPush(&obj–>pushst, x); }
int myQueuePeek(MyQueue* obj) {
if (STEmpty(&obj–>popst)) {
// 倒数据
while (!STEmpty(&obj–>pushst)) {
STPush(&obj–>popst, STTop(&obj–>pushst));
STPop(&obj–>pushst);
}
}
return STTop(&obj–>popst);
}
int myQueuePop(MyQueue* obj) {
int front = myQueuePeek(obj);
STPop(&obj–>popst);
return front;
}
bool myQueueEmpty(MyQueue* obj) {
return STEmpty(&obj–>popst) && STEmpty(&obj–>pushst);
}
void myQueueFree(MyQueue* obj) {
STDestroy(&obj–>pushst);
STDestroy(&obj–>popst);
free(obj);
}
/**
* Your MyQueue struct will be instantiated and called as such:
* MyQueue* obj = myQueueCreate();
* myQueuePush(obj, x);
* int param_2 = myQueuePop(obj);
* int param_3 = myQueuePeek(obj);
* bool param_4 = myQueueEmpty(obj);
* myQueueFree(obj);
*/
代 码 分 析 1、栈 的 实 现 栈 采 用 动 态 数 组 实 现，包 含 指 针 a、栈 顶 索 引 top 和 容 量 capacity： 初 始 化：分 配 初 始 容 量（4），top 初 始 化 为 0（表 示 栈 顶 的 下 一 个 位 置）。 入 栈（Push）：检 查 容 量，必 要 时 扩 容（倍 增 策 略）。 出 栈（Pop）：直 接 减 小 top 索 引。 获 取 栈 顶（Top）：返 回 a[top-1]。 2、队 列 的 实 现 队 列 结 构 包 含 两 个 栈 pushst 和 popst： 创 建 与 销 毁 入 队（Push）：直 接 压 入 pushst。 出 队（Pop）：复 用 myQueuePeek 获 取 队 头，再 弹 出。 获 取 队 头（Peek）：若 popst 为 空，则 将 pushst 元 素 倒 入 popst。 判 空：两 个 栈 都 为 空 时 队 列 为 空。
复 杂 度 分 析 时 间 复 杂 度 入 队（Push）：O(1) 出 队（Pop）/ 获 取 队 头（Peek）：平 均 O(1)（每 个 元 素 最 多 被 倒 入 popst 一 次） 空 间 复 杂 度 O(n)，存 储 所 有 元 素。
第 四 题 – – – 设 计 循 环 队 列
设 计 循 环 队 列
描 述：设 计 你 的 循 环 队 列 实 现。循 环 队 列 是 一 种 线 性 数 据 结 构，其 操 作 表 现 基 于 FIFO（先 进 先 出）原 则 并 且 队 尾 被 连 接 在 队 首 之 后 以 形 成 一 个 循 环。它 也 被 称 为 “ 环 形 缓 冲 器”。
循 环 队 列 的 一 个 好 处 是 我 们 可 以 利 用 这 个 队 列 之 前 用 过 的 空 间。在 一 个 普 通 队 列 里，一 旦 一 个 队 列 满 了，我 们 就 不 能 插 入 下 一 个 元 素，即 使 在 队 列 前 面 仍 有 空 间。但 是 使 用 循 环 队 列，我 们 能 使用 这 些 空 间 去 存 储 新 的 值。
你 的 实 现 应 该 支持 如 下 操 作： MyCircularQueue(k): 构 造 器，设 置 队 列 长 度 为 k。 Front: 从 队 首 获 取 元 素。如 果 队 列 为 空，返 回 -1。 Rear: 获 取 队 尾 元 素。如 果 队 列 为 空，返 回 -1。 enQueue(value): 向 循 环 队 列 插 入 一 个 元 素。如 果 成 功插 入 则 返 回 真。 deQueue(): 从 循 环 队 列 中 删 除 一 个 元 素。如 果 成 功 删 除 则 返 回 真。 isEmpty(): 检 查 循 环 队 列 是 否 为 空。 isFull(): 检 查 循 环 队 列 是 否 已 满。
示 例： MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3 circularQueue.enQueue(1); // 返回 true circularQueue.enQueue(2); // 返回 true circularQueue.enQueue(3); // 返回 true circularQueue.enQueue(4); // 返回 false，队列已满 circularQueue.Rear(); // 返回 3 circularQueue.isFull(); // 返回 true circularQueue.deQueue(); // 返回 true circularQueue.enQueue(4); // 返回 true circularQueue.Rear(); // 返回 4
提 示： 所 有 的 值 都 在 0 至 1000 的 范 围 内； 操 作 数 将 在 1 至 1000 的 范 围 内； 请 不 要 使 用 内 置 的 队 列 库。
循 环 队 列
思 路 分 析 1、循 环 队 列 的 核 心 概 念 循 环 队 列 通 过 将 数 组 首 尾 相 连，解 决 了 普 通 队 列 的 “假 溢 出” 问 题（即 数 组 前 端 有 空 位 但 队 尾 已 到 数 组 末 尾 的 情 况）。关 键 在 于： 使 用 固 定 大 小 的 数 组 存 储 元 素 通 过 front 和 rear 指 针 标 记 队 头 和 队 尾 利 用 取 模 运 算 % 实 现 数 组 的 循 环 访 问
2、关 键 设 计 要 点 空 队 列 判 断： front == rear（首 尾 指 针 重 合） 满 队 列 判 断： (rear + 1) % (k + 1) == front（队 尾 下 一 个 位 置 等 于 队 头） 数 组 大 小：申 请 k+1 个 元 素 的 空 间，避 免 空 队 列 和 满 队 列 判 断 条 件 冲 突 指 针 移 动：入 队 时 rear 后 移，出 队 时 front 后 移，均 通 过 取 模 实 现 循 环。
温 馨 提 示：读 者 们 ，先 自 己 写 代 码，这 是 提 升 编 程 能 力 的 好 机 会。若 未 达 要 求 ，别 气 馁 ，参 考 下 文 解 释 会 有 新 收 获。
下 面 展 示代 码 示 例。
typedef struct {
int* a;
int front;
int rear;
int k;
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
obj–>front = obj–>rear = 0;
obj–>a = (int*)malloc(sizeof(int)*(k+1));
obj–>k=k;
return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj–>front == obj–>rear;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
return (obj–>rear+1)%(obj–>k+1)==obj–>front;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if(myCircularQueueIsFull(obj))
{
return false;
}
obj–>a[obj–>rear++]=value;
obj–>rear%=(obj–>k+1);
return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return false;
}
obj–>front++;
obj–>front%=(obj–>k+1);
return true;
}
int myCircularQueueFront(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return –1;
}
else
{
return obj–>a[obj–>front];
}
}
int myCircularQueueRear(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return –1;
}
else
{
int x = obj–>rear==0?obj–>k:obj–>rear–1;
return obj–>a[x];
}
// return obj->a[(obj->rear-1+obj->k+1) % (obj->k+1)];
}
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj–>a);
free(obj);
}
/**
* Your MyCircularQueue struct will be instantiated and called as such:
* MyCircularQueue* obj = myCircularQueueCreate(k);
* bool param_1 = myCircularQueueEnQueue(obj, value);
* bool param_2 = myCircularQueueDeQueue(obj);
* int param_3 = myCircularQueueFront(obj);
* int param_4 = myCircularQueueRear(obj);
* bool param_5 = myCircularQueueIsEmpty(obj);
* bool param_6 = myCircularQueueIsFull(obj);
* myCircularQueueFree(obj);
*/
代 码 分 析 1、数 据 结 构 定 义 **front：**指 向 队 头 元 素 **rear：**指 向 队 尾 元 素 的 下 一 个 位 置 数 组 大 小 为 k+1，其 中 k 是 队 列 的 最 大 容 量 2、初 始 化 函 数 分 配 队 列 结 构 体 和 数 据 数 组 的 内 存。 初 始 化 front 和 rear 为 0。 数 组 大 小 设 为 k+1，防 止 空 满 判 断 冲 突。 3、空 队 列 与 满 队 列 判 断 空 队 列：首 尾 指 针 指 向 同 一 位 置。 满 队 列：队 尾 下 一 个 位 置（取 模 后）等 于 队 头。 4、入 队 操 作 先 检 查 队 列 是 否 已 满。 将 值 存 入 rear 指 向 的 位 置，然 后 rear 后 移。 通 过 取 模 实 现 rear 的 循 环 移 动。 5、出 队 操 作 先 检 查 队 列 是 否 为 空。 front 指 针 后 移，通 过 取 模 实 现 循 环 移 动。 6、获 取 队 头 和 队 尾 元 素 队 头 元 素：直 接 取 front 指 向 的 元 素 队 尾 元 素：需 计 算 rear 前 一 个 位 置，处 理 rear=0 的 边 界 情 况。 7、内 存 释 放 先 释 放 数 据 数 组，再 释 放 队 列 结 构 体
关 键 细 节 解 析
数 组 大 小 为 k+1 的 原 因： 若 数 组 大 小 为 k，空 队 列 和 满 队 列 的 条 件 都 会 是 front == rear，无 法 区 分 预 留 一 个 空 位 后，满 队 列 条 件 变 为 (rear+1)%(k+1) == front，与 空 队 列 条 件 区 分 开。
指 针 移 动 的 取 模 运 算：
obj–>rear %= (obj–>k + 1); // 入队时rear后移
obj–>front %= (obj–>k + 1); // 出队时front后移
当 指 针 到 达 数 组 末 尾 时，取 模 运 算 使 其 回 到 数 组 开 头，实 现 循 环 效 果。
队 尾 元 素 的 计 算：
int x = obj–>rear == 0 ? obj–>k : obj–>rear – 1;
当 rear = 0 时，队 尾 元 素 在 数 组 末 尾（索 引 为 k）。 否 则，队 尾 元 素 在 rear – 1 位 置。
复 杂 度 分 析 时 间 复 杂 度：所 有 操 作 均 为 O(1)，仅 涉 及 简 单 的 指 针 移 动 和 取 模 运 算。 空 间 复 杂 度：O(k)，用 于 存 储 队 列 元 素 的 数 组。
总 结
至 此，关 于 栈 和 队 列 的 探 索 暂 告 一 段 落，但 你 的 编 程 征 程 才 刚 刚 启 航。编 写 代 码 是 与 计 算 机 逻 辑 深 度 对 话，过 程 中 虽 会 在 结 构 设 计、算 法 实 现 的 困 境 里 挣 扎，但 这 些 磨 砺 加 深 了 对 代 码 逻 辑 和 数 据 组 织 的 理 解。愿 你 合 上 电 脑 后，灵 感 不 断，在 数 据 结 构 的 世 界 里 持 续 深 耕，书 写 属 于 自 己 的 编 程 传 奇，下 一 次 开 启，定 有 全 新 的 精 彩 等 待。小 编 期 待 重 逢，盼 下 次 阅 读 时 见 证 你 们 更 大 的 进 步，共 赴 代 码 之 约！
评论前必须登录！
注册