LeetCode 232: 用栈实现队列

LeetCode 232: 用栈实现队列

标题形貌

利用栈实现队列的操纵。支持以下操纵：

• MyQueue()：初始化队列。
  
• push(x)：将元素 x 推入队列。
  
• pop()：从队列中移除元素。
  
• peek()：返回队列头部的元素。
  
• empty()：查抄队列是否为空。
  

队列的先辈先出（FIFO）原则可以通过两个栈来模拟。栈 A 用于入队操纵，栈 B 用于出队操纵。
C 语言实现

1. #include <stdio.h>
2. #include <stdlib.h>
4. // 定义栈结构体
5. typedef struct {
6.     int* data;
7.     int top;
8.     int capacity;
9. } Stack;
11. // 初始化栈
12. Stack* stackCreate(int capacity) {
13.     Stack* stack = (Stack*)malloc(sizeof(Stack));
14.     stack->data = (int*)malloc(sizeof(int) * capacity);
15.     stack->top = -1;
16.     stack->capacity = capacity;
17.     return stack;
18. }
20. // 检查栈是否为空
21. int stackIsEmpty(Stack* stack) {
22.     return stack->top == -1;
23. }
25. // 入栈操作
26. void stackPush(Stack* stack, int x) {
27.     stack->data[++stack->top] = x;
28. }
30. // 出栈操作
31. int stackPop(Stack* stack) {
32.     return stack->data[stack->top--];
33. }
35. // 获取栈顶元素
36. int stackTop(Stack* stack) {
37.     return stack->data[stack->top];
38. }
40. // 释放栈内存
41. void stackFree(Stack* stack) {
42.     free(stack->data);
43.     free(stack);
44. }
46. // 定义队列结构体
47. typedef struct {
48.     Stack* stackA;
49.     Stack* stackB;
50. } MyQueue;
52. // 初始化队列
53. MyQueue* myQueueCreate() {
54.     MyQueue* queue = (MyQueue*)malloc(sizeof(MyQueue));
55.     queue->stackA = stackCreate(100); // 栈 A 的初始容量
56.     queue->stackB = stackCreate(100); // 栈 B 的初始容量
57.     return queue;
58. }
60. // 入队操作
61. void myQueuePush(MyQueue* obj, int x) {
62.     stackPush(obj->stackA, x);  // 将元素推入栈 A
63. }
65. // 出队操作
66. int myQueuePop(MyQueue* obj) {
67.     if (stackIsEmpty(obj->stackB)) {  // 如果栈 B 为空
68.         while (!stackIsEmpty(obj->stackA)) {  // 将栈 A 中的元素全部移到栈 B
69.             stackPush(obj->stackB, stackPop(obj->stackA));
70.         }
71.     }
72.     return stackPop(obj->stackB);  // 从栈 B 出栈
73. }
75. // 获取队列头部元素
76. int myQueuePeek(MyQueue* obj) {
77.     if (stackIsEmpty(obj->stackB)) {  // 如果栈 B 为空
78.         while (!stackIsEmpty(obj->stackA)) {  // 将栈 A 中的元素全部移到栈 B
79.             stackPush(obj->stackB, stackPop(obj->stackA));
80.         }
81.     }
82.     return stackTop(obj->stackB);  // 返回栈 B 顶部元素
83. }
85. // 检查队列是否为空
86. int myQueueEmpty(MyQueue* obj) {
87.     return stackIsEmpty(obj->stackA) && stackIsEmpty(obj->stackB);  // 栈 A 和栈 B 都为空时队列为空
88. }
90. // 释放队列内存
91. void myQueueFree(MyQueue* obj) {
92.     stackFree(obj->stackA);
93.     stackFree(obj->stackB);
94.     free(obj);
95. }
97. // 测试主函数
98. int main() {
99.     MyQueue* queue = myQueueCreate();
100.    
101.     myQueuePush(queue, 1);
102.     myQueuePush(queue, 2);
103.     printf("peek: %d\n", myQueuePeek(queue));  // 应输出 1
104.     printf("pop: %d\n", myQueuePop(queue));   // 应输出 1
105.     printf("empty: %d\n", myQueueEmpty(queue));  // 应输出 0
107.     myQueuePush(queue, 3);
108.     printf("peek: %d\n", myQueuePeek(queue));  // 应输出 2
109.     printf("pop: %d\n", myQueuePop(queue));   // 应输出 2
110.     printf("pop: %d\n", myQueuePop(queue));   // 应输出 3
111.     printf("empty: %d\n", myQueueEmpty(queue));  // 应输出 1
113.     myQueueFree(queue);
114.     return 0;
115. }

复制代码

代码逐行表明

栈的实现

1. typedef struct {
2.     int* data;
3.     int top;
4.     int capacity;
5. } Stack;

复制代码

我们起首界说了一个 Stack 布局体，包罗了三个成员：

• data：存储栈元素的数组。
  
• top：栈顶元素的索引。
  
• capacity：栈的最大容量。
  

1. Stack* stackCreate(int capacity) {
2.     Stack* stack = (Stack*)malloc(sizeof(Stack));
3.     stack->data = (int*)malloc(sizeof(int) * capacity);
4.     stack->top = -1;
5.     stack->capacity = capacity;
6.     return stack;
7. }

复制代码

stackCreate 用来初始化一个栈，分配内存并设置初始值。

1. int stackIsEmpty(Stack* stack) {
2.     return stack->top == -1;
3. }

复制代码

stackIsEmpty 用于查抄栈是否为空，栈空时返回 1。

1. void stackPush(Stack* stack, int x) {
2.     stack->data[++stack->top] = x;
3. }

复制代码

stackPush 用于将元素推入栈中，top 先自增再将元素存入。

1. int stackPop(Stack* stack) {
2.     return stack->data[stack->top--];
3. }

复制代码

stackPop 用于从栈中弹出元素，并返回弹出的元素。

1. int stackTop(Stack* stack) {
2.     return stack->data[stack->top];
3. }

复制代码

stackTop 用于获取栈顶元素，但不删除它。
队列的实现

1. typedef struct {
2.     Stack* stackA;
3.     Stack* stackB;
4. } MyQueue;

复制代码

我们界说了一个 MyQueue 布局体，它包罗两个栈：

• stackA 用于存储入队元素。
  
• stackB 用于存储出队元素。
  

1. MyQueue* myQueueCreate() {
2.     MyQueue* queue = (MyQueue*)malloc(sizeof(MyQueue));
3.     queue->stackA = stackCreate(100);
4.     queue->stackB = stackCreate(100);
5.     return queue;
6. }

复制代码

myQueueCreate 用于创建一个队列并初始化此中的两个栈。

1. void myQueuePush(MyQueue* obj, int x) {
2.     stackPush(obj->stackA, x);  
3. }

复制代码

myQueuePush 将元素压入 stackA。

1. int myQueuePop(MyQueue* obj) {
2.     if (stackIsEmpty(obj->stackB)) {
3.         while (!stackIsEmpty(obj->stackA)) {
4.             stackPush(obj->stackB, stackPop(obj->stackA));
5.         }
6.     }
7.     return stackPop(obj->stackB);
8. }

复制代码

myQueuePop 用于从队列中弹出元素。起首查抄 stackB 是否为空，假如为空，则将 stackA 中的全部元素转移到 stackB 中。然后从 stackB 弹出栈顶元素。

1. int myQueuePeek(MyQueue* obj) {
2.     if (stackIsEmpty(obj->stackB)) {
3.         while (!stackIsEmpty(obj->stackA)) {
4.             stackPush(obj->stackB, stackPop(obj->stackA));
5.         }
6.     }
7.     return stackTop(obj->stackB);
8. }

复制代码

myQueuePeek 用于获取队列头部的元素，逻辑与 myQueuePop 类似，只不外不移除元素。

1. int myQueueEmpty(MyQueue* obj) {
2.     return stackIsEmpty(obj->stackA) && stackIsEmpty(obj->stackB);
3. }

复制代码

myQueueEmpty 查抄队列是否为空，只有当 stackA 和 stackB 都为空时，队列才为空。

1. void myQueueFree(MyQueue* obj) {
2.     stackFree(obj->stackA);
3.     stackFree(obj->stackB);
4.     free(obj);
5. }

复制代码

myQueueFree 用于开释队列及其内部栈的内存。