`
SunnyYoona
  • 浏览: 384923 次
社区版块
存档分类
最新评论

[剑指Offer]9.用两个栈实现队列

 
阅读更多

题目

用两个栈来实现一个队列,完成队列的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的顶端了,可以直接弹出。

代码

/*---------------------------------------
*   日期:2015-07-20
*   作者:SJF0115
*   题目: 9.用两个栈实现队列
*   结果:AC
*   网址:http://www.nowcoder.com/books/coding-interviews/54275ddae22f475981afa2244dd448c6?rp=1
*   来源:剑指Offer
*   博客:
-----------------------------------------*/
#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;
            }//if
            while(!stack1.empty()){
                stack2.push(stack1.top());
                stack1.pop();
            }//while
        }//while
        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++-剑指offer题解之用两个栈实现队列

    c++ c++_剑指offer题解之用两个栈实现队列

    shushu1234#articles-backup#2018-04-13-剑指Offer-用两个栈实现队列1

    title: 剑指Offer-用两个栈实现队列subtitle: 用两个栈实现队列categories: 剑指Offer用两个栈实现队列题目描述用两个栈来实现一

    剑指offer刷题记录之用两个栈实现队列

    要求用两个栈{stack1,stack2}实现一个队列,也就是说我们需要使用栈的push和pop功能来构造队列的push和pop功能。 栈我们用列表表示,相应的功能使用append和pop函数实现。 队列的push功能: 使用stack1来存储元素,...

    python-剑指offer第5题用两个栈实现队列

    python python_剑指offer第5题用两个栈实现队列

    《剑指Offer》题目及代码.zip

    7. 用两个栈实现队列 8. 求旋转数组的最小数字 9. 斐波那契数列的第n项(青蛙跳台阶) 10. 二进制中1的个数 11. 数值的整数次方 12. 打印1到最大的n位数 13. O(1)时间删除链表节点 14. 使数组中的奇数位于偶数...

    (剑指offer)面试题09. 用两个栈实现队列

    在本题中,我们需要使用两个栈来模拟队列的行为。 题目要求我们实现一个类`CQueue`,它有两个主要方法:`appendTail`用于在队列尾部插入元素,`deleteHead`用于从队列头部删除元素并返回该元素。如果队列为空,`...

    Python《剑指offer》算法实现-用两个栈实现队列

    # Python实现《剑指offer》 部分代码自己添加了一些测试用例, 或者自己添加了一些功能 1. 初级程序员注重算法和数据结构 2. 事先做好准备,对工作有热情 3. 面试过程放松。不要急于写代码,了解清楚所要解决的问题,...

    C语言实现《剑指offer》.zip

    《剑指Offer》中的每个问题通常会设计一个或多个函数来实现解题逻辑,如排序算法、搜索算法等。函数的参数传递、递归调用也是重点考察的内容。 4. **数组和字符串**: 数组是存储同类型元素集合的结构,字符串则是...

    【剑指offer】面试题9-用两个栈实现队列-完整的可执行代码(Java)

    题目描述: 用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。 解题思路参考:https://blog.csdn.net/flower_48237/article/details/104055970

    剑指offer 计划1(栈与队列)---java(csdn)————程序.pdf

    剑指Offer中的第9题提出了一个用两个栈实现队列的问题。这个问题的核心在于利用栈的特性模拟队列的行为。通常情况下,栈不支持在中间位置进行删除操作,但可以通过以下步骤实现队列功能: 1. 添加元素到队列尾部...

    剑指Offer资源.zip

    《剑指Offer资源》是一个包含了丰富编程面试题解和代码实现的压缩包,主要涵盖了算法和编程技巧两个核心领域。这个资源包对于准备IT行业的面试,尤其是针对算法工程师、软件开发工程师等职位的求职者来说,是极具...

    Python《剑指offer》算法实现-用两个队列实现栈

    # Python实现《剑指offer》 部分代码自己添加了一些测试用例, 或者自己添加了一些功能 1. 初级程序员注重算法和数据结构 2. 事先做好准备,对工作有热情 3. 面试过程放松。不要急于写代码,了解清楚所要解决的问题,...

    《剑指Offer》题目及java代码实现

    《剑指Offer》是一本备受推崇的编程面试指南,它集结了众多知名互联网公司的面试题,旨在帮助程序员提升算法和编程能力,为求职面试做好准备。本书主要关注于Java语言的实现,通过解决书中提出的各类问题,读者可以...

    oneone1995#blog#[剑指offer-007]用两个栈实现队列1

    public void push(int node) {//压栈之前先将栈里的元素全部pop出来并push到另一个栈//压入新元素//将之前pop出去的元素再压

    剑指offer学习心得

    - **问题描述**:使用两个栈实现一个队列,完成队列的基本操作。 - **解决方案**: - 设置两个栈:stack1用来模拟队列的入队操作,stack2用来模拟队列的出队操作。 - 入队时,直接将元素压入stack1。 - 出队时,...

    剑指offer.rar

    4. **栈与队列**:用两个栈实现队列、栈的应用(如括号匹配)等。 5. **动态规划**:背包问题、最长公共子序列、爬楼梯等。 6. **递归与回溯**:八皇后问题、N皇后问题、全排列等。 7. **贪心算法**:活动安排、最小...

    剑指offer题解(C++).docx

    5. **用两个栈实现队列及用两个队列实现栈**:利用数据结构的特性进行转换,理解和灵活运用栈和队列的性质。 6. **旋转数组**:这类问题需要理解数组的旋转操作,可以采用分段旋转或者一次整体旋转的方法。 7. **...

    剑指offer程序

    面试中常见的题目有“括号匹配”、“两个栈实现队列”等。 4. **树**:树是一种非线性数据结构,有根节点、子节点和父节点的概念。二叉树、平衡树、红黑树等是面试中的常见话题,如“二叉树的遍历”、“构建高度...

    《剑指Offer》题目及代码(修订版2).pdf

    7. 用两个栈实现队列:考察了栈和队列数据结构的特性及应用。 8. 数值的整数次方:考察了数学问题转化为编程问题的能力及边界条件处理。 书中所提到的算法和数据结构问题,都是程序员在面试时经常遇到的,例如: -...

    前端面试题之算法剑指offer题集.zip

    "算法剑指offer题集"主要涵盖以下几个方面的内容: 1. **数据结构基础**:数组、链表、栈、队列、哈希表、树(二叉树、平衡树如AVL和红黑树)、图等是算法题目的常见背景。理解并熟练运用这些数据结构能够帮助我们...

Global site tag (gtag.js) - Google Analytics