> For the complete documentation index, see [llms.txt](https://txfs19260817.gitbook.io/leetcode-go-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://txfs19260817.gitbook.io/leetcode-go-notes/solutions/225.-implement-stack-using-queues.md).

# 225. Implement Stack using Queues

## LeetCode [225. Implement Stack using Queues](https://github.com/txfs19260817/LeetCode-Go/blob/master/solutions/title/README.md)

### Description

Implement a last in first out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal queue (`push`, `top`, `pop`, and `empty`).

Implement the `MyStack` class:

* `void push(int x)` Pushes element x to the top of the stack.
* `int pop()` Removes the element on the top of the stack and returns it.
* `int top()` Returns the element on the top of the stack.
* `boolean empty()` Returns `true` if the stack is empty, `false` otherwise.

**Notes:**

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

**Example 1:**

```
Input
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 2, 2, false]

Explanation
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return False
```

**Constraints:**

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

**Follow-up:** Can you implement the stack 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. You can use more than two queues.

### Tags

Stack, Design

### Solution

Here we only use a single queue to implement the stack.

* Push: push `x` into the queue, then pop and push all other elements;
* Pop: same as the queue's pop;
* Top: return the value of the front element of the queue;
* Empty: return the equality of the length of queue and 0.

### Complexity

* Time complexity: $$O(n)$$ for Push; $$O(1)$$ for others;
* Space complexity: $$O(n)$$

### Code

```go
type MyStack struct {
	q []int
}

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

// Push element x onto stack. */
func (this *MyStack) Push(x int) {
	n := len(this.q)
	this.q = append(this.q, x)
	for i := 0; i < n; i++ {
		this.q = append(this.q, this.q[0])
		this.q = this.q[1:]
	}
}

// Pop removes the element on top of the stack and returns that element. */
func (this *MyStack) Pop() int {
	val := this.q[0]
	this.q = this.q[1:]
	return val
}

// Top get the top element. */
func (this *MyStack) Top() int {
	return this.q[0]
}

// Empty returns whether the stack is empty. */
func (this *MyStack) Empty() bool {
	return len(this.q) == 0
}
```

## Reference

1. [用队列实现栈](https://leetcode-cn.com/problems/implement-stack-using-queues/solution/yong-dui-lie-shi-xian-zhan-by-leetcode-solution/)


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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/225.-implement-stack-using-queues.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.