剑指Offer面试题：6.用两个栈实现队列

港控/mmm° 2021-11-22 19:14 271阅读 0赞

# 一、题目：用两个栈实现队列 #

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

![192339156755360.jpg][]

原文是使用C++结合模板实现的定义，这里我们采用C\#结合泛型来实现这个队列的定义，我们要实现的就是两个方法：AppendTail与DeleteHead

public class CQueue<T>
        {
            private Stack<T> stack1;
            private Stack<T> stack2;
    
            public CQueue()
            {
                this.stack1 = new Stack<T>();
                this.stack2 = new Stack<T>();
            }
    
            public void AppendTail(T item)
            {
            }
    
            public T DeleteHead()
            {
            }
        }

# 二、解题思路 #

一个队列包含了两个栈stack1和stack2，因此这道题的意图是要求我们**操作这两个“先进后出”的栈实现一个“先进先出”的队列**CQueue。对于两个栈而言，对于插入操作，不妨假设都先插入到stack1，也就实现了入队操作。但是出队操作，则需要借助stack2的过渡：

当stack2中不为空时，在stack2中的栈顶元素是最先进入队列的元素，可以弹出。如果stack2为空时，我们把stack1中的元素逐个弹出并压入stack2。由于先进入队列的元素被压到stack1的底端，经过弹出和压入之后就处于stack2的顶端了，又可以直接弹出。下图展示了一个使用两个栈实现队列的实例：

![192348597852410.jpg][]

# 三、解决问题 #

## 3.1 代码实现 ##

public void AppendTail(T item)
        {
            stack1.Push(item);
        }
    
        public T DeleteHead()
        {
            if(stack2.Count <= 0)
            {
                while(stack1.Count > 0)
                {
                    T item = stack1.Pop();
                    stack2.Push(item);
                }
            }
    
            if(stack2.Count == 0)
            {
                throw new Exception("The queue is empty!");
            }
    
            T head = stack2.Pop();
            return head;
        }

借用作者的话：**本题解法的代码虽然只有只有20几行代码，但形成正确的思路却不容易**。

## 3.2 单元测试 ##

（1）往空的队列里添加、删除元素

[TestMethod]
        public void CQueueTest1()
        {
            CQueue<char> queue = new CQueue<char>();
            queue.AppendTail('a');
            queue.AppendTail('b');
            queue.AppendTail('c');
    
            char head = queue.DeleteHead();
            Assert.AreEqual(head, 'a');
        }
    
        [TestMethod]
        public void CQueueTest2()
        {
            CQueue<char> queue = new CQueue<char>();
            queue.AppendTail('a');
            queue.AppendTail('b');
            queue.AppendTail('c');
    
            char head = queue.DeleteHead();
            head = queue.DeleteHead();
    
            Assert.AreEqual(head, 'b');
        }

（2）往非空的队列里添加、删除元素

[TestMethod]
        public void CQueueTest3()
        {
            CQueue<char> queue = new CQueue<char>();
            queue.AppendTail('a');
            queue.AppendTail('b');
            queue.AppendTail('c');
    
            char head = queue.DeleteHead();
            head = queue.DeleteHead();
    
            queue.AppendTail('d');
            head = queue.DeleteHead();
    
            Assert.AreEqual(head, 'c');
        }
    
        [TestMethod]
        public void CQueueTest4()
        {
            CQueue<char> queue = new CQueue<char>();
            queue.AppendTail('a');
            queue.AppendTail('b');
            queue.AppendTail('c');
    
            char head = queue.DeleteHead();
            head = queue.DeleteHead();
    
            queue.AppendTail('d');
            head = queue.DeleteHead();
    
            queue.AppendTail('e');
            head = queue.DeleteHead();
    
            Assert.AreEqual(head, 'd');
        }

（3）连续删除元素直至队列为空

[TestMethod]
        public void CQueueTest5()
        {
            CQueue<char> queue = new CQueue<char>();
            queue.AppendTail('a');
            queue.AppendTail('b');
            queue.AppendTail('c');
    
            char head = queue.DeleteHead();
            head = queue.DeleteHead();
    
            queue.AppendTail('d');
            head = queue.DeleteHead();
    
            queue.AppendTail('e');
            head = queue.DeleteHead();
            head = queue.DeleteHead();
    
            Assert.AreEqual(head, 'e');
        }

单元测试的结果如下图所示：

![200032512067224.png][]

代码覆盖率结果如下图所示，可以看到，还需要继续增加测试用例才能使得覆盖率达到100%：

![200033342226100.png][]

作者：[周旭龙][Link 1]

出处：[http://edisonchou.cnblogs.com][http_edisonchou.cnblogs.com]

本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文链接。

转载于:https://www.cnblogs.com/edisonchou/p/4743930.html

[192339156755360.jpg]: /images/20211122/b2341197b90840f6aad011583dac7475.png
[192348597852410.jpg]: /images/20211122/c2422434578b4fbca37b04df26ea82e6.png
[200032512067224.png]: /images/20211122/1ca24b2c548148e99c640d45bbce3315.png
[200033342226100.png]: /images/20211122/7175757246f44cf9bd4afab91d8a17bc.png
[Link 1]: http://www.edisonchou.cn
[http_edisonchou.cnblogs.com]: http://edisonchou.cnblogs.com