使用栈实现队列的下列操作:
push(x) -- 将一个元素放入队列的尾部。 pop() -- 从队列首部移除元素。 peek() -- 返回队列首部的元素。 empty() -- 返回队列是否为空。
第一感觉是 很简单,不就是get 和set 则2个操作吗
但是实现起来不容易,不知道里面要点是什么? 还是一片雾水,急着去看答案是没用的,只是浪费你更多时间。
case1 同时插入 3 个记录 12 11 2 ,同时pop3个记录12 11 2
case 2 同时插入 abc 2个记录(12 11 ),pop 1个记录(12),然后在插入1个记录
image.png
必须用2个栈来完成操作,一个负责存储A ,一个负责查询B
关键地方是 pop时候 必须是最先进入的,
如果case1 全部 从存储A,直接拿出就可以 如果是case2:因为必须按照顺序,因为B还有记录 如果在从A全部拿出。结果就不正确了。
image.png
class MyQueue {
private:
stack<int> m_input;
stack<int> m_output;
public:
/** Initialize your data structure here. */
MyQueue() {
}
/** Push element x to the back of queue. */
void push(int x) {
m_input.push(x);
}
/** Removes the element from in front of queue and returns that element. */
int pop() {
int result=peek();
m_output.pop();
return result;
}
/** Get the front element. */
int peek() {
if ( m_output.empty())
{
while ( !m_input.empty())
{
m_output.push(m_input.top());
m_input.pop();
}
}
return m_output.top();
}
/** Returns whether the queue is empty. */
bool empty() {
return m_input.empty() && m_output.empty();
}
};
用栈实现队列,在下面场景 例如
自己没有想到, 队列是2端插入,不回遇到这样问题。栈只是一端操作,需要2个栈来实现
LRU