4. Stack and Queue

Queue

Deque<Integer> queue = new LinkedList<>();

• add

• poll

• peek

Stack

Deque<Integer> queue = new LinkedList<>();

• push

• pop

• peek

Implement stack by queue

1. Two Queue, Push O(1), Pop O(n)

class MyStack {
    private Deque<Integer> q1; 
    private Deque<Integer> q2;
    private int top;

    public MyStack() {
        q1 = new LinkedList<>();
        q2 = new LinkedList<>();
    }

    public void push(int x) {
        q1.add(x);
        top = x;
    }

    public int pop() {
        while(q1.size() > 1){
            top = q1.poll();
            q2.add(top);
        }
        Deque<Integer> tmp = q1;
        q1 = q2;
        q2 = tmp;
        return q2.poll();
    }

    public int top() {
        return top;
    }

    public boolean empty() {
        return q1.isEmpty();
    }
}

2. Two Queue, Push O(n), Pop(1)

class MyStack {
    private Deque<Integer> q1; 
    private Deque<Integer> q2;

    public MyStack() {
        q1 = new LinkedList<>();
        q2 = new LinkedList<>();
    }

    public void push(int x) {
        q2.add(x);
        while(!q1.isEmpty()){
            q2.add(q1.poll());
        }
        Deque<Integer> tmp = q1;
        q1 = q2;
        q2 = tmp;
    }

    public int pop() {
        return q1.poll();
    }

    public int top() {
        return q1.peek();
    }

    public boolean empty() {
        return q1.isEmpty();
    }
}

3. One Queue, Push O(n), Pop(1)

class MyStack {
    private Deque<Integer> q; 

    public MyStack() {
        q = new LinkedList<>();
    }

    public void push(int x) {
        q.add(x);
        while(q.peek() != x){
            q.add(q.poll());
        }
    }

    public int pop() {
        return q.poll();
    }

    public int top() {
        return q.peek();
    }

    public boolean empty() {
        return q.isEmpty();
    }
}

Implement Queue by stack

1. Two stacks, add O(n), poll O(1)

class MyQueue {
    Deque<Integer> s1;
    Deque<Integer> s2; 

    public MyQueue() {
        s1 = new LinkedList<>();
        s2 = new LinkedList<>();
    }

    public void push(int x) {
        while(!s1.isEmpty()){
            s2.push(s1.pop());
        }
        s1.push(x);
        while(!s2.isEmpty()){
            s1.push(s2.pop());
        }
    }

    public int pop() {
        return s1.pop();
    }

    public int peek() {
        return s1.peek();
    }

    public boolean empty() {
        return s1.isEmpty();
    }
}

2. Two stacks, add average O(1), poll O(1)

class MyQueue {
    Deque<Integer> s1;
    Deque<Integer> s2; 
    int front;

    public MyQueue() {
        s1 = new LinkedList<>();
        s2 = new LinkedList<>();
    }

    public void push(int x) {
        if (s1.isEmpty()) front = x;
        s1.push(x);
    }

    public int pop() {
        if (s2.isEmpty()){
            while(!s1.isEmpty()){
                s2.push(s1.pop());
            }
        }
        return s2.pop();
    }

    public int peek() {
        if (!s2.isEmpty()) return s2.peek();
        return front;
    }

    public boolean empty() {
        return s1.isEmpty() && s2.isEmpty();
    }
}