纵有疾风起
人生不言弃

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

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

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

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

  原文是使用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的顶端了,又可以直接弹出。下图展示了一个使用两个栈实现队列的实例:

剑指Offer面试题:6.用两个栈实现队列插图1

三、解决问题

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');    }

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

剑指Offer面试题:6.用两个栈实现队列插图2

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

剑指Offer面试题:6.用两个栈实现队列插图3

 

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

原著是一个有趣的人,若有侵权,请通知删除

未经允许不得转载:起风网 » 剑指Offer面试题:6.用两个栈实现队列
分享到: 生成海报

评论 抢沙发

评论前必须登录!

立即登录