- 一【题目类别】
- 二【题目难度】
- 三【题目编号】
- 四【题目描述】
- 五【题目示例】
- 六【题目提示】
- 七【题目进阶】
- 八【解题思路】
- 九【时间频度】
- 十【代码实现】
- 十一【提交结果】
- 栈
- 简单
- 225.用队列实现栈
- 请你仅使用两个队列实现一个后入先出(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 都保证栈不为空
- 你能否仅用一个队列来实现栈。
- 这道题看起来不难,但是实现起来比较复杂(尤其是用C语言写)
- 我提供了两个思路,但是都差不太多
- 主要就是其中一个队列作为辅助队列,存放主队列存过来的元素,然后就从先进先出变为先进后出了
- 然后最重要的是每次操作之后都要将主队列和辅助队列交换,这样下一次进行操作才不会出错
- 其余的操作就比较简单了,看代码即可
- 时间复杂度:入栈操作 O ( n ) O(n) O(n),其余操作都是 O ( 1 ) O(1) O(1),其中 n n n 是栈内的元素个数
- 空间复杂度: O ( n ) O(n) O(n),其中 n n n 是栈内的元素个数
- Java语言版
package Stack; import java.util.LinkedList; import java.util.Queue; public class p225_ImplementingStacksWithQueues { Queuequeue1; Queue queue2; public static void main(String[] args) { } public void MyStack() { queue1 = new LinkedList (); queue2 = new LinkedList (); } public void push(int x) { queue2.offer(x); while (!queue1.isEmpty()) { queue2.offer(queue1.poll()); } Queue temp = queue1; queue1 = queue2; queue2 = temp; } public int pop() { return queue1.poll(); } public int top() { return queue1.peek(); } public boolean empty() { return queue1.isEmpty(); } }
- C语言版
#include十一【提交结果】#include #include #define MAXSIZE 101 typedef struct queue { int* data; int front; int rear; }Queue; typedef struct { Queue *queue1; Queue *queue2; } MyStack; MyStack* myStackCreate() { MyStack* obj = (MyStack*)malloc(sizeof(MyStack)); obj->queue1 = (Queue*)malloc(sizeof(Queue)); obj->queue2 = (Queue*)malloc(sizeof(Queue)); obj->queue1->data = (int*)malloc(sizeof(int)*MAXSIZE); obj->queue2->data = (int*)malloc(sizeof(int)*MAXSIZE); obj->queue1->front = 0; obj->queue1->rear = 0; obj->queue2->front = 0; obj->queue2->rear = 0; return obj; } void myStackPush(MyStack* obj, int x) { obj->queue1->data[obj->queue1->rear] = x; obj->queue1->rear = (obj->queue1->rear + 1) % MAXSIZE; } int myStackPop(MyStack* obj) { while ((obj->queue1->front + 1) % MAXSIZE != (obj->queue1->rear) % MAXSIZE) { obj->queue2->data[obj->queue2->rear] = obj->queue1->data[obj->queue1->front]; obj->queue2->rear = (obj->queue2->rear + 1) % MAXSIZE; obj->queue1->front = (obj->queue1->front + 1) % MAXSIZE; } Queue* temp = obj->queue1; obj->queue1 = obj->queue2; obj->queue2 = temp; int res = obj->queue2->data[obj->queue2->front]; obj->queue2->front = (obj->queue2->front + 1) % MAXSIZE; return res; } int myStackTop(MyStack* obj) { while ((obj->queue1->front + 1) % MAXSIZE != (obj->queue1->rear) % MAXSIZE) { obj->queue2->data[obj->queue2->rear] = obj->queue1->data[obj->queue1->front]; obj->queue2->rear = (obj->queue2->rear + 1) % MAXSIZE; obj->queue1->front = (obj->queue1->front + 1) % MAXSIZE; } int res = obj->queue1->data[obj->queue1->front]; obj->queue2->data[obj->queue2->rear] = obj->queue1->data[obj->queue1->front]; obj->queue2->rear = (obj->queue2->rear + 1) % MAXSIZE; obj->queue1->front = (obj->queue1->front + 1) % MAXSIZE; Queue* temp = obj->queue1; obj->queue1 = obj->queue2; obj->queue2 = temp; return res; } bool myStackEmpty(MyStack* obj) { return obj->queue1->front == obj->queue1->rear; } void myStackFree(MyStack* obj) { free(obj->queue1->data); obj->queue1->data = NULL; free(obj->queue2->data); obj->queue2->data = NULL; free(obj->queue1); obj->queue1 = NULL; free(obj->queue2); obj->queue2 = NULL; free(obj); obj = NULL; }
-
Java语言版
-
C语言版