栈&队列

 栈，先进后出。   队列，先进先出。

232. 用栈实现队列（easy）

使用栈实现队列的下列操作：

• push(x) — 将一个元素放入队列的尾部。
• pop() — 从队列首部移除元素。
• peek() — 返回队列首部的元素。
• empty() — 返回队列是否为空。

解法：
双数据栈：栈S1的top作为队尾，栈S2的top作为队头

• 入队：直接push到S1（时间,空间复杂度）

• 出队：如果S2为空，从S1逐一pop到S2，再弹出S2的top，此时最差为

  如果S2不为空，直接pop S2，此时为 ```cpp std::stack S1; std::stack S2;

/ Push element x to the back of queue. */ void push(int x) { S1.push(x); } / Removes the element from in front of queue and returns that element. */ int pop() { if(S2.empty()) { while(!S1.empty()) { S2.push(S1.top()); S1.pop(); } } int res=S2.top(); S2.pop(); return res; }

```

具体算法题训练

• 利用栈(一个数据栈一个字符栈)和状态机实现一个简单计算器（”+”,”-“,”(“)—-224(hard)
• 利用最大堆和最小堆寻找中位数—-295(hard)
• 利用最大堆求一个数组中第k个大的元素—-215(median)