stack, queue, heap题型总结

####LeetCode 232. Implement Queue using Stacks

题目意思： 用两个Stacks 实现Queue的功能： push(x), pop(), peek(), empty()

思路： stack1用作push(),

stack2 用作pop()时把Stack1中正序过来，然后 stack2.pop()

主要是pop的实现：

1. if Stack2 is empty： transfer all stack1’s elements to stack2
2. endif; return stack2.pop()
   

   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 37 38 39 40 41

   class MyQueue { Stack<Integer> stack1; Stack<Integer> stack2; /** Initialize your data structure here. */ public MyQueue() { stack1 = new Stack<>(); stack2 = new Stack<>(); } /** Push element x to the back of queue. */ public void push(int x) { stack1.push(x); } /** Removes the element from in front of queue and returns that element. */ public int pop() { if(stack2.isEmpty()){ while(!stack1.isEmpty()){ stack2.push(stack1.pop()); } } return stack2.pop(); } /** Get the front element. */ public int peek() { if(stack2.isEmpty()){ while(!stack1.isEmpty()){ stack2.push(stack1.pop()); } } return stack2.peek(); } /** Returns whether the queue is empty. */ public boolean empty() { return stack1.isEmpty() && stack2.isEmpty(); } }

答案是： 最好是hasNext中实现

用Queue实现Stack的LIFO操作： push(x), pop(), peek(), empty()

1. 方法一： Deque: 双向队列 offerLast(x), pollLast(), peekLast()
2. 方法二： Queue: 单向出口队列： push(x): queue.offer(x)之后，记得把x前面的挪到queue后面去

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

//方法二
class MyStack {
    
    //单向队列
    Queue<Integer> queue;

    /** Initialize your data structure here. */
    public MyStack() {
        queue = new LinkedList<>();
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        queue.offer(x);
        for(int i = 0; i < queue.size() - 1; i++)
            queue.offer(queue.poll());
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        return queue.poll();
    }
    
    /** Get the top element. */
    public int top() {
        return queue.peek();
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return queue.isEmpty();
    }
}