算法-两个栈实现队列

小鱼儿 2022-06-10 07:25 164阅读 0赞

**题目：**  
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数appendTail和deleteHead，分别完成在队列尾部插入结点和在队列头部删除结点的功能。

template <typename T> class CQueue
    {
    public:
        CQueue(void);
        ~CQueue(void);
    
        // 在队列末尾添加一个结点
        void appendTail(const T& node);
    
        // 删除队列的头结点
        T deleteHead();
    
    private:
        stack<T> stack1;
        stack<T> stack2;
    };

**解题思路：**  
首先这个题目要完成两个栈实现队列，其次还涉及到C++类和模板的一些知识，先说前面：  
我们知道，[栈][Link 1]是一种后入先出的结构，而[队列][Link 2]恰恰相反，是一种先入先出的结构，需要用栈实现队列，这意味着我们有现成的push和pop可以用，以实现入队和出队。

现在有两个栈stack1和stack2，我们向stack1依次压入a，b，c三个值，stack2为空：  
![这里写图片描述][SouthEast]  
此时出栈的话，顺序为c，b，a，但是出队的顺序应该是a，b，c，为了实现想要的出队顺序，我们可以把stack1里面的内容依次压入stack2中：  
![这里写图片描述][SouthEast 1]  
此时再将stack2内的内容做出栈，将弹出a：  
![这里写图片描述][SouthEast 2]  
下面讨论再次入队的情况，将d压入stack1，此时两个栈的情况：  
![这里写图片描述][SouthEast 3]  
此时出队的话，在stack2中还有值的话，直接出栈stack2，弹出b，c。此时stack2中已经没有值了，需要再次从stack1中出栈到stack2中入栈，然后再次stack2的出栈，弹出d。这与队列的出队形式完全相同：  
![这里写图片描述][SouthEast 4]  
![这里写图片描述][SouthEast 5]  
![这里写图片描述][SouthEast 6]

我们可以根据上面的实验整理出一个编程思路，如果stack2中没有值，就做stack1到stack2的压栈，如果有就做stack2的出栈，而不管stack1有没有值都可以做入栈。

下面需要考虑的是C++的模板，使用模板的目的就是能够编写与类型无关的代码，在上面例子中使用了a，b，c，d，那么在实例化对象时T就行该是char，比如实例化一个叫做queue的对象：

CQueue<char> queue;

此外，由于deleteHead函数return不为空，所以他的类型是T，此外appendTail和deleteHead都是在类内声明，类外定义的函数，所以在定义函数时要加类名。

**代码实现**

template <typename T> CQueue<T>::~CQueue(void)
    {
    }
    
    template<typename T> void CQueue<T>::appendTail(const T& element)
    {
        stack1.push(element);
    } 
    
    template<typename T> T CQueue<T>::deleteHead()
    {
        if(stack2.size()<= 0)
        {
            while(stack1.size()>0)
            {
                T& data = stack1.top();
                stack1.pop();
                stack2.push(data);
            }
        }
    
        if(stack2.size() == 0)
            throw new exception("queue is empty");
    
        T head = stack2.top();
        stack2.pop();
    
        return head;
    }

[Link 1]: http://blog.csdn.net/chaipp0607/article/details/77127222
[Link 2]: http://blog.csdn.net/chaipp0607/article/details/77132325
[SouthEast]: /images/20220610/e44a1a92974248498d2cd390248bf6c3.png
[SouthEast 1]: /images/20220610/98f7d0875d7348dba15c46bd32d3ba34.png
[SouthEast 2]: /images/20220610/c5fd9fcfa0b642a4835e20369f24bf95.png
[SouthEast 3]: /images/20220610/50523ef5d81e42d480f39dd9ca8ce17c.png
[SouthEast 4]: /images/20220610/2e4f0e8509e64bc48d60b76394d688f3.png
[SouthEast 5]: /images/20220610/995263798d0c4fd2a60d9a4bd7eebac3.png
[SouthEast 6]: /images/20220610/6eb06135ba9c4ea186370e88da49ac26.png

发表评论取消回复

表情：

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

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

相关阅读

相关【数据结构】队列OJ：两个栈实现队列、两个队列实现栈、实现最小值栈

目录一、两个栈实现队列二、两个队列实现栈三、最小值栈----可获取栈的最小值 -------------------- 一、两个栈实现队列栈的特点是先进

梦里梦外;/ 2023年09月27日 13:26/ 0 赞/ 114 阅读

相关 Java 两个栈实现队列和两个队列实现栈

两个队列实现栈： package test; import java.util.Stack; public class TwoSt

以你之姓@/ 2022年07月18日 01:24/ 0 赞/ 231 阅读

相关两个队列实现一个栈

//两个队列实现一个栈 include<iostream> using namespace std; includ

ゞ浴缸里的玫瑰/ 2022年07月17日 01:52/ 0 赞/ 216 阅读

相关两个栈实现队列

> 问题：已知下面Stack类以及其三个方法push、pop和count，请用两个栈实现队列类的入队和出队的方法 -------------------- 这道题在面试中出

旧城等待，/ 2022年06月08日 12:44/ 0 赞/ 225 阅读

相关 python队列和栈操作，两个栈实现队列，两个队列实现栈

参考：[http://docs.python.org/2/tutorial/datastructures.html\more-on-lists的官方代码][http_docs.

迈不过友情╰/ 2022年05月06日 11:30/ 0 赞/ 273 阅读

相关用两个栈实现队列和两个队列实现栈

用两个栈实现队列，完成队列的Push和Pop操作。队列中的元素为int类型。分析：栈是先进后出，队列是先进先出。用两个栈实现队列，栈1入栈，栈2出栈，就是队列的顺序了

以你之姓@/ 2022年04月24日 15:02/ 0 赞/ 299 阅读

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

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

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

相关两个栈实现队列和两个队列实现栈 Java

public class Test07 { / 用两个栈实现一个队列（先进后出）队列的声明如下：实现它的两个函

àì夳堔傛蜴生んèń/ 2021年11月16日 06:08/ 0 赞/ 379 阅读

相关栈/两个栈实现一个队列

Java实现 / @auther: 巨未 @DATE: 2019/1/5 0005 18:29 @Descripti

た入场券/ 2021年09月23日 07:02/ 0 赞/ 404 阅读

相关队列/两个队列实现一个栈

顺序队列的实现 / @auther: 巨未 @DATE: 2019/1/5 20:17 @Description: 顺序队列

谁践踏了优雅/ 2021年09月23日 07:02/ 0 赞/ 402 阅读