q232_用栈实现队列

package 栈相关.q232_用栈实现队列.f1;
import java.util.Stack;
/**
 * 双栈 入队o(n) 出队o(1)
 */
class MyQueue {
    private Stack<Integer> s1 = new Stack<>();
    private Stack<Integer> s2 = new Stack<>();
    private Integer front;
    /** Initialize your data structure here. */
    public MyQueue() {
    }
    /** Push element x to the back of queue. */
    public void push(int x) {
        if (s1.empty()){
            front = x;
        }
        while (!s1.isEmpty()){
            s2.push(s1.pop());
        }
        s2.push(x);
        while (!s2.isEmpty()){
            s1.push(s2.pop());
        }
    }
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        int value = s1.pop();
        if (!s1.empty()){
            front = s1.peek();
        }
        return value;
    }
    /** Get the front element. */
    public int peek() {
        return front;
    }
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return s1.isEmpty();
    }
}

package 栈相关.q232_用栈实现队列.f2;
import java.util.Stack;
/**
 * 双栈 入队o(1) 出队平均o(1)，最坏o(n)
 */
class MyQueue {
    private Stack<Integer> s1 = new Stack<>();
    private Stack<Integer> s2 = new Stack<>();
    private Integer front;
    /** Initialize your data structure here. */
    public MyQueue() {
    }
    /** Push element x to the back of queue. */
    public void push(int x) {
        if (s1.empty()){
            front = x;
        }
        s1.push(x);
    }
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        if (s2.isEmpty()) {
            while (!s1.isEmpty()){
                s2.push(s1.pop());
            }
        }
        return s2.pop();
    }
    /** Get the front element. */
    public int peek() {
        if (!s2.isEmpty()) {
            return s2.peek();
        }
        return front;
    }
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return s1.isEmpty() && s2.isEmpty();
    }
}

package 栈相关.q232_用栈实现队列.含有最大值的队列;
import java.util.LinkedList;
import java.util.Queue;
public class MaxQueue {
    private Queue<Integer> queue;
    private LinkedList<Integer> max;
    public MaxQueue() {
        queue = new LinkedList<>();
        max = new LinkedList<>();
    }
    public int max_value() {
        return max.size() == 0 ? -1 : max.getFirst();
    }
    public void push_back(int value) {
        queue.add(value);
        while (max.size() != 0 && max.getLast() < value) {
            max.removeLast();
        }
        max.add(value);
    }
    public int pop_front() {
        if (max.size() != 0 && queue.peek().equals(max.getFirst())) {
            max.removeFirst();
        }
        return queue.size() == 0 ? -1 : queue.poll();
    }
}