Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commite0b9b63

Browse files
committed
225-implement-stack-using-queues.md Added follow-up solution in JavaScript.
1 parent9a4c92d commite0b9b63

File tree

3 files changed

+72
-15
lines changed

3 files changed

+72
-15
lines changed

‎README.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -51,7 +51,7 @@ You can skip the more difficult problems and do them later.
5151
-[232. Implement Queue using Stacks](en/1-1000/232-implement-queue-using-stacks.md) was solved in_Python, JavaScript_.
5252

5353
#Queue
54-
-[225. Implement Stack using Queues](en/1-1000/225-implement-stack-using-queues.md) was solved in_Python, JavaScript_ and2 ways.
54+
-[225. Implement Stack using Queues](en/1-1000/225-implement-stack-using-queues.md) was solved in_Python, JavaScript_ and3 ways.
5555

5656
#Dynamic Programming
5757
##Basics

‎en/1-1000/225-implement-stack-using-queues.md

Lines changed: 36 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -53,13 +53,18 @@ Can you implement the stack using only one queue?
5353
1. Option 1: Simplify the`push(x)` operation and complicate the`pop()` and`top()` operations. When`pop()` or`top()`, you need to find the last data with effort.
5454
2. Option 2: Simplify the`pop()` and`top()` operations and complicate the`push(x)` operation. When`push(x)`, you need to insert`x` into the front of the queue with effort.
5555
3. Advantages of Option 2: Less code; easier to understand logically because it sorts the data in the queue according to the`last in, first out` rule.
56-
4. This article mainly introduces`Option 2`, and the code of`Option 1` is attached in`Python` to facilitate readers to compare the two solutions.
56+
4. This article mainly introduces`Option 2`, and the code of`Option 1` is attached in`Python`sectionto facilitate readers to compare the two solutions.
5757

5858
##Complexity
5959
* Time:`push O(n)`,`pop O(1)`,`top O(1)`,`empty O(1)`.
6060
* Space:`O(n)`.
6161

62+
##Follow-up
63+
- You can use only one queue to make it. The only change is in the`push` method. Just find a way to insert`x` to the front of the queue without using another`queue_temp`.
64+
- When implementing the`push` method, first`queue.push(x)`, then execute`queue.length - 1` times`queue.push(queue.pop())`. The complete code is attached in`JavaScript` section.
65+
6266
##JavaScript
67+
###Solution for option 2
6368
```javascript
6469
varMyStack=function () {
6570
this.queue= []
@@ -95,8 +100,36 @@ MyStack.prototype.empty = function () {
95100
};
96101
```
97102

103+
###Follow-up solution: use only one queue
104+
```javascript
105+
varMyStack=function () {
106+
this.queue= []
107+
};
108+
109+
MyStack.prototype.push=function (x) {
110+
this.queue.push(x)
111+
112+
_.times(
113+
this.queue.length-1,
114+
()=>this.queue.push(this.queue.shift())
115+
)
116+
};
117+
118+
MyStack.prototype.pop=function () {
119+
returnthis.queue.shift()
120+
};
121+
122+
MyStack.prototype.top=function () {
123+
returnthis.queue[0]
124+
};
125+
126+
MyStack.prototype.empty=function () {
127+
returnthis.queue.length===0
128+
};
129+
```
130+
98131
##Python
99-
###Solution 1: Not recommended, for comparison only.
132+
###Solutionfor option1: Not recommended, for comparison only.
100133
```python
101134
classMyStack:
102135
def__init__(self):
@@ -139,7 +172,7 @@ class MyStack:
139172
returnlen(self.queue)==0
140173
```
141174

142-
###Solution 2:The recommended solution.It is short and easy to understand.
175+
###Solutionfor option2: It is short and easy to understand (recommended).
143176
```python
144177
classMyStack:
145178
def__init__(self):

‎zh/1-1000/225-implement-stack-using-queues.md

Lines changed: 35 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,5 @@
11
#225. 用队列实现栈 - 力扣题解最佳实践
2-
力扣问题链接：[225. 用队列实现栈](https://leetcode.cn/problems/implement-stack-using-queues), 难度:**简单**。
2+
力扣链接：[225. 用队列实现栈](https://leetcode.cn/problems/implement-stack-using-queues), 难度:**简单**。
33

44
##力扣“225. 用队列实现栈”问题描述
55
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（`push`、`top`、`pop` 和`empty`）。
@@ -46,29 +46,25 @@ myStack.empty(); // 返回 False
4646
###[进阶]
4747
你能否仅用一个队列来实现栈？
4848

49-
<details>
50-
<summary>解法提示</summary>
51-
可以只用一个队列。
52-
<br>
53-
改动只在`push`方法。只需要想办法不借助另一个`queue_temp`，把`x`插入到队列的头部。
54-
<br>
55-
在实现`push`方法时，先`queue.push(x)`，然后，执行`queue.length - 1`次`value = queue.pop(); queue.push(value)`即可。
56-
</details>
57-
5849
#中文题解
5950
##思路
6051
1. 使用的两个队列，一个队列用于输入和输出，另一个队列用于临时存储。
6152
2. 用队列模拟栈的功能，有两种方案可供选择：
6253
1. 方案一：简化`push(x)`操作，复杂化`pop()`和`top()`操作。`pop()`或`top()`时，需要费力找到最后一个数据。
6354
2. 方案二：简化`pop()`和`top()`操作，复杂化`push(x)`操作。`push(x)`时，需要费力地把`x`插入到队列头部。
6455
3. 方案二优点：代码量更少；从逻辑上更容易理解，因为它把队列中的数据按`后入先出`的规则排好序了。
65-
4. 本文主要介绍`方案二`，`方案一`的代码附在`Python`中，方便读者对比这两个方案。
56+
4. 本文主要介绍`方案二`，`方案一`的代码附在`Python`章节中，方便读者对比这两个方案。
6657

6758
##复杂度
6859
* 时间：`push O(n)`,`pop O(1)`,`top O(1)`,`empty O(1)`。
6960
* 空间：`O(n)`。
7061

62+
##进阶
63+
- 可以只用一个队列实现栈。改动只在`push`方法。只需要想办法不借助另一个`queue_temp`，把`x`插入到队列的头部。
64+
- 在实现`push`方法时，先`queue.push(x)`，然后，执行`queue.length - 1`次`queue.push(queue.pop())`即可。完整代码附在`JavaScript`章节中。
65+
7166
##JavaScript
67+
###方案二
7268
```javascript
7369
varMyStack=function () {
7470
this.queue= []
@@ -104,6 +100,34 @@ MyStack.prototype.empty = function () {
104100
};
105101
```
106102

103+
###进阶方案：只使用一个队列
104+
```javascript
105+
varMyStack=function () {
106+
this.queue= []
107+
};
108+
109+
MyStack.prototype.push=function (x) {
110+
this.queue.push(x)
111+
112+
_.times(
113+
this.queue.length-1,
114+
()=>this.queue.push(this.queue.shift())
115+
)
116+
};
117+
118+
MyStack.prototype.pop=function () {
119+
returnthis.queue.shift()
120+
};
121+
122+
MyStack.prototype.top=function () {
123+
returnthis.queue[0]
124+
};
125+
126+
MyStack.prototype.empty=function () {
127+
returnthis.queue.length===0
128+
};
129+
```
130+
107131
##Python
108132
###方案一：不推荐，仅用于对比。
109133
```python

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp