当前位置:网站首页>【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语言版
边栏推荐
- Literature retrieval operation code
- uva11624 Fire! (双bfs)
- 【GNN】2022 G-Mixup: Graph Data Augmentation for Graph Classification
- OpenHarmony Light Smart Product Development Live Notes
- mysql-5.5.40的完全卸载
- VMware virtual machine cannot be connected to the Internet after forced shutdown
- Conversion between number systems
- nyoj306 走迷宫(搜索+二分)
- BUUCTF MISC刷题笔记(二)
- 【CNN】2022 ECCV 对比视觉Transformer的在线持续学习
猜你喜欢
BUUCTF MISC刷题笔记(二)
零搜索量的关键词,你需要布局吗?
PoPW代币分配机制或将点燃下一个牛市
[漏洞复现]CVE-2018-12613(远程文件包含)
探索APP性能优化之稳定性优化(解决方案)
Introduction to Network Layer Protocols
ASEMI整流桥GBJ810参数,GBJ810封装,GBJ810重量
The difference between big-endian and little-endian storage is easy to understand at a glance
数制之间的转换
leetcode 35. 搜索插入位置(二分法+找性质也很关键)
随机推荐
[漏洞复现]CVE-2018-12613(远程文件包含)
编程洗衣机:字符串输出后的乱码
数据解析之bs4学习
The embedded serial port interrupt can only receive one byte
pip3 source change to improve speed
文献检索作业代码
STM32 如何知道FLASH的使用情况
Shell编程之正则表达式
Use of prepareStatement
Euclid and the game
【MySQL】mysql:解决[Err] 1093 - You can‘t specify target table ‘表名‘ for update in FROM clause问题
OpenHarmony开源见面会(南京站)相关笔记
Programming a washing machine: garbled characters after string output
消息中间件(MQ)前置知识介绍(必看)
Analysis that may result in a savecount of 0 in Loadrunner checkpoints
bs4之爬取诗词学习
canvas 文字垂直居中
I'm here to advertise
Notes on OpenHarmony Open Source Meeting (Nanjing Station)
hdu2191 多重背包(2016xynu暑期集训检测 -----B题)