一、栈
栈是一种限定仅在表尾进行插入和删除操作的线性表。我们把允许插入和操作的一端称为栈顶，另一端称为栈底，不含任何数据元素的栈称为空栈。栈又称为后进先出（FIFO）的线性表，简称LIFO结构。栈的插入操作，叫做入栈；栈的删除操作，叫做出栈。
比如在自主餐厅里有一摞盘子，当我们取盘子时从最上面开始取，而当放新盘子时也是从最上面开始放，这就是一种栈。再比如在计算机处理递归函数时，也会用到栈。当一个函数被调用时，我们将返回地址（即被调函数执行完后，接下要执行的程序指令的地址）和被调函数的局部变量和形参的值都在存储在递归工作栈中。当执行完一次返回时，被调函数的局部变量和形参的值恢复为调用之前的值（这些值在栈的顶部），而且程序从返回地址处继续执行，这个返回地址也存储在递归工作栈的顶部。
栈的基本操作有：创建空栈，销毁栈，判断是否为空，返回栈的大小，返回栈顶元素，入栈，出栈等等。在C++标准库中，有栈的定义。
栈的物理存储方式也有顺序存储和链式存储两种，其C++实现如下：
二、栈的抽象数据类型
//抽象栈类
#pragma once
#include<iostream>
using namespace std;
template<class T>
class stack
{
public:
virtual ~stack(){}
virtual bool empty() const=0;//判断是否为空栈
virtual int size() const=0;//返回栈的大小
virtual T& top()=0;//返回栈顶元素的引用
virtual void pop()=0;//删除栈顶元素，弹栈
virtual void push(const T& theElement)=0;//入栈
virtual void output(ostream& out) const=0;
};
三、栈的顺序存储结构
//用数组实现栈，栈的顺序存储结构
#include<iostream>
#include<algorithm>
#include<iterator>
#include"stack.h"
using namespace std;
template<class T>
class arrayStack:public stack<T>
{
public:
arrayStack(int initialCapacity=10);
~arrayStack() {delete [] stack;}
bool empty() const {return stackTop==-1;}//当stackTop为-1，判断栈为空，为0是只有一个的栈
int size() const {return stackTop+1;}//返回栈的大小，数组从零开始，Top指向栈顶的下标
void output(ostream& out) const;
T& top()//返回栈顶元素
{
if(stackTop==-1)
{
cerr<<"satck is empty";
exit(0);
}
return stack[stackTop];
}
void pop()//出栈
{
if(stackTop==-1)
{
cerr<<"satck is empty";
return;
}
stack[stackTop--].~T();//T的析构函数，针对不同数据类型而言这样写具有通用
}
void push(const T& theElement)//入栈
{
if(stackTop==arrayLength-1)//空间已满，容量加倍
{
T* temp=new T[arrayLength*2];//新数组
copy(stack,stack+arrayLength,temp);//复制
delete [] stack;//删除旧的
stack=temp;//从新赋值
arrayLength*=2;
}
stack[++stackTop]=theElement;//在栈顶插入
}
private:
int stackTop;//
int arrayLength;//数组长度，栈的容量
T* stack;//栈
};
//构造函数，initialCapacity默认为10；
template<class T>
arrayStack<T>::arrayStack(int initialCapacity)
{
if(initialCapacity<1)
{
cerr<<"Initial Capacity Must be >0";
exit(0);
}
arrayLength=initialCapacity;
stack=new T[arrayLength];
stackTop=-1;
}
//输出操作
template<class T>
void arrayStack<T>::output(ostream& out) const
{
copy(stack,stack+stackTop+1,ostream_iterator<T>(out," "));
}
template<class T>
ostream& operator<<(ostream& out,const arrayStack<T>& x)
{
x.output(out);
return out;
}
测试代码：
#include"arrayStack.h"
#include<iostream>
using namespace std;
void main()
{
arrayStack<int> stack(5);
for(int i=0;i<20;i++)
stack.push(i);
cout<<stack<<endl;
stack.push(100);
cout<<stack<<endl;
stack.pop();
stack.pop();
cout<<stack<<endl;
cout<<stack.empty()<<endl;
cout<<stack.size()<<endl;
}
四、栈的链式存储结构
//用链表实现栈，栈的链式存储结构，在表头进行pop和push操作
#include<iostream>
#include<algorithm>
#include<iterator>
#include"stack.h"
using namespace std;
//节点的结构
template<class T>
struct stackNode
{
T element;//数据域
stackNode<T>* next;//指针域
//其他操作
stackNode(){}
stackNode(const T& element){this->element=element;}
stackNode(const T& element,stackNode<T>* next){this->element=element;this->next=next;}
};
template<class T>
class linkedStack:public stack<T>
{
public:
linkedStack(int initialCapacity=10){stackTop=NULL;stackSize=0;}
~linkedStack();
bool empty() const {return stackSize==0;}//判断栈为空否
int size() const {return stackSize;}//返回栈的大小
void output(ostream& out) const;
T& top()//返回栈顶元素
{
if(stackSize==0)
{
cerr<<"satck is empty";
exit(0);
}
return stackTop->element;
}
void pop()//出栈
{
if(stackSize==0)
{
cerr<<"satck is empty";
return;
}
stackNode<T>* nextNode=stackTop->next;
delete stackTop;
stackTop=nextNode;
stackSize--;
}
void push(const T& theElement)//入栈
{
stackTop=new stackNode<T>(theElement,stackTop);
stackSize++;
}
private:
int stackSize;//栈的大小
stackNode<T>* stackTop;
};
//构造函数，initialCapacity默认为10；
template<class T>
linkedStack<T>::~linkedStack()
{
while(stackTop!=NULL)
{
stackNode<T>* nextNode=stackTop->next;
delete stackTop;
stackTop=nextNode;
}
}
//输出操作
template<class T>
void linkedStack<T>::output(ostream& out) const
{
for(stackNode<T>* pNode=stackTop;pNode!=NULL;pNode=pNode->next)
out<<pNode->element<<" ";
}
template<class T>
ostream& operator<<(ostream& out,const linkedStack<T>& x)
{
x.output(out);
return out;
}
测试代码：
#include"linkedStack.h"
#include<iostream>
using namespace std;
void main()
{
linkedStack<int> myStack(5);
for(int i=0;i<20;i++)
myStack.push(i);
cout<<myStack<<endl;
myStack.push(100);
cout<<myStack<<endl;
myStack.pop();
myStack.pop();
cout<<myStack<<endl;
cout<<myStack.empty()<<endl;
cout<<myStack.size()<<endl;
}