java用两个栈实现队列的push和pop
程序员文章站
2023-11-02 23:57:27
文章目录1.题目详情2.解题代码1.题目详情用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead ,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead 操作返回 -1 )示例 1:输入:[“CQueue”,“appendTail”,“deleteHead”,“deleteHead”][[],[3],[],[]]输出:[null,null,3,-1]示例 2:输入:[“CQueue”,“dele...
1.题目描述
用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。
2.具体算法
class Solution
{
public:
void push(int node) {
stack1.push(node);//将node压入stack1中
}
int pop() {
int ref;//定义ref为记录出栈的元素
if(!stack2.empty())//记录stack2不为空时的情况
{
ref = stack2.top();
stack2.pop();
}
else{
if(!stack1.empty())//记录stack2为空,但是stack1不为空时的情况
{
while(!stack1.empty())
{
int temp;
temp = stack1.top();
stack2.push(temp);
stack1.pop();
}
ref = stack2.top();
stack2.pop();
}
}
return ref;//返回pop出的元素值
}
private:
stack<int> stack1;
stack<int> stack2;
};
3.算法总结
- 这个算法的操作很简单,但是重点是理解题目所要求的意思。用两个栈来实现队列,这个算法挺有趣的,而且在大大小小的面试和参考书上都有见过。它的push和pop操作都是指针对一个元素的出栈和入栈,不是将栈里面所有的元素都出栈和入栈,只要想清楚了这个问题,基本上就没问题了。
- push操作:将元素压入stack1中,保存下来。
- pop操作:分为两种情况:如果stack2是非空的,那么直接用stack2.pop()来使元素出栈;如果stack2是空的,那么只能将stack1中所有元素出栈,并按顺序压入stack2中,最后再用stack2.pop()来使栈顶元素出栈,以完成操作。
本文地址:https://blog.csdn.net/weixin_42534963/article/details/107354973