索鸟网

  1. 首页
  2. (试题)使用两个栈实现一个队列

(试题)使用两个栈实现一个队列


思路分析

  • 1、首先我们需要明确栈和队列两者的性质。栈是后进先出型,而队列是先进先出型。这是他俩在操作和使用上最明显的区别,那如果我们需要用两个栈来实现一个队列,最重要的一点就是能够使用栈后进先出的性质来实现队列的先进先出。

  • 2、需要实现上述操作的话,便会产生倒栈的操作。所谓倒栈,就是将数据在两个栈之间到来倒腾的操作。和我们在生活中使用两个杯子来回倒水加速热水冷却的过程十分类似。

  • 3、我们将两个栈分别命名为s1和s2。当我们需要入栈的时候,就将数据元素压入s1中;而需要进行出栈操作时,则将s1中的元素一个个弹出,反向压入s2中,再取s2的栈顶元素,之后再将s2中的剩余元素倒入s1中。此为一次倒栈操作。

  • 4、上述行为已经能够完成题目所需,但明显的是,该办法的效率不是很高,特别是在进行出栈操作时,每一步需要进行太多次倒栈操作。那我们便试着优化一下吧。

  • 5、我们可以在执行倒栈操作时,当执行完size-1次弹出及压栈之后,即s1还剩余一个栈底元素时,将此栈底元素直接弹出,而不再压入s2中,可以减少一次压栈操作。

  • 6、而在进行实际操作及测试的过程中,我们知道,并不会单纯的只进行入栈操作或者出栈操作,大多数操作,此两种操作都是交替进行的。所以,我们需要在进行压栈和出栈前,对行为进行一次预判,以防出现意料之外的bug。

  • 7、入队时,我们先行判断s1是否为空。若不为空,则说明s2中没有元素,我们直接将元素压入s1即可;若为空,则说明可能有剩余元素在s2中,我们需要先进行一次倒栈操作将s2中的元素倒入s1中之后,再将新的元素压入s1中。

  • 8、出队时,则先判断s2是否为空。若不为空,则直接弹出s2的栈顶元素即可;若为空,则需要将s1中的所有元素压入s2中之后,再将s2的栈顶元素弹出。


  • 9、综上所述,我们的最终方案是:
    • 入队时,直接将元素压入s1中;
    • 出队时,先判断s2是否为空。若不为空,则直接弹出s2的栈顶元素;若为空,则将s1中的元素一一压入s2中之后,再弹出s2的栈顶元素。

      这里写图片描述

      这里写图片描述

代码实现

template<class T>
class Myqueue
{
public:
    Myqueue()
    {}

    ~Myqueue()
    {}

    void Push(const T& x)
    {
        s1.push(x);
        back_elem = x;
    }

    void Pop()
    {
        if (!s2.empty())
        {
            s2.pop();
        }
        else if (!s1.empty())
        {
            while (!s1.empty())
            {
                s2.push(s1.top());
                s1.pop();
            }
            s2.pop();
        }
        /*else
        {
            cout << "Error!" << endl;
        }*/
    }

    T& Front()
    {
        if (!s2.empty())
        {
            return s2.top();
        }
        else if (!s1.empty())
        {
            while (!s1.empty())
            {
                s2.push(s1.top());
                s1.pop();
            }
            return s2.top();
        }
    }

    T& Back()
    {
        if (!empty())
            return back_elem;
    }

    T Size()
    {
        return s1.size() + s2.size();
    }

    bool empty()
    {
        return (s1.empty()) && (s2.empty());
    }

    void Print()
    {
        if (!s2.empty())
        {
            while (!s2.empty())
            {
                cout << s2.top() << " ";
                s2.pop();
            }
        }
        if (!s1.empty())
        {
            while (!s1.empty())
            {
                s2.push(s1.top());
                s1.pop();
            }
            while (!s2.empty())
            {
                cout << s2.top() << " ";
                s2.pop();
            }
        }
        cout << endl;

    }
private:
    stack<T> s1;
    stack<T> s2;
    T back_elem;
};

测试用例

void Test4()
{
    Myqueue<int> s;
    s.Push(1);
    s.Push(2);
    s.Push(3);
    s.Push(4);
    s.Print();


    s.Push(1);
    s.Push(2);
    s.Push(3);
    s.Push(4);
    s.Pop();
    s.Pop();
    s.Print();

    s.Push(1);
    s.Push(2);
    s.Push(3);
    s.Push(4);
    s.Pop();
    s.Pop();
    s.Push(5);
    s.Push(6);
    s.Print();

    s.Push(1);
    s.Push(2);
    s.Push(3);
    s.Push(4);
    s.Pop();
    s.Pop();
    s.Push(5);
    s.Push(6);
    cout << s.Back() << endl;
    cout << s.Front() << endl;
    cout << s.Size() << endl;

}

实现结果

这里写图片描述

来源地址:http://blog.csdn.net/js_evey/article/details/78229238 版权归作者所有!

相关教程

  • 算法---两个栈实现一个队列

    其实JS很“流氓的”,JS的数组完全既可以是队列也可以是栈。因为数组的push,pop就是栈的一组方法嘛。数据的push,shift就是队列的一组方法嘛。但是数据结构知识的需要,数据结构中对队列、栈的定义很明确: 栈,先进后出 队列,先进先出 现在要用两个栈实现一个队列,那么首先定义一个栈构造函数吧。 定义一个栈Stack构造函数 new两个Sta
  • 【数据结构】 两个栈实现一个队列【面试】

    栈结构:先进后出,后进先出,只允许在栈尾操作。队列:先进先出,在队尾入队,在队头出队。要想用两个栈实现一个队列,就需要使用一个相当于中间量的结构进行队列的入队和出队操作。用图形象化为:这样问题就从图中得出了思路:入队操作:把入队元素一一存入一个栈结构中即可。出队操作:出队时,先判断另一个栈结构中是否有元素,若有先将元素出栈Pop();若为空,则把栈S1中的元素全部倒入Push()
  • 两个栈实现队列

    s1和s2为两个栈 1. 入队时,将元素压入s1。 2. 出队时,判断s2是否为空,如不为空,则直接弹出顶元素;如为空,则将s1的元素逐个“倒入”s2,把最后一个元素弹出并出队。 这个思路,避免了反复“倒”栈,仅在需要时才“倒”一次。
  • 用两个栈实现队列

       编写一个类,用两个栈实现一个队列,支持队列的基本操作(add,poll,peek)   //编写一个类,用两个栈实现队列,支持队列的基本操作(add、poll、peek) import java.util.Stack; public class TwoStackQueue{ Stack &l
  • 剑指offer/LintCode494_用两个队列实现一个栈

    剑指offer/LintCode494_用两个队列实现一个栈 声明 文章均为本人技术笔记,转载请注明出处https://segmentfault.com/u/yzwall 解题思路 实现功能: 用两个队列实现一个栈,实现push(element),pop(),top()和isEmpty()方法; 解题思路 假设有队列queue1和queue2; 实现栈的
  • 【干货】容器适配器实现两个栈模拟队列

        用两个栈模拟队列的思想就是“倒水思想”,这里我们用自定义类型模拟出线性表,再用线性表做容器实现栈的数据结构,最后用栈来实现队列,代码如下:#include<iostream> #include<string> #include<cassert> struct __TrueType//类型
  • JavaScript实现 栈和队列

    创建一个类来表示栈: function Stack () { var items = []; //选择数组来保存栈里的元素 this.push = function (element) {//这个方法负责往栈里添加新元素(只添加到栈顶) items.push(element); }; this.pop = functi
  • 剑指offer/LintCode40_用两个栈模拟队列

    剑指offer/LintCode40_用两个栈模拟队列 声明 文章均为本人技术笔记,转载请注明出处https://segmentfault.com/u/yzwall 解题思路 实现功能: 用两个栈模拟实现一个队列的push(element),pop()和top()操作; 解题思路 假设有两个栈stack1, stack2 队列push(element)