堆栈是一个后进先出(last-in-first-out, LIFO)的数据结构。
1. 数组实现的堆栈
源代码如下：
View Code
using namespace std;
template<class T>
class Stack{
public:
Stack(int MaxStackSize=10);
~Stack(){
delete [] stack;
}
bool IsEmpty()const{
return top==-1;
}
bool IsFull()const{
return top==MaxTop;
}
T Top()const;
Stack<T>& Add(const T& x);
Stack<T>& Delete(T & x);
private:
int top;
int MaxTop;
T* stack;
};
template<class T>
Stack<T>::Stack(int MaxStackSize)
{
MaxTop=MaxStackSize-1;
stack=new T[MaxStackSize];
top=-1;
}
template<class T>
T Stack<T>::Top()const
{
if(IsEmpty())
throw "Out of Bounds";
return stack[top];
}
template<class T>
Stack<T>& Stack<T>::Add(const T& x)
{
if(IsFull())
throw "Not enough Memorry";
stack[++top]=x;
cout<<"Success"<<endl;
return *this;
}
template<class T>
Stack<T>& Stack<T>::Delete(T & x)
{
if(IsEmpty())
throw "Out of Bounds";
x=stack[top--];
return *this;
}
int main(void)
{
int x;
Stack<int> S(3);
try {
S.Add(1).Add(2).Add(3).Add(4);
}
catch (...) {
cout << "Could not complete additions" << endl;
}
cout << "Stack should be 123" << endl;
cout << "Stack top is " << S.Top() << endl;
try {
S.Delete(x);
cout << "Deleted " << x << endl;
S.Delete(x);
cout << "Deleted " << x << endl;
S.Delete(x);
cout << "Deleted " << x << endl;
S.Delete(x);
cout << "Deleted " << x << endl;
}
catch (...) {
cout << "Last delete failed " << endl;
}
}
2.链表实现的堆栈
源代码如下：
View Code
using namespace std;
template<class T>
class LinkedStack;
template<class T>
class Node{
friend class LinkedStack<T>;
private:
T data;
Node<T>* link;
};
template<class T>
class LinkedStack{
public:
LinkedStack(){
top=0;
}
~LinkedStack();
bool IsEmpty()const{
return top==0;
}
bool IsFull()const;
T Top()const;
LinkedStack<T>& Add(const T& x);
LinkedStack<T>& Delete(T& x);
private:
Node<T>*top;
};
template<class T>
LinkedStack<T>::~LinkedStack()
{
Node<T>*next;
while(top){
next=top->link;
delete top;
top=next;
}
}
template<class T>
bool LinkedStack<T>::IsFull()const
{
try{
Node<T> *p=new Node<T>;
delete p;
return false;
}
catch(...){
return true;
}
}
template<class T>
T LinkedStack<T>::Top()const
{
if(IsEmpty())
throw "OutofBounds";
return top->data;
}
template<class T>
LinkedStack<T>& LinkedStack<T>::Add(const T& x)
{
Node<T> *p=new Node<T>;
p->data=x;
p->link=top;
top=p;
return *this;
}
template<class T>
LinkedStack<T>& LinkedStack<T>::Delete(T& x)
{
if(IsEmpty())
throw "Out of Bounds()";
x=top->data;
Node<T> *p;
p=top->link;
delete top;
top=p;
return *this;
}
int main(void)
{
int x;
LinkedStack<int> S;
try {S.Add(1).Add(2).Add(3).Add(4);}
catch (...) {
cout << "Could not complete additions" << endl;
}
cout << "Stack should be 1234" << endl;
cout << "Stack top is " << S.Top() << endl;
try {
S.Delete(x);
cout << "Deleted " << x << endl;
S.Delete(x);
cout << "Deleted " << x << endl;
S.Delete(x);
cout << "Deleted " << x << endl;
S.Delete(x);
cout << "Deleted " << x << endl;
}
catch (...) {
cout << "Last delete failed " << endl;
}
}
3. 堆栈使用
(1)括号匹配
View Code
#include <stack>
#include <string>
using namespace std;
void PrintMatchedPairs(string expr){
stack<int> s;
string::iterator it;
int i=1;
for(it=expr.begin();it!=expr.end();++it,++i){
if(*it=='(')
s.push(i);
else if(*it==')')
{
if(s.empty()){
cout<<"No match for left parentthesis at "<<i<<endl;
}
else{
int t=s.top();
cout<<t<<" "<<i<<endl;
s.pop();
}
}
}
while(!s.empty()) {
int t=s.top();
cout<<"No match for left parentthesis at "<<t<<endl;
s.pop();
}
}
int main(void)
{
const int MaxLength=200;
char expr[MaxLength];
cout << "Type an expression of length at most "
<< MaxLength << endl;
cin.getline(expr, MaxLength);
cout <<"The pairs of matching parentheses in"
<< endl;
cout<<expr<<endl;
cout <<"are" << endl;
string expr2(expr);
PrintMatchedPairs(expr2);
}
（2）汉诺塔
View Code
#include <stack>
using namespace std;
void TowersofHanoi(int n,int x,int y,int z){
if(n>0){
TowersofHanoi(n-1,x,z,y);
cout<<"move top disk from tower "<<x<<" to top of tower "<<y<<endl;
TowersofHanoi(n-1,z,y,x);
}
}
int main(){
cout << "Moves for a three disk problem are" << endl;
TowersofHanoi(3,1,2,3);
}
网上给出的一个很不错的非递归方式的汉诺塔实现，具体见这，下面是代码：
View Code
using namespace std;
//圆盘的个数最多为64
const int MAX = 64;
//用来表示每根柱子的信息
struct st{
int s[MAX]; //柱子上的圆盘存储情况
int top; //栈顶，用来最上面的圆盘
char name; //柱子的名字，可以是A，B，C中的一个
int Top()//取栈顶元素
{
return s[top];
}
int Pop()//出栈
{
return s[top--];
}
void Push(int x)//入栈
{
s[++top] = x;
}
} ;
long Pow(int x, int y); //计算x^y
void Creat(st ta[], int n); //给结构数组设置初值
void Hannuota(st ta[], long max); //移动汉诺塔的主要函数
int main(void)
{
int n;
cin >> n; //输入圆盘的个数
st ta[3]; //三根柱子的信息用结构数组存储
Creat(ta, n); //给结构数组设置初值
long max = Pow(2, n) - 1;//动的次数应等于2^n - 1
Hannuota(ta, max);//移动汉诺塔的主要函数
return 0;
}
void Creat(st ta[], int n)
{
ta[0].name = 'A';
ta[0].top = n-1;
//把所有的圆盘按从大到小的顺序放在柱子A上
for (int i=0; i<n; i++)
ta[0].s[i] = n - i;
//柱子B，C上开始没有没有圆盘
ta[1].top = ta[2].top = 0;
for (int i=0; i<n; i++)
ta[1].s[i] = ta[2].s[i] = 0;
//若n为偶数，按顺时针方向依次摆放 A B C
if (n%2 == 0)
{
ta[1].name = 'B';
ta[2].name = 'C';
}
else //若n为奇数，按顺时针方向依次摆放 A C B
{
ta[1].name = 'C';
ta[2].name = 'B';
}
}
long Pow(int x, int y)
{
long sum = 1;
for (int i=0; i<y; i++)
sum *= x;
return sum;
}
void Hannuota(st ta[], long max)
{
int k = 0; //累计移动的次数
int i = 0;
int ch;
while (k < max)
{
//按顺时针方向把圆盘1从现在的柱子移动到下一根柱子
ch = ta[i%3].Pop();
ta[(i+1)%3].Push(ch);
cout << ++k << ": " <<
"Move disk " << ch << " from " << ta[i%3].name <<
" to " << ta[(i+1)%3].name << endl;
i++;
//把另外两根柱子上可以移动的圆盘移动到新的柱子上
if (k < max)
{
//把非空柱子上的圆盘移动到空柱子上，当两根柱子都为空时，移动较小的圆盘
if (ta[(i+1)%3].Top() == 0 ||
ta[(i-1)%3].Top() > 0 &&
ta[(i+1)%3].Top() > ta[(i-1)%3].Top())
{
ch = ta[(i-1)%3].Pop();
ta[(i+1)%3].Push(ch);
cout << ++k << ": " << "Move disk "
<< ch << " from " << ta[(i-1)%3].name
<< " to " << ta[(i+1)%3].name << endl;
}
else
{
ch = ta[(i+1)%3].Pop();
ta[(i-1)%3].Push(ch);
cout << ++k << ": " << "Move disk "
<< ch << " from " << ta[(i+1)%3].name
<< " to " << ta[(i-1)%3].name << endl;
}
}
}
}
本人使用STL中的stack对上面的代码进行了一下修改：
View Code
public:
stack<int> st;
char name;
};
int Pow(int x,int y){
int sum=1;
for(int i=0;i<y;i++)
sum*=x;
return sum;
}
void Hanoi(int N){
Tower ta[3];
ta[0].name='A';
for(int i=0;i<N;i++)
ta[0].st.push(N-i);
if(N%2==0){
ta[1].name='B';
ta[2].name='C';
}
else{
ta[1].name='C';
ta[2].name='B';
}
int k=0;
int i=0;
int ch;
int max=Pow(2,N)-1;
while(k<max){
ch=ta[i%3].st.top();
ta[i%3].st.pop();
ta[(i+1)%3].st.push(ch);
cout<<++k<<": Move disk "<<ch<<" from "<<ta[i%3].name<<" to "<<ta[(i+1)%3].name<<endl;
i++;
if(k<max){
if(ta[(i+1)%3].st.empty()||!ta[(i-1)%3].st.empty()&&ta[(i+1)%3].st.top()>ta[(i-1)%3].st.top()){
ch=ta[(i-1)%3].st.top();
ta[(i-1)%3].st.pop();
ta[(i+1)%3].st.push(ch);
cout<<++k<<": Move disk "<<ch<<" from "<<ta[(i-1)%3].name<<" to "<<ta[(i+1)%3].name<<endl;
}
else{
ch=ta[(i+1)%3].st.top();
ta[(i+1)%3].st.pop();
ta[(i-1)%3].st.push(ch);
cout<<++k<<": Move disk "<<ch<<" from "<<ta[(i+1)%3].name<<" to "<<ta[(i-1)%3].name<<endl;
}
}
}
}
下图是对两种方法（递归和迭代）的比较：
