数据结构实验--栈和队列操作
#include<iostream>
#include <cstdlib>
using namespace std;
#define MAXSIZE 100 //顺序栈存储空间的初始分配量
typedef int SElemType; //栈元素类型
/*
****************************************顺序栈操作方法**********************************
*/
//顺序栈的存储结构
typedef struct
{
SElemType *base; //栈底指针
SElemType *top; //栈顶指针
int stacksize; //栈可用最大容量
} SqStack;
//销毁顺序栈
void DestroyStack(SqStack &S)
{
if(S.base)
{
delete []S.base;
S.stacksize=0;
S.base=S.top=NULL;
}
}
//1顺序栈初始化
void InitStack(SqStack &S)
{
//构造一个空栈S
S.base=new SElemType[MAXSIZE]; //为顺序栈动态分配一个最大容量为MAXSIZE的数组空间
if(!S.base)
{
cout<<"存储空间分配失败"<<endl;
exit(0); //异常退出
}
S.top=S.base; //top初始为base，空栈
S.stacksize=MAXSIZE; //stacksize置为栈的最大容量MAXSIZE
cout<<"顺序栈初始化成功"<<endl;
}
//2求顺序栈长度
int StackLength(SqStack S)
{
return S.top-S.base;
}
//3清空顺序栈
void ClearStack(SqStack &S)
{
if(S.base)
{
S.top=S.base;
cout<<"顺序栈已清空"<<endl;
}
}
//4取栈顶元素
void GetTop(SqStack S)
{
if(S.top==S.base)
cout<<"栈为空"<<endl;
else
cout<<"栈顶元素为:"<<*(S.top-1)<<endl;
}
//5入栈
void Push(SqStack &S,SElemType e)
{
//插入元素e为新的栈顶元素
if(S.top-S.base==S.stacksize)
cout<<"栈已满"<<endl;
else
{
*S.top++=e;
cout<<"元素"<<e<<"入栈成功"<<endl;
}
}
//6出栈
void Pop(SqStack &S,SElemType e)
{
//删除S的栈顶元素，用e返回其值
if(S.top==S.base)
cout<<"栈为空"<<endl;
else
{
e=*--S.top;
cout<<"元素"<<e<<"出栈成功"<<endl;
}
}
//7显示顺序栈元素
void DisplayStack(SqStack S)
{
if(S.top==S.base)
cout<<"栈为空"<<endl;
else
{
cout<<"栈底->";
SElemType *l = S.base;
while(l != S.top)
cout << *l++ << " ";
cout <<"->栈顶"<< endl;
}
}
//顺序栈操作选项
void Stackshow_help()
{
cout<<"\n******* Data Structure ******"<<endl;
cout<<"1----顺序栈初始化"<<endl;
cout<<"2----求顺序栈长度"<<endl;
cout<<"3----清空顺序栈"<<endl;
cout<<"4----取栈顶元素"<<endl;
cout<<"5----入栈"<<endl;
cout<<"6----出栈"<<endl;
cout<<"7----显示栈元素"<<endl;
cout<<" 退出，输入0"<<endl;
}
/*
****************************************链队列操作方法******************************
*/
typedef int QElemType; //队列元素类型
//链队列存储结构
typedef struct QNode
{
QElemType data;
struct QNode *next;
} QNode,*QueuePtr;
typedef struct
{
QueuePtr front; //头指针
QueuePtr rear; //尾指针
} LinkQueue;
//销毁队列
void DestroyQueue(LinkQueue &Q)
{
while(Q.front)
{
Q.rear=Q.front->next;
delete Q.front;
Q.front=Q.rear;
}
}
//1链队列初始化
void InitQueue(LinkQueue &Q)
{
Q.front=new QNode; //创建一个头结点
Q.rear=Q.front; //头尾指针都指向头结点
Q.front->next=NULL;
cout<<"链队列初始化成功"<<endl;
}
//2求链队列长度
int QueueLength(LinkQueue Q)
{
QNode *p1 = Q.front;
QNode *p2 = Q.rear;
int length = 0;
while(p1 != p2)
{
p1 = p1->next;
length++;
}
return length;
}
//3求链队列队头元素
void GetHead(LinkQueue Q)
{
if(Q.front==Q.rear)
cout<<"链队列为空"<<endl;
else
cout<<"队头元素为:"<<Q.front->next->data<<endl;;
}
//4入队
void EnQueue(LinkQueue &Q,QElemType e)
{
QNode *p=new QNode;
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
cout<<"元素"<<e<<"入队成功"<<endl;
}
//5出队
void DeQueue(LinkQueue &Q,QElemType e)
{
if(Q.front==Q.rear)
cout<<"链队列为空"<<endl;
else
{
QNode *p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p)
Q.rear=Q.front;
delete p; //释放被删结点
}
cout<<"元素"<<e<<"出队成功"<<endl;
}
//6输出队列元素
void DisplayQueue(LinkQueue Q)
{
if(Q.front==Q.rear)
cout<<"链队列为空"<<endl;
else
{
QNode *p =Q.front->next;
cout<<"队头->";
while (p)
{
cout<<p->data<<" ";
p = p->next;
}
cout<<"->队尾"<<endl;
}
}
//链队列操作选项
void Queueshow_help()
{
cout<<"\n******* Data Structure ******"<<endl;
cout<<"1----链队列初始化"<<endl;
cout<<"2----求链队列长度"<<endl;
cout<<"3----求链队列队头元素"<<endl;
cout<<"4----入队"<<endl;
cout<<"5----出队"<<endl;
cout<<"6----输出队列元素"<<endl;
cout<<" 退出，输入0"<<endl;
}
void show_choice()
{
cout<<"\n******* Data Option ******"<<endl;
cout<<"1----顺序栈操作"<<endl;
cout<<"2----链队列操作"<<endl;
cout<<"0----退出"<<endl;
}
int main()
{
char operate_code,choice; //choice表示选择栈操作还是队列操作
while(1)
{
show_choice();
cout<<"选择操作选项: ";
cin>>choice;
if(choice=='1') //***********************顺序栈操作******************************8
{
SElemType e;
SqStack S; //定义栈变量
Stackshow_help();
while(1)
{
cout<<"输入要执行的顺序栈操作：";
cin>>operate_code;
if(operate_code=='1')
{
InitStack(S);
continue;
}
else if (operate_code=='2')
{
cout<<"顺序栈长度为："<<StackLength(S)<<endl;
continue;
}
else if (operate_code=='3')
{
ClearStack(S);
continue;
}
else if (operate_code=='4')
{
GetTop(S);
continue;
}
else if (operate_code=='5')
{
cout<<"请输入入栈元素:";
cin>>e;
Push(S,e);
continue;
}
else if (operate_code=='6')
{
Pop(S,e);
continue;
}
else if(operate_code=='7')
{
DisplayStack(S);
continue;
}
else if (operate_code=='0')
{
break;
}
else
{
cout<<"\n操作码错误！！！"<<endl;
Stackshow_help();
}
}
DestroyStack(S);
}
else if(choice=='2') //************************链队列操作***********************************
{
QElemType e;
LinkQueue Q; //定义链队列变量
Queueshow_help();
while(1)
{
cout<<"输入要执行的链队列操作：";
cin>>operate_code;
if(operate_code=='1')
{
InitQueue(Q);
continue;
}
else if (operate_code=='2')
{
cout<<"链队列长度为："<<QueueLength(Q)<<endl;
continue;
}
else if (operate_code=='3')
{
GetHead(Q);
continue;
}
else if (operate_code=='4')
{
cout<<"请输入入队元素:";
cin>>e;
EnQueue(Q,e);
continue;
}
else if (operate_code=='5')
{
DeQueue(Q,e);
continue;
}
else if (operate_code=='6')
{
DisplayQueue(Q);
continue;
}
else if (operate_code=='0')
{
break;
}
else
{
cout<<"\n操作码错误！！！"<<endl;
Queueshow_help();
}
}
DestroyQueue(Q);
}
else if(choice=='0') //***********************退出程序***********************8
{
break;
}
}
return 0;
}