一、基础知识
栈与队列的内部实现机制
队列是先进先出,栈是先进后出
四个关于栈的问题
1、C++中stack 是容器么?
栈和队列是STL(C++标准库)里面的两个数据结构
STL中栈往往不被归类为容器,而被归类为container adapter(容器适配器)
STL 队列也不被归类为容器,而被归类为container adapter( 容器适配器)
2、我们使用的stack是属于哪个版本的STL?
栈和队列是SGI STL里面的数据结构
三个最为普遍的STL版本:
HP STL 其他版本的C++ STL,一般是以HP STL为蓝本实现出来的,HP STL是C++ STL的第一个实现版本,而且开放源代码。
P.J.Plauger STL 由P.J.Plauger参照HP STL实现出来的,被Visual C++编译器所采用,不是开源的。
SGI STL 由Silicon Graphics Computer Systems公司参照HP STL实现,被Linux的C++编译器GCC所采用,SGI STL是开源软件,源码可读性甚高。
3、我们使用的STL中stack是如何实现的?
栈的内部结构,栈的底层实现可以是vector,deque,list 都是可以的, 主要就是数组和链表的底层实现。
栈是以底层容器完成其所有的工作,对外提供统一的接口,底层容器是可插拔的(也就是说我们可以控制使用哪种容器来实现栈的功能)。
SGI STL,如果没有指定底层实现的话,默认是以deque为缺省情况下栈的底层结构。
deque是一个双向队列,只要封住一段,只开通另一端就可以实现栈的逻辑了。
SGI STL中 队列底层实现缺省情况下一样使用deque实现的。
可以指定vector为栈的底层实现,初始化stack的语句如下:
std::stack<int, std::vector<int> > third; // 使用vector为底层容器的栈
可以指定list 为队列的底层实现,初始化queue的语句如下:
std::queue<int, std::list<int>> third; // 定义以list为底层容器的队列
4、stack 提供迭代器来遍历stack空间么?
栈提供push 和 pop 等等接口,所有元素必须符合先进后出规则,所以栈不提供走访功能,也不提供迭代器(iterator)。 不像是set 或者map 提供迭代器iterator来遍历所有元素。
二、题目
232.用栈实现队列
做题思路
用两个栈实现队列,一个模拟入栈操作,一个模拟出栈操作
代码细节
// stack.top():返回最后入栈的元素,位于栈的最顶端(也就是最后一个被插入的元素)的元素
class MyQueue {
public:
// 用两个栈实现队列,一个模拟入栈操作,一个模拟出栈操作
stack<int> stack_1;
stack<int> stack_2;
MyQueue() {
}
// 将元素 x 推到队列的末尾
void push(int x) {
stack_1.push(x);
}
// 从队列的开头移除并返回元素,注意看动画,可以想象成给杯子倒水
int pop() {
// 注意点:只有当stack_2为空的时候,才能从stack_1里导入全部数据
if (stack_2.empty()) {
while (!stack_1.empty()) {
// 栈顶元素 c 是最后入栈1的元素,把最后入栈1的元素 c 先放进栈2里,出栈2时就先出 c
stack_2.push(stack_1.top());
stack_1.pop();
}
}
// 栈顶元素是最后入栈的元素
int res = stack_2.top();
stack_2.pop();
return res;
}
// 返回队列开头的元素,即第一个入队列的元素
// 同pop函数
int peek() {
// 直接使用已有的pop函数
int res= this->pop();
// 恢复原位
stack_2.push(res);
return res;
}
// 如果队列为空,返回 true ;否则,返回 false
bool empty() {
return stack_1.empty() && stack_2.empty();
}
};
225. 用队列实现栈
做题思路
法1:用两个队列que1和que2实现栈的功能,que2其实完全就是一个备份的作用,把que1最后面的元素以外的元素都备份到que2,然后弹出最后面的元素,再把其他元素从que2导回que1。
法2:用一个队列实现栈的功能,在模拟栈弹出元素的时候,只要将队列头部的元素(除了最后一个元素外) 重新添加到队列尾部,此时再去弹出元素就是栈的顺序了。
代码细节
// que.front():返回队列的第一个元素
// que.back():返回队列的最后一个元素
class MyStack {
public:
// 用一个队列实现栈的功能
queue<int> que;
MyStack() {
}
// 将元素 x 压入栈顶。
void push(int x) {
que.push(x);
}
// 移除并返回栈顶元素
int pop() {
int size = que.size()-1;
// 最后一个元素保留不变
while(size--) {
// 把队列的第一个元素(除了最后一个元素)重新添加到队列尾部
que.push(que.front());
que.pop();
}
// 取值,弹出,返回值
int res = que.front();
que.pop();
return res;
}
// 返回栈顶元素
int top() {
return que.back();
}
// 如果栈是空的,返回 true ;否则,返回 false 。
bool empty() {
return que.empty();
}
};
/**
* Your MyStack object will be instantiated and called as such:
* MyStack* obj = new MyStack();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->top();
* bool param_4 = obj->empty();
*/