1 栈具有后进先出（LIFO）的操作特点，是操作受限的线性表。栈的存储有顺序栈和链栈两种。
2 在顺序存储方式下，采用一维数组（即向量）来模拟连续的存储空间。通常将0下表作为栈底，栈的第一个元素（即栈底元素）存放在0下表位置。顺序栈的实现：
//SqStack.h#ifndef _SQSTACK_#define _SQSTACK_template class SqStack{public: SqStack(int); ~SqStack(); void Clear(); bool Empty() const; int Length() const; T& Top() const; void Push(const T&); void Pop();private: T* m_base; int m_top; int m_size;};template SqStack ::SqStack(int m){ m_top = 0; m_base = new T[m]; m_size = m;}template SqStack ::~SqStack(){ if (m_base != NULL) delete [] m_base;}template void SqStack ::Clear(){ m_top = 0;}template bool SqStack ::Empty() const{ return m_top == 0;}template int SqStack ::Length() const{ return m_top;}template T& SqStack ::Top() const{ if (m_top != 0) { return m_base[m_top-1]; }}template void SqStack ::Push(const T& e){ if (m_top >= m_size) { T* newbase = new T[m_size+10]; for (int i = 0; i < m_size; i++) { newbase[i] = m_base[i]; } delete [] m_base; m_base = newbase; m_size += 10; } m_base[m_top++] = e;}template void SqStack ::Pop(){ m_top--;}#endif
3 用链式存储结构实现的栈成为链栈。当栈非空时，top指向栈顶元素结点；而当栈为空时，top为空指针。链栈的实现：
//LinkStack.h#ifndef _LINKSTACK_#define _LINKSTACK_template struct LinkNode{ T data; LinkNode * next;};template class LinkStack{public: LinkStack(); ~LinkStack(); void Clear(); int Length() const; bool Empty() const; T& Top() const; void Push(const T&); void Pop();private: LinkNode *top;};template LinkStack ::LinkStack(){ top = NULL;}template LinkStack ::~LinkStack(){ Clear();}template void LinkStack ::Clear(){ LinkNode * p; while(top) { p = top; top = top->next; delete p; }}template bool LinkStack ::Empty() const{ return top == NULL;}template int LinkStack ::Length() const{ LinkNode * p = top; int i = 0; while (p) { i++; p = p->next; } return i;}template T& LinkStack ::Top() const{ if (top) { return top->data; }}template void LinkStack ::Push(const T& e){ LinkNode * p = new LinkNode ; p->data = e; p->next = top; top = p;}template void LinkStack ::Pop(){ LinkNode * p = top; top = top->next; delete p;}#endif
4 栈的应用
4.1 回文判断。
所谓回文，是指一个字符串的字符序列（不包括空格）顺读和逆读是一样的。例如“dad”，"noon"都是回文。程序实现如下：
#include #include "SqStack.h"#include "LinkStack.h"using namespace std;#define MAX_STRING_LEN 100bool ispalindrome(char*);void main(int argc, char* argv[]){ char instring[MAX_STRING_LEN]; cin.getline(instring,MAX_STRING_LEN); if (ispalindrome(instring)) { cout<<"YES"< s(MAX_STRING_LEN); char deblankstring[MAX_STRING_LEN],c; int i = 0; while (*in_string) { if (*in_string != ' ') { deblankstring[i++] = *in_string; } in_string++; } deblankstring[i] = '\0'; i = 0; while (deblankstring[i]) { s.Push(deblankstring[i++]); } int k = 0; while (!s.Empty()) { c = s.Top(); s.Pop(); if (c != deblankstring[k++]) { return false; } } return true;}
4.2 迷宫问题
#include #include "SqStack.h"#include using namespace std;#define MAXSIZE 30struct PosType{ int x; //行 int y; //列};struct DataType{ PosType seat; //位置 int di; //方向};class Maze{public: Maze(int, int); ~Maze(); bool MazePath(PosType, PosType); void Input(); void Print();private: PosType NextPos(PosType, int); int ** m_maze; int m_row; int m_col;};Maze::Maze(int m, int n){ m_row = m + 2; m_col = n + 2; m_maze = new int*[m_row]; for (int i = 0; i < m_row; i++) { m_maze[i] = new int[m_col]; }}Maze::~Maze(){ for (int i = 0; i < m_row; i++) { if (m_maze[i] != NULL) { delete [] m_maze[i]; } } if (m_maze != NULL) { delete [] m_maze; }}bool Maze::MazePath(PosType start, PosType end){ SqStack path(MAXSIZE); PosType curpos; DataType e; curpos = start; int curstep = 1; do { if (m_maze[curpos.x][curpos.y] == 0) { m_maze[curpos.x][curpos.y] = curstep; e.seat.x = curpos.x; e.seat.y = curpos.y; e.di = 0; path.Push(e); curstep++; if (curpos.x == end.x && curpos.y == end.y) //达到终点 { return true; } curpos = NextPos(curpos, e.di); } else { if (!path.Empty()) { e = path.Top(); path.Pop(); curstep--; while (e.di == 3 && !path.Empty()) { m_maze[e.seat.x][e.seat.y] = -1; //留下不能通过的标记 e = path.Top(); //退回一步 path.Pop(); curstep--; } if (e.di < 3) //没到最后一个方向 { e.di++; //换下一个方向搜索 path.Push(e); curstep++; curpos = NextPos(e.seat,e.di); } } } } while (!path.Empty()); return false;}void Maze::Input(){ int i,j; ifstream input("input.txt"); cout<<"请输入"< <<"*"< <<"的迷宫:"< >m_maze[i][j]; } } for (i = 0; i < m_row; i++) { m_maze[i][0] = 1; m_maze[i][m_col-1] = 1; } for (j = 0; j < m_col; j++) { m_maze[0][j] = 1; m_maze[m_row-1][j] = 1; }}void Maze::Print(){ int i, j; for (i = 0; i < m_row; i++) { for (j = 0; j < m_col; j++) { if (m_maze[i][j] >= 0 && m_maze[i][j] < 10) { cout<<" "< >m>>n; Maze maze(m,n); maze.Input(); maze.Print(); cout<<"请输入入口位置（行数，列数）"; cin>>begin.x>>begin.y; cout<<"请输入出口位置（行数，列数）"; cin>>end.x>>end.y; bool b = maze.MazePath(begin, end); if (b) { cout<<"此迷宫从入口到出口的一条路径如下："<
4.3 表达式求值，例如求取表达式“7+(9-12/3)*4=”的值。
#include #include "SqStack.h"#include using namespace std;#define MaxExpLength 100char ops[7] = {'+','-','*','/','(',')','='};char cmp[7][7] = { {'>','>','<','<','<','>','>'}, {'>','>','<','<','<','>','>'}, {'>','>','>','>','<','>','>'}, {'>','>','>','>','<','>','>'}, {'<','<','<','<','<','=',' '}, {'>','>','>','>',' ','>','>'}, {'<','<','<','<','<',' ','='}};//判断ch是否为运算符bool IsOperator(char ch){ for (int i = 0; i < 7; i++) { if (ch == ops[i]) { return true; } } return false;}//比较运算符的优先级char Compare(char ch1, char ch2){ char priority; int m,n; for (int i = 0; i < 7; i++) { if (ch1 == ops[i]) { m = i; } if (ch2 == ops[i]) { n = i; } } priority = cmp[m][n]; return priority;}//计算z=x y，若除数为0，则返回falsebool Compute(double x, char op, double y, double& z){ switch (op) { case '+': z = x + y; break; case '-': z = x - y; break; case '*': z = x * y; break; case '/': if (y != 0.0) { z = x / y; break; } else { cout<<"除数为0，出错！"< optr(20); SqStack opnd(20); optr.Push('='); ch = str[i++]; while (ch != '=' || optr.Top() != '=') { while (ch == ' ') { ch = str[i++]; } if (IsOperator(ch)) //ch是操作符 { switch(Compare(optr.Top(), ch)) { case '<': optr.Push(ch); ch = str[i++]; break; case '=': optr.Pop(); ch = str[i++]; break; case '>': op = optr.Top(); optr.Pop(); b = opnd.Top(); opnd.Pop(); a = opnd.Top(); opnd.Pop(); if (Compute(a,op,b,v)) { opnd.Push(v); break; } else { result = 0; return false; } } } else //ch是数字 { temp = ch - '0'; ch = str[i++]; while (!IsOperator(ch) && ch != ' ') { temp = temp * 10 + ch - '0'; ch = str[i++]; } opnd.Push(temp); } } result = opnd.Top(); return true;}void main(int argc, char* argv[]){ int i = 0; double result; char* str; cout<<"请输入一个正确的四则表达式（以\"=\"结束，运算符为正整数）："< >str[i]; while (str[i] != '=') { input>>str[++i]; } if (ExpEvaluation(str, result)) { cout<<"表达式的值是"< <
4.4 汉诺塔问题
汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
#include #include using namespace std;int times;//将第n个圆盘从x柱移到z柱void move(int n, char x, char z){ cout<<"第"<<++times<<"步，将"< <<"号盘从"< <<"移到"< < >n; hanoi(n, 'a', 'b', 'c'); system("pause");}