题目
用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。
思路
用栈来模拟队列。我们首先插入一个元素a到stack1中,再压入两个元素bc,此时栈中有元素abc,其中c位于栈顶,而stack2仍然为空。我们试着删除一个元素。按照队列先进先出的原则,我们应该先删除元素a。元素a存放在stack1中且不在栈顶,因此不能直接删除。注意到stack2还未使用,我们把stack1中的元素逐个弹出并压入stack2中,stack2中的元素是cba,栈顶元素是a,我们现在可以直接删除元素a了。
当stack2中不为空时,在stack2中的栈顶元素是最先进入队列的元素,可以弹出。如果stack2为空时,我们把stack1中的元素逐个弹出并压入stack2中。由于先进入队列的元素被压到stakc1的低端,经过弹出和压入之后就处于stack2的顶端了,可以直接弹出。
代码
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <algorithm>
using namespace std;
class Solution{
public:
void push(int node) {
stack1.push(node);
}
int pop() {
if(stack2.empty()){
if(stack1.empty()){
return -1;
}
while(!stack1.empty()){
stack2.push(stack1.top());
stack1.pop();
}
}
int num = stack2.top();
stack2.pop();
return num;
}
private:
stack<int> stack1;
stack<int> stack2;
};
int main(){
Solution s;
s.push(1);
s.push(2);
s.push(3);
cout<<s.pop()<<endl;
cout<<s.pop()<<endl;
s.push(4);
s.push(5);
cout<<s.pop()<<endl;
s.push(6);
cout<<s.pop()<<endl;
cout<<s.pop()<<endl;
cout<<s.pop()<<endl;
cout<<s.pop()<<endl;
return 0;
}
<script type="text/javascript">
$(function () {
$('pre.prettyprint code').each(function () {
var lines = $(this).text().split('\n').length;
var $numbering = $('<ul/>').addClass('pre-numbering').hide();
$(this).addClass('has-numbering').parent().append($numbering);
for (i = 1; i <= lines; i++) {
$numbering.append($('<li/>').text(i));
};
$numbering.fadeIn(1700);
});
});
</script>
分享到:
相关推荐
c++ c++_剑指offer题解之用两个栈实现队列
title: 剑指Offer-用两个栈实现队列subtitle: 用两个栈实现队列categories: 剑指Offer用两个栈实现队列题目描述用两个栈来实现一
要求用两个栈{stack1,stack2}实现一个队列,也就是说我们需要使用栈的push和pop功能来构造队列的push和pop功能。 栈我们用列表表示,相应的功能使用append和pop函数实现。 队列的push功能: 使用stack1来存储元素,...
python python_剑指offer第5题用两个栈实现队列
7. 用两个栈实现队列 8. 求旋转数组的最小数字 9. 斐波那契数列的第n项(青蛙跳台阶) 10. 二进制中1的个数 11. 数值的整数次方 12. 打印1到最大的n位数 13. O(1)时间删除链表节点 14. 使数组中的奇数位于偶数...
在本题中,我们需要使用两个栈来模拟队列的行为。 题目要求我们实现一个类`CQueue`,它有两个主要方法:`appendTail`用于在队列尾部插入元素,`deleteHead`用于从队列头部删除元素并返回该元素。如果队列为空,`...
# Python实现《剑指offer》 部分代码自己添加了一些测试用例, 或者自己添加了一些功能 1. 初级程序员注重算法和数据结构 2. 事先做好准备,对工作有热情 3. 面试过程放松。不要急于写代码,了解清楚所要解决的问题,...
《剑指Offer》中的每个问题通常会设计一个或多个函数来实现解题逻辑,如排序算法、搜索算法等。函数的参数传递、递归调用也是重点考察的内容。 4. **数组和字符串**: 数组是存储同类型元素集合的结构,字符串则是...
题目描述: 用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。 解题思路参考:https://blog.csdn.net/flower_48237/article/details/104055970
剑指Offer中的第9题提出了一个用两个栈实现队列的问题。这个问题的核心在于利用栈的特性模拟队列的行为。通常情况下,栈不支持在中间位置进行删除操作,但可以通过以下步骤实现队列功能: 1. 添加元素到队列尾部...
《剑指Offer资源》是一个包含了丰富编程面试题解和代码实现的压缩包,主要涵盖了算法和编程技巧两个核心领域。这个资源包对于准备IT行业的面试,尤其是针对算法工程师、软件开发工程师等职位的求职者来说,是极具...
# Python实现《剑指offer》 部分代码自己添加了一些测试用例, 或者自己添加了一些功能 1. 初级程序员注重算法和数据结构 2. 事先做好准备,对工作有热情 3. 面试过程放松。不要急于写代码,了解清楚所要解决的问题,...
《剑指Offer》是一本备受推崇的编程面试指南,它集结了众多知名互联网公司的面试题,旨在帮助程序员提升算法和编程能力,为求职面试做好准备。本书主要关注于Java语言的实现,通过解决书中提出的各类问题,读者可以...
public void push(int node) {//压栈之前先将栈里的元素全部pop出来并push到另一个栈//压入新元素//将之前pop出去的元素再压
- **问题描述**:使用两个栈实现一个队列,完成队列的基本操作。 - **解决方案**: - 设置两个栈:stack1用来模拟队列的入队操作,stack2用来模拟队列的出队操作。 - 入队时,直接将元素压入stack1。 - 出队时,...
4. **栈与队列**:用两个栈实现队列、栈的应用(如括号匹配)等。 5. **动态规划**:背包问题、最长公共子序列、爬楼梯等。 6. **递归与回溯**:八皇后问题、N皇后问题、全排列等。 7. **贪心算法**:活动安排、最小...
5. **用两个栈实现队列及用两个队列实现栈**:利用数据结构的特性进行转换,理解和灵活运用栈和队列的性质。 6. **旋转数组**:这类问题需要理解数组的旋转操作,可以采用分段旋转或者一次整体旋转的方法。 7. **...
面试中常见的题目有“括号匹配”、“两个栈实现队列”等。 4. **树**:树是一种非线性数据结构,有根节点、子节点和父节点的概念。二叉树、平衡树、红黑树等是面试中的常见话题,如“二叉树的遍历”、“构建高度...
7. 用两个栈实现队列:考察了栈和队列数据结构的特性及应用。 8. 数值的整数次方:考察了数学问题转化为编程问题的能力及边界条件处理。 书中所提到的算法和数据结构问题,都是程序员在面试时经常遇到的,例如: -...
"算法剑指offer题集"主要涵盖以下几个方面的内容: 1. **数据结构基础**:数组、链表、栈、队列、哈希表、树(二叉树、平衡树如AVL和红黑树)、图等是算法题目的常见背景。理解并熟练运用这些数据结构能够帮助我们...