面试题【栈和队列:用两个栈实现队列】

题目描述

用两个栈来实现一个队列，完成队列的push和pop操作。 队列中的元素为int类型。

解题思路

栈：先进后出，队列：先进先出。用两个【先进后出】的实现一个【先进先出】。对于两个栈而言，插入的时候没有什么问题，直接插入就可以，出栈的时候，需要借助另外一个栈操作。简单的来说就是负负为正。这里有个效率问题，进栈的第一个数据不用pop到出栈中直接返回就可以了。

基础属性

        /// <summary>
        /// 出栈
        /// </summary>
        private stack<int> dequeue;
        /// <summary>
        /// 进栈
        /// </summary>
        private stack<int> enqueue;

        public coding005()
        {
            dequeue = new stack<int>();
            enqueue = new stack<int>();
        }

进栈

        /// <summary>
        /// 进栈
        /// </summary>
        /// <param name="item"></param>
        public void enqueue(int item)
        {
            enqueue.push(item);
        }

出栈

        /// <summary>
        /// 出栈
        /// </summary>
        /// <returns></returns>
        public int dequeue()
        {
            //没有数据
            if (enqueue.count == 0 && dequeue.count == 0)
            {
                return -1;
            }

            while (enqueue.count > 0)
            {
                var item = enqueue.pop();
                dequeue.push(item);
            }

            return dequeue.pop();
        }

优化过的出栈

        /// <summary>
        /// 出栈（优化）
        /// </summary>
        /// <returns></returns>
        public int dequeue2()
        {
            //没有数据
            if (enqueue.count == 0 && dequeue.count == 0) {
                return -1;
            }

            while (enqueue.count > 1) {
                var item = enqueue.pop();
                dequeue.push(item);
            }

            if (enqueue.count == 1)
            {
                return enqueue.pop();
            }
            else {
                return dequeue.pop();
            }
        }

测试

[fact]
        public void test1()
        {
            coding005 coding005 = new coding005();
            queue<int> queue = new queue<int>();

            coding005.enqueue(1);
            queue.enqueue(1);

            coding005.enqueue(2);
            queue.enqueue(2);

            coding005.enqueue(3);
            queue.enqueue(3);

            assert.equal(queue.dequeue(), coding005.dequeue());
            assert.equal(queue.dequeue(), coding005.dequeue());
            assert.equal(queue.dequeue(), coding005.dequeue());
        }

        [fact]
        public void test2()
        {
            coding005 coding005 = new coding005();
            queue<int> queue = new queue<int>();

            coding005.enqueue(1);
            queue.enqueue(1);

            coding005.enqueue(2);
            queue.enqueue(2);

            assert.equal(queue.dequeue(), coding005.dequeue());
            assert.equal(queue.dequeue(), coding005.dequeue());

            coding005.enqueue(3);
            queue.enqueue(3);
            assert.equal(queue.dequeue(), coding005.dequeue());
        }

        [fact]
        public void test3()
        {
            coding005 coding005 = new coding005();
            queue<int> queue = new queue<int>();

            coding005.enqueue(1);
            queue.enqueue(1);

            assert.equal(queue.dequeue(), coding005.dequeue());
        }

        [fact]
        public void test4()
        {
            coding005 coding005 = new coding005();
            queue<int> queue = new queue<int>();

            coding005.enqueue(1);
            queue.enqueue(1);

            assert.equal(queue.dequeue(), coding005.dequeue());

            coding005.enqueue(2);
            queue.enqueue(2);

            coding005.enqueue(3);
            queue.enqueue(3);
            assert.equal(queue.dequeue(), coding005.dequeue());
            assert.equal(queue.dequeue(), coding005.dequeue());
        }

想入非非：扩展思维，发挥想象

1. 栈和队列的熟悉
2. 两个队列实现栈

两个队列实现栈

思路：把进队列的数据最后一个返回，每次都是返回进队列的最后一个数据。第二个队列主要用于保存临时数据，之后做交换用的。

    /// <summary>
    /// 栈和队列:用两个队列实现栈
    /// </summary>
    public class hstack
    {
        /// <summary>
        /// 出栈
        /// </summary>
        private queue<int> pop;
        /// <summary>
        /// 进栈
        /// </summary>
        private queue<int> push;

        public hstack()
        {
            pop = new queue<int>();
            push = new queue<int>();
        }

        /// <summary>
        /// 出栈
        /// </summary>
        /// <returns></returns>
        public int pop()
        {
            //没有数据
            if (push.count == 0 && pop.count == 0)
            {
                return -1;
            }

            while (push.count > 1)
            {
                var item = push.dequeue();
                pop.enqueue(item);
            }
            int result = push.dequeue();

            //数据交换回去
            var temp = pop;
            pop = push;
            push = temp;

            return result;
        }

        /// <summary>
        /// 进栈
        /// </summary>
        /// <param name="item"></param>
        public void push(int item)
        {
            push.enqueue(item);
        }
    }