当前位置:网站首页>【LeetCode每日一题】——225.用队列实现栈
【LeetCode每日一题】——225.用队列实现栈
2022-08-09 08:44:00 【IronmanJay】
一【题目类别】
- 栈
二【题目难度】
- 简单
三【题目编号】
- 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 {
Queue<Integer> queue1;
Queue<Integer> queue2;
public static void main(String[] args) {
}
public void MyStack() {
queue1 = new LinkedList<Integer>();
queue2 = new LinkedList<Integer>();
}
public void push(int x) {
queue2.offer(x);
while (!queue1.isEmpty()) {
queue2.offer(queue1.poll());
}
Queue<Integer> 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<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#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语言版
边栏推荐
猜你喜欢
随机推荐
嵌入式之串口中断只能收到一个字节
OSI网络模型
消息中间件(MQ)前置知识介绍(必看)
引导过程与服务控制
基于appinventor与EasyDL物体检测API的物体检测app
[MySQL]mysql: Solve the problem of [Err] 1093 - You can't specify target table 'table name' for update in FROM clause
Shell编程之正则表达式
PoPW代币分配机制或将点燃下一个牛市
XCTF高校战“疫”网络安全分享赛Misc wp
数制之间的转换
Euclid and the game
LAN技术-6MSTP
电子产品整机结构设计的一般性思路
[Vulnerability reproduction] CVE-2018-12613 (remote file inclusion)
交换机的工作原理
【Harmony OS】【ARK UI】公共事件模块
bs4之爬取诗词学习
EMQ X message server learning record - prepare for the subsequent completion
eTS UI development learning
Introduction to Network Layer Protocols