栈和队列在实现结构上可以有数组和链表两种形式：
数组实现比较容易；
用链表结构比较复杂，因为有指针。
栈结构的基本操作：
pop 从栈顶弹出一个元素；
top或peek 只访问栈顶元素，但是不弹出删除；
push 向栈顶压入一个元素；
size 返回当前栈中的元素个数；
队列的基本操作：
与站操作不同的是，push操作为在队头加入元素；
而pop操作是从队列尾部弹出一个元素。
栈和队列的基本操作都是时间复杂度为o(1)的操作；
栈可以看做一条射线，底部是固定的；队列是一条直线，操作在两端进行，一端用来进入队列，一端用来出队列；
特殊结构：双端队列结构为首尾都可以压入和弹出元素！！！
优先级队列为根据元素的优先级值，决定元素的弹出顺序；优先级队列的结构堆结构，并不是线性结构。
树的遍历方式有先序、中序、后序以及按层遍历！
图的遍历方式：深度优先遍历（DFS）和宽度优先遍历（BFS）！
深度优先遍历可以用栈实现：元素入栈的顺序就是深度优先遍历的顺序也就是访问的顺序；
宽度优先遍历用队列实现：元素进队列的顺序就是宽度优先遍历的顺序，也就是访问的顺序。
平时使用的递归函数实际上用到了提供的函数系统栈，递归的过程可以看做递归函数依次进入函数站的处理过程！
所有用递归函数可以做的过程一定更可以用非递归的方式实现；
案例一：
实现一个特殊的栈，在实现栈的基本功能的 基础上，再实现返回栈中最小元素的操作getmin。
要求：
1. pop push getMin操作的时间复杂度丢失o(1)/
2. 设计的栈类型可以使用现成的栈结构。
一共有两种方式，两种方式都是利用两个栈，其中一个栈用来保存正常的数据元素，记为stackdata，另一个栈用来保存每一步的最小值，记为stackmin.。
第一种方式中，只有当前数小于等于stackmin的栈顶时，该数放入stackmin。在弹出的时候，只有stackdata当前值等于stackmin栈顶的时候才会弹出。
由压入规则可知，stackmin始终记录的都是压入的stackdata当前的最小值。再弹出的时候，stackmin在stackdata弹出的时候，依旧维护着stackdata中的最小值。
另一种方式中，当前数和stackmin栈顶元素比较，较小的压入stackmin。如果当前数不比stackmin中的数小，那么就依旧向stackmin中压入上一次压入的值。
stackmin中始终记录着stackdata中每一步的最小值，不管是压入还是弹出。并且stackdata和stackmin是同步弹出的，不需要比较。
由上面的两种方式可以知道。它们都是利用第二个栈stackmin来保存stackdata每一步的最小值。
并且这两种方式的时间复杂度都是o（1）额外空间复杂度都是o（n）,
区别在于方案一的stackmin在压入时稍微节省空间，弹出时稍微浪费时间，方案二stackmin在压入时稍微浪费空间，弹出时节省时间，因为弹出的时候不需要比较，同步弹出就可以。
class Solution {
public:
stack<int> datastack;
stack<int> minstack;
void push(int value) {
datastack.push(value);
if(!minstack.empty()&&value<=minstack.top())
minstack.push(value);
else if(minstack.empty())
minstack.push(value);
}
void pop() {
if(!datastack.empty()&&(datastack.top()==minstack.top())){
minstack.pop();
datastack.pop();
}else if(!datastack.empty()&&(datastack.top()!=minstack.top())){
datastack.pop();
}
}
int top() {
return datastack.top();
}
int min() {
return minstack.top();
}
};
上面的代码是方案一的实现！！
案例二：编写一个类，只能用两个栈结构实现队列，支持队列的基本操作（add，poll，peek）。对应c++队列中的（push pop front empty）
需要注意的是栈是先进后出，但是队列是先进先出，用两个栈正好可以实现一个队列。
实现方式为：
一个栈为压入栈，stackpush，压入数据时只向这个栈压入数据。
另一个栈是弹出栈，stackpop，在弹出数据时只从这个栈弹出数据。
因此将stackpush中的数据倒入stackpop栈中数据的顺序就倒过来了。
再从stackpop中弹出数据时，顺序就和队列一样了！！！
有两个需要注意的点：
1. 如果stackpush要往stackpop中倒入数据，那么必须要把stackpush中的所有数据一次性到完。
2. 如果stackpop中有数据，则不能发生倒数据的行为。
不能违反上面两点规则，否则会发生错误。
class TwoStack {
public:
vector<int> twoStack(vector<int> ope, int n) {
// write code here
vector<int> result;
int temp;
for(int i=0;i<n;i++){
if(ope[i]!=0){
if(push_stack.empty()&&!pop_stack.empty()){
while(!pop_stack.empty()){
push_stack.push(pop_stack.top());
pop_stack.pop();
}
}
push_stack.push(ope[i]);
}else{
if(pop_stack.empty()){
while(!push_stack.empty()){
temp= push_stack.top();
push_stack.pop();
pop_stack.push(temp);
}
}
result.push_back(pop_stack.top());
pop_stack.pop();
}
}
return result;
}
private:
stack<int> push_stack;
stack<int> pop_stack;
};
具体实现如上面的程序所示，但是需要时刻注意的是那两个不能违反的规则，否则会发生错误！！
从stackpush倒向stackpop这个行为可以选择在很多方法中（add poll peek）包含该逻辑，但要保证倒入数据的两个注意点不被违反。
案例三：实现一个栈的逆序，但是只能用递归函数和这个栈本身的操作来实现，而不能自己申请另外的数据结构。
首先介绍第一个函数：这个函数的功能是移除栈底元素并返回。利用了递归。
public int get(Stack<Integer> stack){
int result=stack.top();
stack.pop();
if(stack.empty()){
return result;
}else{
int last=get(Stack);
stack.push(result);
return last;
}
}
对于下面的例子来说，栈中原来的样子为：
1
2
3
上面的程序执行完毕之后，1和2又被重新压入栈中，3被返回。
上面的方法被记为get方法。
下面介绍一个函数：把栈中的元素逆序的主方法。也是利用了递归。
public void reverse(Stack<Integer>stack){
if(stack.isEmpty()){
reurn;
}
int i=get(stack);
reverse(stack);
stack.push();
}
这个函数利用了上面的方法，也就是删除栈底元素并返回。
也是利用了递归。
上面的例子中，栈中原来的样子为：
1
2
3
需要注意的是vector也可以当做stack来用，这样的话vector中的push_back相当于stack中的push，然后vector中的back相当于stack中的top，vector中的pop_back相当于stack中的pop。需要注意的是下面的程序中是将vector数组中的最后一个元素作为栈顶元素。之所以会这样是因为push_back是在数组的最后添加一个数据；pop_back是去掉数组的最后一个数据；back是得到数组的最后一个单元的引用；而front是得到数组头的引用。因此这里使用的是back而不是front。
class StackReverse {
public:
vector<int> reverseStack(vector<int> A, int n) {
// write code here
//首先需要实现的删除栈底元素，并且返回
reverse(A,n);
return A;
}
//首先需要实现的删除栈底元素，并且返回，这个函数也是利用递归函数实现，
int getStack(vector<int>& A,int n){
int temp=A.back();
A.pop_back();
if(A.empty()){
return temp;
}
else{
int last=getStack(A,n);
A.push_back(temp);
return last;//需要注意的是这里的last是非常重要的！！！
}
}
void reverse(vector<int>& B,int n ){
int temp;
if(B.empty()){
return;//注意在递归函数中，如果中间要返回那么如果这个递归函数的返回值不是空，那么中间的返回也要有返回值。
}else{
temp=getStack(B,n);
reverse(B,n);
B.push_back(temp);
}
}
};
具体的实现如上所示，上面的程序中将vector当做了stack来用！！
案例四：一个栈中元素类型为整形，现在想将该栈从顶到底按照从大到小的顺序排序，只允许申请一个栈，除此之外，可以申请新的变量，但不能申请额外的数据结构，如何完成排序？
方法为将想要排序的栈记为stack，申请的辅助栈记为help，在stack上执行pop操作，弹出的元素记为current，这个current要和help中的栈顶元素进行比较，如果current小于或者等于help栈顶元素的话，就直接push进入help栈；如果current大于help的栈顶元素，那么将help中的元素逐渐弹出并且压回到stack中，直到current小于等于help中的栈顶元素，然后将current压入栈。重复执行上面的操作，直到stack中没有元素，然后将help中的元素弹出压入到stack中。
class TwoStacks {
public:
vector<int> twoStacksSort(vector<int> numbers) {
// write code here
//这里规定第一个元素为栈顶也就是说，对于vector来说从左到右应该是从大到小排序的
//但是我们使用pop_back以及push_back 以及front函数的时候是将vector数组的最后的元素作为栈顶的。
//因此，这里我们将vector从后向前从小到大排序
stack<int> help;
int current;
while(!numbers.empty()){
if(help.empty()){
help.push(numbers.back());
numbers.pop_back();
}else{
if(numbers.back()>=help.top()){
help.push(numbers.back());
numbers.pop_back();
continue;
}else{
current=numbers.back();
numbers.pop_back();
while(!help.empty()){
if(current<help.top()){
numbers.push_back(help.top());
help.pop();
}else{
help.push(current);
break;
}
}
if(help.empty())
help.push(current);
}
}
}//最后help从栈顶到栈底是从大到小排列的
numbers.clear();
while(!help.empty()){
numbers.push_back(help.top());
help.pop();
}
return numbers;
}
};
需要时刻注意什么时候pop和什么时刻push！！！