第四章 堆栈与队列
堆栈（stack）是一组类型相同数据的组合（如数组）。具有先进后出的特性，所有的操作都在栈顶进行。
“heap和stack区别：1、heap是堆，stack是栈；2、stack的空间由操作系统自动分配和释放，heap的空间是手动申请和释放的；3、stack空间有限，heap的空间是很大的*区。”
stack相对速度快。
//
// Ch04_01
//
#include <iostream>
#include <iomanip>
#define MAXSTACK 100 //定义堆栈的最大容量
using namespace std;
int stack[MAXSTACK]; //声明用于堆栈操作的数组
int top=-1; //堆栈的顶端
//判断是否为空堆栈
int isEmpty()
{
if(top==-1) return 1;
else return 0;
}
//将指定的数据压入堆栈
int push(int data)
{
if(top>=MAXSTACK)
{
cout<<"堆栈已满,无法再压入"<<endl;
return 0;
}
else
{
stack[++top]=data; //将数据压入堆栈
return 1;
}
}
//从堆栈弹出数据
int pop()
{
if(isEmpty()) //判断堆栈是否为空,如果是则返回-1
return -1;
else
return stack[top--]; //将数据弹出后,再将堆栈指针往下移
}
//主程序
int main(void)
{
int value;
int i;
cout<<"请按序输入10个数据:"<<endl;
for(i=0;i<10;i++)
{
cin>>value;
push(value);
}
cout<<"===================="<<endl;
while(!isEmpty()) //将数据陆续从顶端弹出
cout<<"堆栈弹出的顺序为:"<<setw(2)<<pop()<<endl;
cout<<"===================="<<endl;
system("pause");
return 0;
}
//
// Ch04_02
//
#include <iostream>
#include <iomanip>
#include <ctime>
#include <cstdlib>
using namespace std;
void Swap(int*,int*);
void push(int statck[],int MAX,int val);
int pop(int stack[]);
int top=-1;
int main(void)
{
int card[52],stack[52]={0};
int i,j,k=0, ascVal;
char suit[4][10]={"草花","方块","红桃","黑桃"};
int style;
srand((unsigned)time(NULL));
for (i=0;i<52;i++)
card[i]=i+1;
cout<<"[洗牌中...请稍后!]"<<endl;
while(k<30)
{
for(i=0;i<51;i++)
for(j=i+1;j<52;j++)
if(rand()%52==2)
Swap(&card[i],&card[j]);//洗牌
k++;
}
i=0;
while(i!=52)
{
push(stack,52,card[i]);//将52张牌压入堆栈
i++;
}
cout<<"[逆时针发牌]"<<endl;
cout<<"[显示各家拿到的牌]"<<endl;
cout<<"\t\t东家\t 北家\t 西家\t 南家"<<endl;
cout<<"========================================================="<<endl;
while (top >=0)
{
style = stack[top]/13; //计算扑克牌的花色
switch(style) //扑克牌花色对应的图标
{
case 0: //梅花
ascVal=0;
break;
case 1: //方块
ascVal=1;
break;
case 2: //红心
ascVal=2;
break;
case 3: //黑桃
ascVal=3;
break;
}
cout<<"["<<suit[ascVal]<<setw(3)<<stack[top]%13+1<<"]\t";
if(top%4==0)
cout<<endl;
top--;
}
system("pause");
return 0;
}
void push(int stack[],int MAX,int val)
{
if(top>=MAX-1)
cout<<"[堆栈已经满了]"<<endl;
else
{
top++;
stack[top]=val;
}
}
int pop(int stack[])
{
if(top<0)
cout<<"[堆栈已经空了]"<<endl;
else
top--;
return stack[top];
}
void Swap(int* a,int* b)
{
int temp;
temp=*a;
*a=*b;
*b=temp;
}
//
// Ch04_03
//
#include <iostream>
#include <cstdlib>
#include <iomanip>
using namespace std;
class Node //声明堆栈链表节点
{
public:
int data; //声明存放堆栈数据的变量
class Node *next; //堆栈中用来指向下一个节点的指针
};
typedef class Node Stack_Node; //定义堆栈中节点的新类型
typedef Stack_Node *Linked_Stack; //定义链表堆栈的新类型
Linked_Stack top=NULL; //指向堆栈顶端的指针
//判断是否为空堆栈
int isEmpty()
{
if(top==NULL) return 1;
else return 0;
}
//将指定的数据压入堆栈
void push(int data)
{
Linked_Stack new_add_node; //新加入节点的指针
//分配内存给新节点
new_add_node=new Stack_Node;
new_add_node->data=data; //将传入的值赋值给节点的数据变量
new_add_node->next=top; //将新节点指向堆栈的顶端
top=new_add_node; //新节点成为堆栈的顶端
}
//从堆栈弹出数据
int pop()
{
Linked_Stack ptr; //指向堆栈顶端的指针
int temp;
if(isEmpty()) //判断堆栈是否为空,如果是则返回-1
{
cout<<"===目前为空堆栈==="<<endl;
return -1;
}
else
{
ptr=top; //指向堆栈的顶端
top=top->next; //将堆栈顶端的指针指向下一个节点
temp=ptr->data; //取出堆栈的数据
free(ptr); //将节点占用的内存释放
return temp; //将从堆栈取出的数据返回给主程序
}
}
//主程序
int main(void)
{
int value;
int i;
cout<<"请按序输入10个数据:"<<endl;
for(i=0;i<10;i++)
{
cin>>value;
push(value);
}
cout<<"===================="<<endl;
while(!isEmpty()) //将数据陆续从顶端弹出
cout<<"堆栈弹出的顺序为:"<<setw(2)<<pop()<<endl;
cout<<"===================="<<endl;
system("pause");
return 0;
}
//
// Ch04_04
//
#include <iostream>
#include <cstdlib>
using namespace std;
template <class Type> // 定义链表中的节点
struct Node
{
Type data; // 记录数据
Node* next;// 记录下一笔节点的地址
};
template <class Type>
class LinkedList // 链表类型
{
private:
Node<Type>* first; // 指到第一个节点的指针
public:
LinkedList() // 构造函数
{
first = NULL;
}
void addNode(Type data); // 加入节点
void display(); // 显示所有的节点
};
template<class Type>
void LinkedList<Type>::addNode(Type data)
{
Node<Type>* newNode = new Node<Type>; // 新增一个节点
newNode->data = data; // 记录数据
newNode->next = first; // 指向前一个节点
first = newNode; // 指向新的节点
}
template<class Type>
void LinkedList<Type>::display()
{
Node<Type>* currentNode = first; // 从第一个节点开始显示
while( currentNode != NULL )
{
cout << currentNode->data << " -> ";
currentNode = currentNode->next;
}
}
int main()
{
LinkedList<double> dblList; // 建立一个存储double类型数据的链表
double num; // 记录输入的数据
char ch; // 记录用户的选择
do{
cout << endl <<"请输入一个数字 : ";
cin >> num;
dblList.addNode( num );
cout << "继续输入(y / n)?";
cin >> ch;
}while( ch != 'n' );
cout << endl;
dblList.display(); // 显示所有的数据
cout << endl << endl;
system("pause");
return 0;
}
//
// Ch04_05
//
#include <iostream>
#include <cstdlib>
using namespace std;
// 设定类样版的类型参数Type的默认值为整数int,非类型参数的类型为整数int,默认值为5
template <class Type = int, int size = 5> // 声明类样板
class Stack
{
private:
Type st[size]; // 声明一数组作为堆栈的存储空间
int top; // 堆栈数据顶端的索引
public:
Stack()
{
top = -1;
}
void push(Type data); // 将数据压入堆栈
Type pop(); // 将数据从堆栈中弹出
};
template < class Type, int size >
void Stack< Type, size > :: push ( Type data )
{
st[ ++top ] = data;
}
template < class Type, int size >
Type Stack<Type, size> :: pop()
{
return st[ top-- ];
}
int main()
{
Stack<> stk_1; // 声明一个堆栈对象, 并使用其默认值
Stack<char*, 4> stk_2; // 声明堆栈对象, 其类型为字符串, 大小为4
stk_1.push( 11 );
stk_1.push( 22 );
stk_1.push( 33 );
cout << "stack_1 [1] = " << stk_1.pop() << endl;
cout << "stack_1 [2] = " << stk_1.pop() << endl;
cout << "stack_1 [3] = " << stk_1.pop() << endl;
cout << endl;
stk_2.push( "第一名" );
stk_2.push( "第二名" );
stk_2.push( "第三名" );
cout << "stack_2 [1] = " << stk_2.pop() << endl;
cout << "stack_2 [2] = " << stk_2.pop() << endl;
cout << "stack_2 [3] = " << stk_2.pop() << endl;
cout << endl;
system("pause");
return 0;
}
//
// Ch04_06
//
#include <iostream>
#define EAST MAZE[x][y+1] //定义东方的相对位置
#define WEST MAZE[x][y-1] //定义西方的相对位置
#define SOUTH MAZE[x+1][y] //定义南方的相对位置
#define NORTH MAZE[x-1][y] //定义北方的相对位置
using namespace std;
const int ExitX = 8; //定义出口的X坐标在第8行
const int ExitY = 10; //定义出口的Y坐标在第10列
struct list
{
int x,y;
struct list* next;
};
typedef struct list node;
typedef node* link;
int MAZE[10][12] = { 1,1,1,1,1,1,1,1,1,1,1,1, //声明迷宫数组
1,0,0,0,1,1,1,1,1,1,1,1,
1,1,1,0,1,1,0,0,0,0,1,1,
1,1,1,0,1,1,0,1,1,0,1,1,
1,1,1,0,0,0,0,1,1,0,1,1,
1,1,1,0,1,1,0,1,1,0,1,1,
1,1,1,0,1,1,0,1,1,0,1,1,
1,1,1,1,1,1,0,1,1,0,1,1,
1,1,0,0,0,0,0,0,1,0,0,1,
1,1,1,1,1,1,1,1,1,1,1,1};
link push(link stack,int x,int y);
link pop(link stack,int* x,int* y);
int chkExit(int ,int ,int,int);
int main(void)
{
int i,j;
link path = NULL;
int x=1; //入口的X坐标
int y=1; //入口的Y坐标
cout<<"[迷宫的路径(0的部分)]"<<endl; //打印出迷宫的路径图
for(i=0;i<10;i++)
{
for(j=0;j<12;j++)
cout<<MAZE[i][j]<<" ";
cout<<endl;
}
while(x<=ExitX&&y<=ExitY)
{
MAZE[x][y]=2;
if(NORTH==0)
{
x -= 1;
path=push(path,x,y);
}
else if(SOUTH==0)
{
x+=1;
path=push(path,x,y);
}
else if(WEST==0)
{
y-=1;
path=push(path,x,y);
}
else if(EAST==0)
{
y+=1;
path=push(path,x,y);
}
else if(chkExit(x,y,ExitX,ExitY)==1) //检查是否走到出口了
break;
else
{
MAZE[x][y]=2;
path=pop(path,&x,&y);
}
}
cout<<"[老鼠走过的路径(2的部分)]"<<endl; //打印出老鼠成功走出迷宫的路径图
for(i=0;i<10;i++)
{
for(j=0;j<12;j++)
cout<<MAZE[i][j]<<" ";
cout<<endl;
}
system("pause");
return 0;
}
link push(link stack,int x,int y)
{
link newnode;
newnode = new node;
if(!newnode)
{
cout<<"Error!内存分配失败!"<<endl;
return NULL;
}
newnode->x=x;
newnode->y=y;
newnode->next=stack;
stack=newnode;
return stack;
}
link pop(link stack,int* x,int* y)
{
link top;
if(stack!=NULL)
{
top=stack;
stack=stack->next;
*x=top->x;
*y=top->y;
delete top;
return stack;
}
else
*x=-1;
return stack;
}
int chkExit(int x,int y,int ex,int ey)
{
if(x==ex&&y==ey)
{
if(NORTH==1||SOUTH==1||WEST==1||EAST==2)
return 1;
if(NORTH==1||SOUTH==1||WEST==2||EAST==1)
return 1;
if(NORTH==1||SOUTH==2||WEST==1||EAST==1)
return 1;
if(NORTH==2||SOUTH==1||WEST==1||EAST==1)
return 1;
}
return 0;
}
//
// Ch04_07
//
#include <iostream>
#include <iomanip>
#include <cmath>
#define EIGHT 8 //定义堆栈的最大容量
#define TRUE 1
#define FALSE 0
using namespace std;
int queen[EIGHT]; //存放8个皇后的行位置
int number=0; //计算总共有几组解
//决定皇后存放的位置
//输出所需要的结果
int attack(int ,int);
void print_table()
{
int x=0,y=0;
number+=1;
cout<<endl;
cout<<"八皇后问题的第"<<setw(2)<<number<<"组解"<<endl<<"\t";
for(x=0;x<EIGHT;x++)
{
for(y=0;y<EIGHT;y++)
if(x==queen[y])
cout<<"<q>";
else
cout<<"<->";
cout<<endl<<"\t";
}
system("pause");
}
void decide_position(int value)
{
int i=0;
while(i<EIGHT)
{
//是否受到攻击的判断语句
if(attack(i,value)!=1)
{
queen[value]=i;
if(value==7)
print_table();
else
decide_position(value+1);
}
i++;
}
}
//测试在(row, col)上的皇后是否遭受攻击
//若遭受攻击则返回值为1,否则返回0
int attack(int row,int col)
{
int i=0,atk=FALSE;
int offset_row=0,offset_col=0;
while((atk!=1)&&i<col)
{
offset_col=abs(i-col);
offset_row=abs(queen[i]-row);
//判断两皇后是否在同一行或在同一对角线
if((queen[i]==row)||(offset_row==offset_col))
atk=TRUE;
i++;
}
return atk;
}
//主程序
int main(void)
{
decide_position(0);
return 0;
}
/*
// Ch04_08
[示范]:将数学表达式由中序表示法转为后序表示法
*/
#include <iostream>
#include <cstdlib>
#include <iomanip>
using namespace std;
#define MAX 50
char infix_q[MAX]; //用来存放中序表示法的队列
//运算符优先级的比较，若输入运算符的优先级小于堆栈中运算符的优先级，
//则返回值为1，否则为0
int compare(char stack_o, char infix_o)
{
//在中序表示法队列和暂存堆栈中，运算符的优先级表，
//其优先级值为INDEX/2
char infix_priority[9] ;
char stack_priority[8] ;
int index_s=0, index_i=0;
infix_priority[0]='q';infix_priority[1]=')';
infix_priority[2]='+';infix_priority[3]='-';
infix_priority[4]='*';infix_priority[5]='/';
infix_priority[6]='^';infix_priority[7]=' ';
infix_priority[8]='(';
stack_priority[0]='q';stack_priority[1]='(';
stack_priority[2]='+';stack_priority[3]='-';
stack_priority[4]='*';stack_priority[5]='/';
stack_priority[6]='^';stack_priority[7]=' ';
while (stack_priority[index_s] != stack_o)
index_s++;
while (infix_priority[index_i] != infix_o)
index_i++;
return ((int)(index_s/2) >= (int)(index_i/2) ? 1 : 0);
}
//中序转前序的方法
void infix_to_postfix()
{
int rear=0, top=0, flag=0,i=0;
char stack_t[MAX];
for (i=0; i<MAX; i++)
stack_t[i]='\0';
gets(infix_q);
i=0;
while(infix_q[i]!='\0')
{
i++;
rear++;
}
infix_q[rear] = 'q'; //在队列加入q为结束符号
cout<<"\t"<<"后序表示法 : ";
stack_t[top] = 'q'; //在堆栈加入q为结束符号
for (flag = 0; flag <= rear; flag++)\
{
switch (infix_q[flag])
{
//输入为)时，则输出堆栈内的运算符，直到堆栈内为(
case ')':
while(stack_t[top]!='(')
cout<<setw(1)<<stack_t[top--];
top--;
break;
//输入为q，则将堆栈内还未输出的运算符输出
case 'q':
while(stack_t[top]!='q')
cout<<setw(1)<<stack_t[top--];
break;
//输入为运算符，若其优先级小于TOP在堆栈中所指运算符的优先级，
//则将堆栈所指运算符输出，若优先级大于等于TOP在堆栈中所指运算符
//的优先级，则将输入的运算符压入堆栈。
case '(':
case '^':
case '*':
case '/':
case '+':
case '-':
while (compare(stack_t[top], infix_q[flag])==1)
cout<<setw(1)<<stack_t[top--];
stack_t[++top] = infix_q[flag];
break;
//输入为操作数，则直接输出
default :
cout<<setw(1)<<infix_q[flag];
break;
}
}
}
//主函数声明
int main (void)
{
int i=0;
for (i=0; i<MAX; i++)
infix_q[i]='\0';
cout<<"\t=========================================="<<endl;
cout<<"\t本程序会将其转成后序法表达式"<<endl;
cout<<"\t请输入中序法表达式"<<endl;
cout<<"\t例如:(9+3)*8+7*6-8/4 "<<endl;
cout<<"\t可以使用的运算符包括:^,*,+,-,/,(,)等 "<<endl;
cout<<"\t=========================================="<<endl;
cout<<"\t请开始输入中序法表达式: ";
infix_to_postfix();
cout<<endl;
cout<<"\t=========================================="<<endl;
system("pause");
return 0;
}
/*
// Ch04_09
[示范]:实现队列数据的进队和出队
*/
#include <iostream>
using namespace std;
const int MAX=20;//定义队列的大小
int main(void)
{
int front,rear,val,queue[MAX]={0};
char ch;
front=rear=-1;
while(rear<MAX-1&&ch!='E')
{
cout<<"[I]存入一个数值 [G]取出一个数值 [E]结束: ";
cin>>ch;
switch(ch)
{
case 'I':
cout<<"[请输入数值]: ";
cin>>val;
rear++;
queue[rear]=val;
break;
case 'G':
if(rear>front)
{
front++;
cout<<"[取出数值为]: ["<<queue[front]<<"]";
cout<<endl;
queue[front]=0;
}
else
{
cout<<"[队列已经空了]"<<endl;
exit(0);
}
break;
default:
cout<<endl;
break;
}
}
if(rear==MAX-1) cout<<"[队列已经满了]"<<endl;
cout<<"[目前队列中的数据]:";
if (front>=rear)
{
cout<<"没有"<<endl;
cout<<"[队列已经空了]"<<endl;
}
else
{
while (rear>front)
{
front++;
cout<<"["<<queue[front]<<"]\t";
}
cout<<endl;
}
system("pause");
return 0;
}
/*
// Ch04_10
[示范]:以链表来实现队列
*/
#include <iostream>
#include <cstdlib>
#include <iomanip>
using namespace std;
class Node
{
public:
int data;
class Node *next;
};
typedef class Node QueueNode;
typedef QueueNode *QueueByLinkedList;
QueueByLinkedList front=NULL;
QueueByLinkedList rear=NULL;
//方法enqueue:数据的加入队列
void enqueue(int value) {
QueueByLinkedList node; //建立节点
node=new QueueNode;
node->data=value;
node->next=NULL;
//检查是否为空队列
if (rear==NULL)
front=node; //新建立的节点成为第1个节点
else
rear->next=node; //将节点加入到队列的末尾
rear=node; //将队列的末尾指针指向新加入的节点
}
//方法dequeue:从队列取出数据
int dequeue()
{
int value;
//检查队列是否为空队列
if (!(front==NULL))
{
if(front==rear) rear=NULL;
value=front->data; //从队列取出数据
front=front->next; //将队列的前端指针指向下一个
return value;
}
else return -1;
}
int main(void)
{
int temp;
cout<<" 以链表来实现队列"<<endl;
cout<<"===================================="<<endl;
cout<<"在队列前端加入第1个数据，此数据值为1"<<endl;
enqueue(1);
cout<<"在队列前端加入第2个数据，此数据值为3"<<endl;
enqueue(3);
cout<<"在队列前端加入第3个数据，此数据值为5"<<endl;
enqueue(5);
cout<<"在队列前端加入第4个数据，此数据值为7"<<endl;
enqueue(7);
cout<<"在队列前端加入第5个数据，此数据值为9"<<endl;
enqueue(9);
cout<<"===================================="<<endl;
while (1)
{
if (!(front==NULL))
{
temp=dequeue();
cout<<"从队列前端按序取出的元素数据值为："<<setw(1)<<temp<<endl;
}
else
break;
}
cout<<endl;
system("pause");
return 0;
}
/*
// Ch04_11
[示范]：实现环状队列数据的进队和出队
*/
#include <iostream>
using namespace std;
int main(void)
{
int front,rear,val=0,queue[5]={0};
front=rear=-1;
while(rear<5&&val!=-1)
{
cout<<"请输入一个值以存入队列，欲取出值请输入-2。(结束输入-1)：";
cin>>val;
if(val==-2)
{
if(front==rear)
{
cout<<"[队列已经空了]"<<endl;
break;
}
front++;
if (front==5)
front=0;
cout<<"取出队列值 ["<<queue[front]<<"]"<<endl;
queue[front]=0;
}
else if(val!=-1 && rear<5)
{
if(rear+1==front || rear==4 && front<=0)
{
cout<<"[队列已经满了]"<<endl;
break;
}
rear++;
if(rear==5)
rear=0;
queue[rear]=val;
}
}
cout<<"\n队列剩余数据："<<endl;
if (front==rear)
cout<<"队列已空!!"<<endl;
else
{
while(front!=rear)
{
front++;
if (front==5)
front=0;
cout<<"["<<queue[front]<<"]";
queue[front]=0;
}
}
cout<<endl;
system("pause");
return 0;
}
/*
// Ch04_12
[示范]：实现双向队列
*/
#include <iostream>
#include <cstdlib>
#include <iomanip>
using namespace std;
class Node
{
public:
int data;
class Node *next;
};
typedef class Node QueueNode;
typedef QueueNode *QueueByLinkedList;
QueueByLinkedList front=NULL;
QueueByLinkedList rear=NULL;
//方法enqueue: 数据加入队列
void enqueue(int value)
{
QueueByLinkedList node; //建立节点
node=new QueueNode;
node->data=value;
node->next=NULL;
//检查是否为空队列
if (rear==NULL)
front=node;//新建立的节点成为第1个节点
else
rear->next=node;//将节点加入到队列的末尾
rear=node;//将队列的队尾指针指向新加入的节点
}
//方法dequeue:从队列取出数据
int dequeue(int action)
{
int value;
QueueByLinkedList tempNode,startNode;
//从队首取出数据
if (!(front==NULL) && action==1)
{
if(front==rear) rear=NULL;
value=front->data;//将队列数据从队首取出
front=front->next;//将队列的队首指针指向下一个
return value;
}
//从队尾取出数据
else if(!(rear==NULL) && action==2)
{
startNode=front;//先记下队首的指标值
value=rear->data;//取出当前队尾的数据
//寻找最末尾节点的前一个节点
tempNode=front;
while (front->next!=rear && front->next!=NULL)
{
front=front->next;
tempNode=front;
}
front=startNode;//记录从队尾取出数据后的队列队首指针
rear=tempNode;//记录从队尾取出数据后的队列队尾指针
//下一行程序是指当队列中仅剩下最后一个节点时,
//取出数据后便将front和rear指向NULL
if ((front->next==NULL) || (rear->next==NULL))
{
front=NULL;
rear=NULL;
}
return value;
}
else return -1;
}
int main(void)
{
int temp;
cout<<"以链表来实现双向队列"<<endl;
cout<<"===================================="<<endl;
cout<<"在双向队列队首加入第1笔数据，此数据值为1"<<endl;
enqueue(1);
cout<<"在双向队列队首加入第2笔数据，此数据值为3"<<endl;
enqueue(3);
cout<<"在双向队列队首加入第3笔数据，此数据值为5"<<endl;
enqueue(5);
cout<<"在双向队列队首加入第4笔数据，此数据值为7"<<endl;
enqueue(7);
cout<<"在双向队列队首加入第5笔数据，此数据值为9"<<endl;
enqueue(9);
cout<<"===================================="<<endl;
temp=dequeue(1);
cout<<"从双向队列队首按序取出的元素数据值为："<<setw(1)<<temp<<endl;
temp=dequeue(2);
cout<<"从双向队列队尾按序取出的元素数据值为："<<setw(1)<<temp<<endl;
temp=dequeue(1);
cout<<"从双向队列队首按序取出的元素数据值为："<<setw(1)<<temp<<endl;
temp=dequeue(2);
cout<<"从双向队列队尾按序取出的元素数据值为："<<setw(1)<<temp<<endl;
temp=dequeue(1);
cout<<"从双向队列队首按序取出的元素数据值为："<<setw(1)<<temp<<endl;
cout<<endl;
system("pause");
return 0;
}