用栈实现队列
程序员文章站
2024-01-28 21:52:46
...
利用一个临时栈,调换顺序
class MyQueue {
public:
/** Initialize your data structure here. */
MyQueue() {
}
/** Push element x to the back of queue. */
void push(int x) {
stack<int> tmp_stack;
while(!data_stack.empty())
{
tmp_stack.push(data_stack.top());
data_stack.pop();
}
tmp_stack.push(x);
while(!tmp_stack.empty())
{
data_stack.push(tmp_stack.top());
tmp_stack.pop();
}
}
/** Removes the element from in front of queue and returns that element. */
int pop() {
int x = data_stack.top();
data_stack.pop();
return x;
}
/** Get the front element. */
int peek() {
return data_stack.top();
}
/** Returns whether the queue is empty. */
bool empty() {
return data_stack.empty();
}
private:
stack<int> data_stack;
};
/**
* 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();
*/
2:
class MyQueue {
public:
/** Initialize your data structure here. */
MyQueue() {
}
//双栈法,一个用来存输入,一个用来存输出,当需要输出时,如果output为空,就把input的部分放进来,相当于就调换了顺序
//如果不为空,就可以直接out.pop(),因为放在output的是已经调换过的了
/** Push element x to the back of queue. */
void push(int x) {
input.push(x);
}
/** Removes the element from in front of queue and returns that element. */
int pop() {
adjust();
int x = output.top();
output.pop();
return x;
}
/** Get the front element. */
int peek() {
adjust();
return output.top();
}
/** Returns whether the queue is empty. */
bool empty() {
return input.empty()&&output.empty();
}
private:
stack<int> input;
stack<int> output;
void adjust()
{
if(!output.empty())
return;
while(!input.empty())
{
output.push(input.top());
input.pop();
}
}
};
/**
* 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();
*/
上一篇: PHP如何透过ODBC来存取数据库
下一篇: 抖音带货提升销量的知识分享