C/C++面试题—使用STL两个队列实现一个栈

向右看齐 2022-05-24 07:44 94阅读 0赞

# 题目介绍 #

使用STL中的两个队列实现一个栈，实现栈的top、pop、push、clear等操作。

# 思路分析 #

思路和[使用2个栈实现一个队列][2]是相通的，用一个队列queue1容器用来 压栈，出栈的时候判断queue1.size()是否大于1，大于1的话队尾元素是栈顶需要弹出，这时就用到了queue2，将queue1其他的元素倒腾到queue2中，queue1中剩下的那一个元素就是栈顶的元素了。下次再继续出栈，如果queue1中没有元素 就判断queue2中的元素，queue2的队尾为栈顶，将其他元素倒腾到queue1中。

# 代码展示 #

/* 使用STL，用两个队列来实现一个栈，完成栈的push，pop，top，clear */
    #include <queue>
    #include <stack>
    #include <iostream>
    using namespace std;
    
    template<typename T> class MyStack
    {
    public:
        void clear()
        {
            if (queue1.size() > 0)
                queue1.swap(queue<T>());
            if (queue2.size() > 0)
                queue2.swap(queue<T>());
    
        }
        T top() //栈顶就是 队列的最后一个元素，和pop函数十分类似
        {
            while (queue1.size() > 1)//queue1的队尾元素是栈顶元素，将其余的倒腾到queue2中去
            {
                T front = queue1.front();
                queue1.pop();
                queue2.push(front);
            }
            if (queue1.size() == 1)
            {
                T front = queue1.front();
                //queue1.pop();
                return front;
            }
            while (queue2.size() > 1)//queue1没有元素，queue2有元素，queue2的队尾为栈顶元素，将其余的倒腾到queue1中去
            {
                T front = queue2.front();
                queue2.pop();
                queue1.push(front);
            }
            if (queue2.size() == 1)
            {
                T front = queue2.front();
                //queue2.pop();
                return front;
            }
            throw std::exception("queue is empty");
        }
        void push(T data)   //压栈
        {
            queue1.push(data);
        }
        T pop() //将栈顶元素弹出
        {
                while (queue1.size() > 1)//queue1的队尾元素是栈顶元素，将其余的倒腾到queue2中去
                {
                    T front = queue1.front();
                    queue1.pop();
                    queue2.push(front);
                }
                if (queue1.size() == 1)
                {
                    T front = queue1.front();
                    queue1.pop();
                    return front;
                }
                while (queue2.size() > 1)//queue1没有元素，queue2有元素，queue2的队尾为栈顶元素，将其余的倒腾到queue1中去
                {
                    T front = queue2.front();
                    queue2.pop();
                    queue1.push(front);
                }
                if (queue2.size() == 1)
                {
                    T front = queue2.front();
                    queue2.pop();
                    return front;
                }
                throw std::exception("queue is empty");
        }
    private:
        queue<T> queue1;    //用来压栈
        queue<T> queue2;    //辅助容器
    };
    
    int main(int argc, char *argv[])
    {
        MyStack<int> stack;
        stack.push(1);
        stack.push(2);
        stack.push(3);
        int top = stack.top();//3
        cout << "top = " << top << endl;    //3
        int n1 = stack.pop();
        int n2 = stack.pop();
        top = stack.top();
        cout << "top = " << top << endl;    //1
        int n3 = stack.pop();
        cout << n1 << " "<< n2 << " " << n3 << endl;        //入栈 1 2 3 ->出栈 3 2 1
        stack.clear();
        stack.push(100);
        stack.push(200);
        stack.push(300);
        n1 = stack.pop();
        n2 = stack.pop();
        n3 = stack.pop();
        cout << n1 << " " << n2 << " " << n3 << endl;       //入栈 100 200 300 ->出栈 300 200 100
        return 0;
    }

# 运行测试 #

![这里写图片描述][70]

[2]: https://blog.csdn.net/qq_29542611/article/details/79630624
[70]: /images/20220524/39925ceb0afd4290b86822f94c623f78.png

发表评论取消回复

表情：

评论列表（有 0 条评论，94人围观）

还没有评论，来说两句吧...

相关阅读

相关栈&队列面试题之两个队列实现一个栈

两个队列实现一个栈在之前我曾经实现了两个栈实现一个队列的面试题，其实思路也很简单就是充分利用栈的特性-后进先出，将输入的数据先输入栈1，将该栈1再输出到栈2，最后将栈

àì夳堔傛蜴生んèń/ 2022年09月26日 01:57/ 0 赞/ 156 阅读

相关栈&队列面试题之之两个栈实现一个队列

使用两个栈实现一个队列剖析：我们知道栈是后进先出的一种数据结构，而队列是先进先出的一种数据结构，如何用两个栈来模拟队列这种数据结构呢？利用栈的特性-后进的先出，

本是古典何须时尚/ 2022年09月25日 13:21/ 0 赞/ 140 阅读

相关面试题7：用两个队列实现一个栈

面试题7：用两个队列实现一个栈题目描述用两个栈来实现一个队列，完成队列的Push和Pop操作。队列中的元素为int类型。代

梦里梦外;/ 2022年07月12日 05:15/ 0 赞/ 280 阅读

相关面试题7：用两个队列实现一个栈

面试题7：用两个队列实现一个栈题目描述用两个栈来实现一个队列，完成队列的Push和Pop操作。队列中的元素为int类型。代

- 日理万妓/ 2022年07月12日 05:15/ 0 赞/ 332 阅读

相关使用两个队列实现一个栈

两个队列实现一个栈队列是先进先出，而栈是先进后出；考虑到我们取栈顶元素的便利性，我们在实现时使得栈顶等于队列头；由于栈的pop弹出栈顶元素，而队列的pop也是弹出栈顶元

以你之姓@/ 2022年06月12日 07:37/ 0 赞/ 124 阅读

相关使用两个栈实现一个队列

两个栈实现一个队列： ![SouthEast][] 代码： include<iostream> include<stack> using n

「爱情、让人受尽委屈。」/ 2022年06月12日 07:28/ 0 赞/ 130 阅读

相关 C/C++面试题—使用STL两个队列实现一个栈

题目介绍使用STL中的两个队列实现一个栈，实现栈的top、pop、push、clear等操作。思路分析思路和[使用2个栈实现一个队列][2]是相通的，用一个

向右看齐/ 2022年05月24日 07:44/ 0 赞/ 95 阅读

相关详解两个队列实现一个栈（python实现——经典面试题）

1、任务详解使用两个队列数据结构实现一个栈，要求实现栈的出栈和进栈操作。 2、解题思路 push()操作：为了保证先进栈的元素一直在栈底，需要将两个队列交替

╰+哭是因爲堅強的太久メ/ 2022年05月14日 05:17/ 0 赞/ 96 阅读

相关两个队列实现一个栈+两个栈实现一个队列（Java 实现）

两个队列实现一个栈 1. 现有两个队列 q1 和 q2，入栈则将元素加到 q1 2. 出栈的时候先判读 q1 是否为空，因为 q1 中的元素总是后进来的，后进先出，除

浅浅的花香味﹌/ 2022年03月06日 03:18/ 0 赞/ 273 阅读

相关使用两个队列实现一个栈

栈：先进后出队列：先进先出思路：利用一个队列做主队列，另一个队列作为辅助队列，把元素翻转过来即可。 public class Test {

叁歲伎倆/ 2022年01月17日 04:09/ 0 赞/ 184 阅读