做淘宝客网站难吗,提升关键词排名seo软件,免费个人网站建站申请一下,建设项目自主验收公示网站题目描述#xff1a;
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作#xff08;push、pop、peek、empty#xff09;#xff1a;
实现 MyQueue 类#xff1a;
void push(int x) 将元素 x 推到队列的末尾 int pop() 从队列的开头移除并返回元素…题目描述
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作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双端队列来模拟一个栈只要是标准的栈操作即可。
题目解答
class MyQueue {
public:stackint s_input,s_output;MyQueue() {}void push(int x) {s_input.push(x);}int pop() {if(s_output.empty()){while(!s_input.empty()){s_output.push(s_input.top());s_input.pop();}}int ress_output.top();s_output.pop();return res;}int peek() {int resthis-pop();s_output.push(res);return res;}bool empty() {return s_input.empty() s_output.empty();}
};/*** Your MyQueue object will be instantiated and called as such:* MyQueue* obj new MyQueue();* obj-push(x);* int param_2 obj-pop();* int param_3 obj-peek();* bool param_4 obj-empty();*/题目思路
优化后的代码思路主要集中在减少不必要的元素移动操作特别是在pop和peek方法中。这里我们详细分析优化后的代码思路
成员变量
代码中有两个栈s_input和s_output。s_input用于接收所有入队的元素而s_output用于辅助实现队列的先进先出特性。
方法
1. push(int x)
当元素入队时直接将其压入s_input栈。这是队列的基本入队操作没有变化。
2. pop()
在出队操作时首先检查s_output栈是否为空。如果为空意味着所有入队的元素都还在s_input中且尚未以队列的顺序排列。此时需要将s_input中的所有元素逐一弹出并压入s_output这样s_output的栈顶元素就是队列的队首元素。完成这个步骤后s_output的栈顶元素就可以安全地弹出并返回。
优化点通过确保在每次pop之前s_output中都有元素除非队列本身为空我们可以避免在每次pop时都检查并移动元素。这提高了效率因为一旦s_output被填充后续的pop操作就可以直接从s_output中执行而无需再次移动元素。
3. peek()
peek方法用于查看队列的队首元素但不移除它。其逻辑与pop方法类似首先检查s_output是否为空。如果为空则将s_input中的元素移动到s_output。然后返回s_output的栈顶元素但不弹出它。
优化点与pop方法共享相同的逻辑来确保s_output中有元素避免了重复的检查和移动操作。这提高了peek方法的效率。
4. empty()
这个方法检查队列是否为空。它通过检查s_input和s_output两个栈是否都为空来实现。如果两个栈都为空则队列为空。
总结
主要是利用两个栈来实现队列的功能并通过确保s_output栈在pop和peek操作前总是包含队列的元素除非队列为空来减少不必要的元素移动。这种优化减少了重复操作提高了队列操作的效率。
