用栈实现队列

news/2025/2/4 13:06:22/

工作上一定没人这么搞，但是考察对栈、队列理解程度的好题

232.用栈实现队列

力扣题目链接

使用栈实现队列的下列操作：

push(x) – 将一个元素放入队列的尾部。
pop() – 从队列首部移除元素。
peek() – 返回队列首部的元素。
empty() – 返回队列是否为空。

示例:

MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek();  // 返回 1
queue.pop();   // 返回 1
queue.empty(); // 返回 false

说明:

  • 你只能使用标准的栈操作 – 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
  • 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
  • 假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）。

思路

这是一道模拟题，不涉及到具体算法，考察的就是对栈和队列的掌握程度。

使用栈来模式队列的行为，如果仅仅用一个栈，是一定不行的，所以需要两个栈一个输入栈，一个输出栈，这里要注意输入栈和输出栈的关系。

下面动画模拟以下队列的执行过程：

执行语句：
queue.push(1);
queue.push(2);
queue.pop(); 注意此时的输出栈的操作
queue.push(3);
queue.push(4);
queue.pop();
queue.pop();注意此时的输出栈的操作
queue.pop();
queue.empty();

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4IebXiUM-1687051224542)(https://code-thinking.cdn.bcebos.com/gifs/232.用栈实现队列版本2.gif)]

在push数据的时候，只要数据放进输入栈就好，但在pop的时候，操作就复杂一些，输出栈如果为空，就把进栈数据全部导入进来（注意是全部导入），再从出栈弹出数据，如果输出栈不为空，则直接从出栈弹出数据就可以了。

最后如何判断队列为空呢？如果进栈和出栈都为空的话，说明模拟的队列为空了。

在代码实现的时候，会发现pop() 和 peek()两个函数功能类似，代码实现上也是类似的，可以思考一下如何把代码抽象一下。

C++代码如下：

class MyQueue {
public:stack<int> stIn;stack<int> stOut;/** Initialize your data structure here. */MyQueue() {}/** Push element x to the back of queue. */void push(int x) {stIn.push(x);}/** Removes the element from in front of queue and returns that element. */int pop() {// 只有当stOut为空的时候，再从stIn里导入数据（导入stIn全部数据）if (stOut.empty()) {// 从stIn导入数据直到stIn为空while(!stIn.empty()) {stOut.push(stIn.top());stIn.pop();}}int result = stOut.top();stOut.pop();return result;}/** Get the front element. */int peek() {int res = this->pop(); // 直接使用已有的pop函数stOut.push(res); // 因为pop函数弹出了元素res，所以再添加回去return res;}/** Returns whether the queue is empty. */bool empty() {return stIn.empty() && stOut.empty();}
};

拓展

可以看出peek()的实现，直接复用了pop()， 要不然，对stOut判空的逻辑又要重写一遍。

再多说一些代码开发上的习惯问题，在工业级别代码开发中，最忌讳的就是 实现一个类似的函数，直接把代码粘过来改一改就完事了。

这样的项目代码会越来越乱，一定要懂得复用，功能相近的函数要抽象出来，不要大量的复制粘贴，很容易出问题！（踩过坑的人自然懂）

工作中如果发现某一个功能自己要经常用，同事们可能也会用到，自己就花点时间把这个功能抽象成一个好用的函数或者工具类，不仅自己方便，也方便了同事们。

同事们就会逐渐认可你的工作态度和工作能力，自己的口碑都是这么一点一点积累起来的！在同事圈里口碑起来了之后，你就发现自己走上了一个正循环，以后的升职加薪才少不了你！哈哈哈

其他语言版本

Java：

class MyQueue {Stack<Integer> stackIn;Stack<Integer> stackOut;/** Initialize your data structure here. */public MyQueue() {stackIn = new Stack<>(); // 负责进栈stackOut = new Stack<>(); // 负责出栈}/** Push element x to the back of queue. */public void push(int x) {stackIn.push(x);}/** Removes the element from in front of queue and returns that element. */public int pop() {    dumpstackIn();return stackOut.pop();}/** Get the front element. */public int peek() {dumpstackIn();return stackOut.peek();}/** Returns whether the queue is empty. */public boolean empty() {return stackIn.isEmpty() && stackOut.isEmpty();}// 如果stackOut为空，那么将stackIn中的元素全部放到stackOut中private void dumpstackIn(){if (!stackOut.isEmpty()) return; while (!stackIn.isEmpty()){stackOut.push(stackIn.pop());}}
}

Python：

class MyQueue:def __init__(self):"""in主要负责push，out主要负责pop"""self.stack_in = []self.stack_out = []def push(self, x: int) -> None:"""有新元素进来，就往in里面push"""self.stack_in.append(x)def pop(self) -> int:"""Removes the element from in front of queue and returns that element."""if self.empty():return Noneif self.stack_out:return self.stack_out.pop()else:for i in range(len(self.stack_in)):self.stack_out.append(self.stack_in.pop())return self.stack_out.pop()def peek(self) -> int:"""Get the front element."""ans = self.pop()self.stack_out.append(ans)return ansdef empty(self) -> bool:"""只要in或者out有元素，说明队列不为空"""return not (self.stack_in or self.stack_out)

Go：

type MyQueue struct {stackIn  []int //输入栈stackOut []int //输出栈
}func Constructor() MyQueue {return MyQueue{stackIn:  make([]int, 0),stackOut: make([]int, 0),}
}// 往输入栈做push
func (this *MyQueue) Push(x int) {this.stackIn = append(this.stackIn, x)
}// 在输出栈做pop，pop时如果输出栈数据为空，需要将输入栈全部数据导入，如果非空，则可直接使用
func (this *MyQueue) Pop() int {inLen, outLen := len(this.stackIn), len(this.stackOut)if outLen == 0 {if inLen == 0 {return -1}for i := inLen - 1; i >= 0; i-- {this.stackOut = append(this.stackOut, this.stackIn[i])}this.stackIn = []int{}      //导出后清空outLen = len(this.stackOut) //更新长度值}val := this.stackOut[outLen-1]this.stackOut = this.stackOut[:outLen-1]return val
}func (this *MyQueue) Peek() int {val := this.Pop()if val == -1 {return -1}this.stackOut = append(this.stackOut, val)return val
}func (this *MyQueue) Empty() bool {return len(this.stackIn) == 0 && len(this.stackOut) == 0
}

javaScript:

// 使用两个数组的栈方法（push, pop） 实现队列
/**
* Initialize your data structure here.
*/
var MyQueue = function() {this.stackIn = [];this.stackOut = [];
};/**
* Push element x to the back of queue. 
* @param {number} x
* @return {void}
*/
MyQueue.prototype.push = function(x) {this.stackIn.push(x);
};/**
* Removes the element from in front of queue and returns that element.
* @return {number}
*/
MyQueue.prototype.pop = function() {const size = this.stackOut.length;if(size) {return this.stackOut.pop();}while(this.stackIn.length) {this.stackOut.push(this.stackIn.pop());}return this.stackOut.pop();
};/**
* Get the front element.
* @return {number}
*/
MyQueue.prototype.peek = function() {const x = this.pop();this.stackOut.push(x);return x;
};/**
* Returns whether the queue is empty.
* @return {boolean}
*/
MyQueue.prototype.empty = function() {return !this.stackIn.length && !this.stackOut.length
};

TypeScript:

class MyQueue {private stackIn: number[]private stackOut: number[]constructor() {this.stackIn = [];this.stackOut = [];}push(x: number): void {this.stackIn.push(x);}pop(): number {if (this.stackOut.length === 0) {while (this.stackIn.length > 0) {this.stackOut.push(this.stackIn.pop()!);}}return this.stackOut.pop()!;}peek(): number {let temp: number = this.pop();this.stackOut.push(temp);return temp;}empty(): boolean {return this.stackIn.length === 0 && this.stackOut.length === 0;}
}

Swift：

class MyQueue {var stackIn = [Int]()var stackOut = [Int]()init() {}/** Push element x to the back of queue. */func push(_ x: Int) {stackIn.append(x)}/** Removes the element from in front of queue and returns that element. */func pop() -> Int {if stackOut.isEmpty {while !stackIn.isEmpty {stackOut.append(stackIn.popLast()!)}}return stackOut.popLast() ?? -1}/** Get the front element. */func peek() -> Int {let res = pop()stackOut.append(res)return res}/** Returns whether the queue is empty. */func empty() -> Bool {return stackIn.isEmpty && stackOut.isEmpty}
}

C:

/*
1.两个type为int的数组（栈），大小为100第一个栈stackIn用来存放数据，第二个栈stackOut作为辅助用来输出数据
2.两个指针stackInTop和stackOutTop，分别指向栈顶
*/
typedef struct {int stackInTop, stackOutTop;int stackIn[100], stackOut[100];
} MyQueue;/*
1.开辟一个队列的大小空间
2.将指针stackInTop和stackOutTop初始化为0
3.返回开辟的队列
*/
MyQueue* myQueueCreate() {MyQueue* queue = (MyQueue*)malloc(sizeof(MyQueue));queue->stackInTop = 0;queue->stackOutTop = 0;return queue;
}/*
将元素存入第一个栈中,存入后栈顶指针+1
*/
void myQueuePush(MyQueue* obj, int x) {obj->stackIn[(obj->stackInTop)++] = x;
}/*
1.若输出栈为空且当第一个栈中有元素（stackInTop>0时），将第一个栈中元素复制到第二个栈中（stackOut[stackTop2++] = stackIn[--stackTop1])
2.将栈顶元素保存
3.当stackTop2>0时，将第二个栈中元素复制到第一个栈中(stackIn[stackTop1++] = stackOut[--stackTop2])
*/
int myQueuePop(MyQueue* obj) {//优化：复制栈顶指针，减少对内存的访问次数int stackInTop = obj->stackInTop;int stackOutTop = obj->stackOutTop;//若输出栈为空if(stackOutTop == 0) {//将第一个栈中元素复制到第二个栈中while(stackInTop > 0) {obj->stackOut[stackOutTop++] = obj->stackIn[--stackInTop];}}//将第二个栈中栈顶元素（队列的第一个元素）出栈，并保存int top = obj->stackOut[--stackOutTop];//将输出栈中元素放回输入栈中while(stackOutTop > 0) {obj->stackIn[stackInTop++] = obj->stackOut[--stackOutTop];}//更新栈顶指针obj->stackInTop = stackInTop;obj->stackOutTop = stackOutTop;//返回队列中第一个元素return top;
}//返回输入栈中的栈底元素
int myQueuePeek(MyQueue* obj) {return obj->stackIn[0];
}//若栈顶指针均为0，则代表队列为空
bool myQueueEmpty(MyQueue* obj) {return obj->stackInTop == 0 && obj->stackOutTop == 0;
}//将栈顶指针置0
void myQueueFree(MyQueue* obj) {obj->stackInTop = 0;obj->stackOutTop = 0;
}

C#:

public class MyQueue {Stack<int> inStack;Stack<int> outStack;public MyQueue() {inStack = new Stack<int>();// 负责进栈outStack = new Stack<int>();// 负责出栈}public void Push(int x) {inStack.Push(x);}public int Pop() {dumpstackIn();return outStack.Pop();}public int Peek() {dumpstackIn();return outStack.Peek();}public bool Empty() {return inStack.Count == 0 && outStack.Count == 0;}// 处理方法：// 如果outStack为空，那么将inStack中的元素全部放到outStack中private void dumpstackIn(){if (outStack.Count != 0) return; while(inStack.Count != 0){outStack.Push(inStack.Pop());}}
}

PHP:

// SplStack 类通过使用一个双向链表来提供栈的主要功能。[PHP 5 >= 5.3.0, PHP 7, PHP 8]
// https://www.php.net/manual/zh/class.splstack.php
class MyQueue {// 双栈模拟队列：In栈存储数据；Out栈辅助处理private $stackIn;private $stackOut;function __construct() {$this->stackIn = new SplStack();$this->stackOut = new SplStack();}// In: 1 2 3  <= push  function push($x) {$this->stackIn->push($x);}function pop() {$this->peek();return $this->stackOut->pop();}function peek() {if($this->stackOut->isEmpty()){$this->shift();}return $this->stackOut->top();}function empty() {return $this->stackOut->isEmpty() && $this->stackIn->isEmpty();}// 如果Out栈为空，把In栈数据压入Out栈// In: 1 2 3 => pop    push => 1 2 3 :Out  private function shift(){while(!$this->stackIn->isEmpty()){$this->stackOut->push($this->stackIn->pop());}}}

Scala:

class MyQueue() {import scala.collection.mutableval stackIn = mutable.Stack[Int]() // 负责出栈val stackOut = mutable.Stack[Int]() // 负责入栈// 添加元素def push(x: Int) {stackIn.push(x)}// 复用代码，如果stackOut为空就把stackIn的所有元素都压入StackOutdef dumpStackIn(): Unit = {if (!stackOut.isEmpty) returnwhile (!stackIn.isEmpty) {stackOut.push(stackIn.pop())}}// 弹出元素def pop(): Int = {dumpStackIn()stackOut.pop()}// 获取队头def peek(): Int = {dumpStackIn()val res: Int = stackOut.pop()stackOut.push(res)res}// 判断是否为空def empty(): Boolean = {stackIn.isEmpty && stackOut.isEmpty}}

rust:

struct MyQueue {stack_in: Vec<i32>,stack_out: Vec<i32>,
}
impl MyQueue {fn new() -> Self {MyQueue {stack_in: Vec::new(),stack_out: Vec::new(),}}fn push(&mut self, x: i32) {self.stack_in.push(x);}fn pop(&mut self) -> i32 {if self.stack_out.is_empty(){while !self.stack_in.is_empty() {self.stack_out.push(self.stack_in.pop().unwrap());}}self.stack_out.pop().unwrap()}fn peek(&mut self) -> i32 {let res = self.pop();self.stack_out.push(res);res}fn empty(&self) -> bool {self.stack_in.is_empty() && self.stack_out.is_empty()}
}

http://www.ppmy.cn/news/447278.html

相关文章

华为Esight安装包

华为Esight安装包

eSight平台 提供存储、服务器、应用、交换机、路由器、防火墙、WLAN、PON网络、无线宽带集群设备、视频监控、IP话机、视讯设备等多种设备的统一管理&#xff0c;支持多厂商设备统一视图、资源&#xff0c;拓扑、故障、性能以及智能配置功能&#xff0c;同时为客户提供第三方设…
阅读更多...
华为软件机试测试题C语言,华为软件测试面试经验

华为软件机试测试题C语言,华为软件测试面试经验

面试过程&#xff1a; 网申&#xff0c;然后会收到测评通知&#xff0c;按平时表现做测评&#xff0c;没啥难度&#xff0c;就是花些时间做题。过几天后会统一安排时间机试&#xff0c;开摄像头在自己笔记本上做就好。这些都怎么不刷人。编程题1道简单的&#xff0c;一道复杂一…
阅读更多...
华为机试C语言-篮球比赛

华为机试C语言-篮球比赛

题目描述&#xff1a;https://pycoder.blog.csdn.net/article/details/125270003?spm1001.2014.3001.5502 动态规划 &#xff1a; dp[i] 表示是否能组成容量为 i 的战斗力。 #include <stdio.h> #include <stdlib.h> #include <string.h> #include <ma…
阅读更多...
华为机试C语言-最远足迹

华为机试C语言-最远足迹

题目描述&#xff1a;https://pycoder.blog.csdn.net/article/details/125531902 https://blog.csdn.net/weixin_44052055/article/details/123945932 #include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h>int res_max;int…
阅读更多...
华为机试C语言-组成最大数

华为机试C语言-组成最大数

题目描述&#xff1a;https://pycoder.blog.csdn.net/article/details/125923027 想不到这也是一道qsort的题目~ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h>char str[1000]; int strArrIndex; char strArr[1000…
阅读更多...
华为计算机c面试题,几道华为经典C语言面试题

华为计算机c面试题,几道华为经典C语言面试题

《几道华为经典C语言面试题》由会员分享&#xff0c;可在线阅读&#xff0c;更多相关《几道华为经典C语言面试题(6页珍藏版)》请在人人文库网上搜索。 1、1、找错void test1()char string10;char* str1;strcpy(string, str1);这里string数组越界&#xff0c;因为字符串长度为10…
阅读更多...
华为笔试

华为笔试

目录 2017年4月21日华为笔试题 圣诞的祝福 2017年4月21日华为笔试题 德州扑克 2017年4月21日华为笔试题 日期的天数序号 2017华为笔试题 任务调度 2017华为笔试题 公司年会 2017华为笔试题 水仙花数 2018华为笔试题 2018华为笔试题2 2017年4月21日华为笔试题 圣诞的祝福…
阅读更多...
华为研发工程师编程题 饮料瓶问题 C语言实现

华为研发工程师编程题 饮料瓶问题 C语言实现

这里写自定义目录标题 华为研发工程师编程题 饮料瓶问题 C语言实现 华为研发工程师编程题 饮料瓶问题 C语言实现 该编程题实现方法很多&#xff0c;找下来发现该C语言实现方法堪称为教科书实现方式&#xff0c;方法来自于教学课程&#xff0c;愿称最强&#xff01; 该问题算法…
阅读更多...
最新文章

Copyright @ 2022~2023