卖萌的弱渣

I am stupid, I am hungry.

Implement Stack Using Queues

Implement the following operations of a stack using queues.

  • push(x) – Push element x onto stack.
  • pop() – Removes the element on top of the stack.
  • top() – Get the top element.
  • empty() – Return whether the stack is empty.

Notes:

  • You must use only standard operations of a queue – which means only push to back, peek/pop from front, size, and is empty operations are valid.
  • Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
  • You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).

Solution

(Implement-Stack-Using-Queues.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

class Stack(object):
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []

    def push(self, x):
        """
        :type x: int
        :rtype: nothing
        """
        self.stack.append(x)

    def pop(self):
        """
        :rtype: nothing
        """
        self.stack.pop()


    def top(self):
        """
        :rtype: int
        """
        return self.stack[-1]

    def empty(self):
        """
        :rtype: bool
        """
        if not self.stack:
            return True
        else:
            return False
  • Java: push 的时候，把queue反过来
(Implement-Stack-Using-Queues.java) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class MyStack {
    Queue<Integer> myQueue;
    public MyStack(){
        this.myQueue = new LinkedList<Integer>();
    }
    // Push element x onto stack.
    public void push(int x) {
        myQueue.add(x);
        //　把queue反过来
        // add: 插入到队尾
        // poll(): 弹出head
        for (int i = 1; i<myQueue.size(); i++){
            myQueue.add(myQueue.poll());
        }
    }

    // Removes the element on top of the stack.
    public void pop() {
        myQueue.poll();
    }

    // Get the top element.
    public int top() {
        return myQueue.peek();
    }

    // Return whether the stack is empty.
    public boolean empty() {
        return myQueue.isEmpty();
    }
}