# 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)

```java
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)

```java
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)

```java
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)

```java
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)

```java
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();
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://netjimmy.gitbook.io/code-interview-note/stack.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.