面试题【栈和队列:用两个栈实现队列】
程序员文章站
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); } }