欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2023-10-20 22:58:16
题目描述 用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。 解题思路 栈:先进后出,队列:先进先出。用两个【先进后出】的实现一个【先进先出】。对于两个栈而言,插入的时候没有什么问题,直接插入就可以,出栈的时候,需要借助另外一个栈操作。简单的来说就是负负为正。这里有 ......

题目描述

用两个栈来实现一个队列,完成队列的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);
        }
    }