类似百科式的网站建设,网页设计与制作基础教程,郑州网站开发外包,做网站打广告图片素材题目
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作#xff08;push、pop、peek、empty#xff09;#xff1a;
实现 MyQueue 类#xff1a;
void push(int x) 将元素 x 推到队列的末尾 int pop() 从队列的开头移除并返回元素 int peek() 返回…题目
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作push、pop、peek、empty
实现 MyQueue 类
void push(int x) 将元素 x 推到队列的末尾 int pop() 从队列的开头移除并返回元素 int peek() 返回队列开头的元素 boolean empty() 如果队列为空返回 true 否则返回 false 说明
你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。 你所使用的语言也许不支持栈。你可以使用 list 或者 deque双端队列来模拟一个栈只要是标准的栈操作即可。 提示 1 x 9 最多调用 100 次 push、pop、peek 和 empty 假设所有操作都是有效的 例如一个空的队列不会调用 pop 或者 peek 操作
思路
因为队列为先进先出。而栈为先进后出顺序刚好相反。那么我们只需要准备两个栈s1和s2。 将数据分别通过栈s1和s2.即可做到先进先出。
但需要注意的是因为可能连续push多个数pop一次然后继续push多个数。那么就形成了连续的段1和连续的段2。我们将段1放入s2后。需要先将此时s2的栈顶返回才是我们想要pop的数然后再继续放入段2。如果是将段1和段2都放入s2时再返回s2的栈顶不会是我们想要pop的数。因为此时s2中只是段间符合队列的顺序但段与段之间不符合队列的顺序。
同时我们也因为push的不连续性和push时先都将数只缓存在s1的操作只有在查询队列队头或者弹出队头时才涉及s2的操作导致s1和s2都是有可能为空的。我们要判断整个队列是否为空需要看s1和s2是否同时为空。 ①s1为空s2不为空的情况s1的数已经全部赋给s2了。此时s2就是队列。 ②s2为空s1不为空的情况正在连续push数中s1此时为队列的逆序顺序。
代码
class MyQueue {StackInteger s1 new StackInteger();StackInteger s2 new StackInteger();public MyQueue() {}public void push(int x) {s1.push(x);}public int pop() {if(s2.empty()){while(!s1.empty()){s2.push(s1.peek());s1.pop();}}int ans (int)s2.peek();s2.pop();return ans;}public int peek() {if(s2.empty()){while(!s1.empty()){s2.push(s1.peek());s1.pop();}}return s2.peek();}public boolean empty() {return s1.empty()s2.empty();}
}*/效率
0ms击败100.00%使用 Java 的用户。应该不用再优化了。
