Microsoft : 一个栈实现队列

回复 17# ilovexiao77

当时上课的时候老师也出过这个题：但问的不是如何实现，而是这样的队列的最大容积是多少，当然，两个栈的容积都是n。这样我觉得比最简单是实现多了很多意思。

长见识了。。。还可以这么写！

只用一个stack的话，就要保证在任何时候，这个stack里都是越早加入的元素越靠top，越晚的越靠bottom。

这跟stack的性质正好相反，怎么实现呢？用递归。

Java代码：

1. // Implementing queue using only one stack and recusion
   
2. 
   
3. public class SSQueue {
   
4.         private Stack<Integer> stack;
   
5. 
   
6.         public SSQueue() {
   
7.                 this.stack = new Stack<Integer>();
   
8.         }
   
9. 
   
10.         public void enqueue(int e) {
    
11.                 this.stack = this.addAtBottom(e, this.stack);
    
12.         }
    
13. 
    
14.         private Stack<Integer> addAtBottom(int e, Stack<Integer> stack) {
    
15.                 if (stack == null) {
    
16.                         return null;
    
17.                 }
    
18. 
    
19.                 if (stack.size() == 0) {
    
20.                         stack.push(e);
    
21.                         return stack;
    
22.                 }
    
23. 
    
24.                 Integer top = stack.pop();
    
25.                 stack = this.addAtBottom(e, stack);
    
26.                 stack.push(top);
    
27. 
    
28.                 return stack;
    
29.         }
    
30. 
    
31.         public int dequeue() {
    
32.                 int e = -1;
    
33. 
    
34.                 e = this.stack.pop();
    
35. 
    
36.                 return e;
    
37.         }
    
38. 
    
39.         public boolean isEmpty() {
    
40.                 boolean isEmpty = false;
    
41. 
    
42.                 isEmpty = this.stack.isEmpty();
    
43. 
    
44.                 return isEmpty;
    
45.         }
    
46. 
    
47.         public int peek() {
    
48.                 int head = -1;
    
49. 
    
50.                 int top = this.stack.peek();
    
51.                 head = top;
    
52. 
    
53.                 return head;
    
54.         }
    
55. 
    
56.         /**
    
57.          * @param args
    
58.          */
    
59.         public static void main(String[] args) {
    
60.                 SSQueue myQueue = new SSQueue();
    
61.                
    
62.                 myQueue.enqueue(1);
    
63.                 myQueue.enqueue(2);
    
64.                 myQueue.enqueue(3);
    
65.                 myQueue.enqueue(4);
    
66.                 myQueue.enqueue(5);
    
67.                
    
68.                 while (!myQueue.isEmpty()) {
    
69.                         System.out.println(myQueue.dequeue());
    
70.                 }
    
71.         }
    
72. }

复制代码

运行结果：

1. 1
   
2. 2
   
3. 3
   
4. 4
   
5. 5

复制代码

#include <stack>
#include <iostream>

using namespace std;

template <typename T>
class Fifo : public std::stack<T>
{
        public:
                Fifo() {}
                void push(const T &val){
                        if(empty()) {
                                this->std::stack<T>::push(val);
                        } else {
                                T ntop = top();
                                pop();
                                push(val);
                                this->std::stack<T>::push(ntop);
                        }
                }
};

int main()
{
        Fifo<int> mf;
        int i;
        for(i = 0 ; i < 10 ; i ++)
        {
                mf.push(i);
        }

        i = 0;
        while(!mf.empty())
        {
                int data = mf.top();
                mf.pop();
                std::cout << i++  << " is  " << data << std::endl;
        }


        return 0;
}