# 232. Implement Queue using Stacks

## LeetCode [232. Implement Queue using Stacks](https://github.com/txfs19260817/LeetCode-Go/blob/master/solutions/title/README.md)

### Description

Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (`push`, `peek`, `pop`, and `empty`).

Implement the `MyQueue` class:

* `void push(int x)` Pushes element x to the back of the queue.
* `int pop()` Removes the element from the front of the queue and returns it.
* `int peek()` Returns the element at the front of the queue.
* `boolean empty()` Returns `true` if the queue is empty, `false` otherwise.

**Notes:**

* You must use **only** standard operations of a stack, which means only `push to top`, `peek/pop from top`, `size`, and `is empty` operations are valid.
* Depending on your language, the stack may not be supported natively. You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack's standard operations.

**Follow-up:** Can you implement the queue such that each operation is [**amortized**](https://en.wikipedia.org/wiki/Amortized_analysis) `O(1)` time complexity? In other words, performing `n` operations will take overall `O(n)` time even if one of those operations may take longer.

**Example 1:**

```
Input
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 1, 1, false]

Explanation
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
```

**Constraints:**

* `1 <= x <= 9`
* At most `100` calls will be made to `push`, `pop`, `peek`, and `empty`.
* All the calls to `pop` and `peek` are valid.

### Tags

Stack, Design

### Solution

We use 2 stacks `a` and `b`, for receive and emit elements, respectively.

* Push: push `x` into `a`;
* Peek: When `b` is empty, pop all elements from `a` and push them into `b`, then return the top of `b`;
* Push: do Peek first, then pop the top of `b`;
* Empty: return true if no elements exist in both `a` and `b`.

### Complexity

* Time complexity: $$O(n)$$ for Pop and Peek; $$O(1)$$ for others;
* Space complexity: $$O(n)$$

### Code

```go
type MyQueue struct {
	a, b []int
}

// Constructor initialize your data structure here.
func Constructor() MyQueue {
	return MyQueue{make([]int, 0, 100), make([]int, 0, 100)}
}

// Push element x to the back of queue.
func (this *MyQueue) Push(x int) {
	this.a = append(this.a, x)
}

// Pop removes the element from in front of queue and returns that element.
func (this *MyQueue) Pop() int {
	val := this.Peek()
	this.b = this.b[:len(this.b)-1]
	return val
}

// Peek gets the front element.
func (this *MyQueue) Peek() int {
	if len(this.b) == 0 {
		for len(this.a) > 0 {
			this.b = append(this.b, this.a[len(this.a)-1])
			this.a = this.a[:len(this.a)-1]
		}
	}
	return this.b[len(this.b)-1]
}

// Empty returns whether the queue is empty.
func (this *MyQueue) Empty() bool {
	return len(this.a) == 0 && len(this.b) == 0
}
```


---

# 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://txfs19260817.gitbook.io/leetcode-go-notes/solutions/232.-implement-queue-using-stacks.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.