实验二 栈和队列的基本操作
一、实验目的
1.掌握栈与队列的数据类型描述及特点；
2.掌握栈和队列的存储；
3.掌握栈的顺序和链式存储存表示与入栈、出栈操作的程序实现；
4. 掌握队列的链式存储表示与入队、出队基本操作算法实现。
二、实验用软件和工具
实验软件 VC++ 6.0
三、实验步骤
1.根据栈数据结构，分别建立一个顺序栈和链式栈并实现其上基本操作（出栈和入栈等）,定义一个顺序栈和链栈结构体（队列结构体）。
2.利用入栈功能保存数据。
3.利用出栈删除弹出栈内信息。
4.根据队列数据结构，分别建立链队列和循环队列，并完成其上的基本操作（出入队列等）,利用入队功能保存数据。
5.利用出队删除队列信息。
四、实验程序与程序运行结果
顺序栈程序：
sxz.h
#include <iostream>
using namespace std;
template <class T>
class sq_Stack
{private:
int mm;
int top;
T *s;
public:
sq_Stack(int);
void prt_sq_Stack();
void ins_sq_Stack(T x);
T del_sq_Stack();
T read_sq_Stack();
};
template <class T>
sq_Stack<T>::sq_Stack(int m)
{
mm=m;
s = new T[mm];
top=0;
return;
}
template <class T>
void sq_Stack<T>::prt_sq_Stack()
{
int i;
cout<<"top="<<top<<endl;
for (i=top;i>0;i--) cout<<s[i-1]<<endl;
return;
}
template <class T>
void sq_Stack<T>::ins_sq_Stack(T x)
{
if (top==mm)
{cout<<"overflow!"<<endl; return;}//存储空间已满，上溢错误
top=top+1; //
s[top-1]=x; //插入新元素
return;
}
template<class T>
T sq_Stack<T>::del_sq_Stack()
{
T y;
if(top==0) //空，下溢错误
{cout<<"underflow!"<<endl; return(0);}
y=s[top-1]; //
top=top-1; //长度减1
return(y);
}
template<class T>
T sq_Stack<T>::read_sq_Stack()
{
if(top==0) //空，下溢错误
{cout<<"underflow!"<<endl; return(0);}
return(s[top-1]);
}
sxz.cpp
#include "sq_Stack.h"
int main()
{
sq_Stack<int> s(10);
s.ins_sq_Stack(50);
s.ins_sq_Stack(60);
s.ins_sq_Stack(70);
s.ins_sq_Stack(80);
s.ins_sq_Stack(90);
s.ins_sq_Stack(100);
cout<<"第1次输出栈顶指针与栈中的元素:"<<endl;
s.prt_sq_Stack();
cout<<"输出栈顶元素:"<<s.read_sq_Stack()<<endl;
cout<<"输出退栈的元素:"<<endl;
cout<<s.del_sq_Stack()<<endl;
cout<<s.del_sq_Stack()<<endl;
cout<<s.del_sq_Stack()<<endl;
cout<<"再输出栈顶指针与栈中的元素:"<<endl;
s.prt_sq_Stack();
return 0;
}
顺序队列程序：
sq_Queue.h
#include <iostream>
using namespace std;
template <class T>
class sq_Queue
{private:
int mm;
int front;
int rear;
int s;
T *q;
public:
sq_Queue(int) ;
void prt_sq_Queue();
void ins_sq_Queue(T x);
T del_sq_Queue();
};
template <class T>
sq_Queue<T>::sq_Queue(int m)
{
mm=m;
q = new T[mm];
front=mm;
rear=mm;
s=0;
return;
}
template <class T>
void sq_Queue<T>::prt_sq_Queue()
{
int i;
cout<<"front="<<front<<endl;
cout<<"rear="<<rear<<endl;
if ((s==0)&&(rear==front))
{cout<<"队列空!"<<endl; return;}
i=front;
if (front>=mm)
front=i%mm ;
for (i=front; i<rear;i++)
{ cout<<q[i]<<endl;}
return;
}
template <class T>
void sq_Queue<T>::ins_sq_Queue(T x)
{
if ((s==1)&&(rear==front))
{cout<<"Queue_overflow!"<<endl; return;}//存储空间已满，上溢错误
rear=rear+1; //
if (rear==mm+1)
rear=1;
q[rear-1]=x; //插入新元素
s=1;
return;
}
template <class T>
T sq_Queue<T>::del_sq_Queue()
{
T y;
if (s=0)
{cout<<"Queue_underflow!"<<endl; return(0);}//存储空间已满，上溢错误
front=front+1; //
if (front==mm+1)
front=1;
y=q[front-1]; //插入新元素
if (rear==front)
s=0;
return(y);
}
sq_Queue.cpp
#include "sq_Queue.h"
int main()
{
sq_Queue<int> q(10);
q.prt_sq_Queue();
q.ins_sq_Queue(50);
q.ins_sq_Queue(60);
q.ins_sq_Queue(70);
q.ins_sq_Queue(80);
q.ins_sq_Queue(90);
q.ins_sq_Queue(100);
cout<<"输出队头与队尾指针及队列中的元素:"<<endl;
q.prt_sq_Queue();
cout<<"输出退队元素:"<<endl;
cout<<q.del_sq_Queue()<<endl;
cout<<q.del_sq_Queue()<<endl;
cout<<q.del_sq_Queue()<<endl;
cout<<"再输出队头与队尾指针及队列中的元素:"<<endl;
q.prt_sq_Queue();
return 0;
}
链栈：
#include <iostream.h>
#include <stdio.h>
#include <stdlib.h>
typedef char DateType;
typedef struct node
{
DateType data;
struct node* next;
}LinkStack;
LinkStack *top;
void InitStack()
{
top=(LinkStack*)malloc(sizeof(LinkStack));
top->next=NULL;
top->data=0;
cout<<"初始化链栈成功!";
}
void push(DateType x)
{
LinkStack* s;
s=(LinkStack*)malloc(sizeof(LinkStack));
s->data=x;
s->next=top;
top=s;
cout<<"入栈成功!";
}
void pop()
{
LinkStack* s;
s=top;
if(s->next==NULL)
{
cout<<"栈为空!";
}
else
{
top=s->next;
free(s);
cout<<"出栈成功";
}
}
void readTop()
{
if(top==NULL)
{
cout<<"栈为空!";
}
else
{
cout<<"栈顶元素为:"<<top->data;
}
}
void showStack()
{
LinkStack* s;
s=top;
if(s->next==NULL)
{
cout<<"栈为空!";
}
else
{
cout<<"链栈元素为:\n";
cout<<"\t\t\t";
while(s!=NULL)
{
cout<<" "<<s->data;
s=s->next;
}
}
}
void main()
{
int i,j;
DateType x;
while(j)
{
cout<<"\n\n\n\n";
cout<<"****************************************************************"<<endl;
cout<<"*** 菜单： ***"<<endl;
cout<<"*** ①创建链栈 ②入栈 ③读栈顶元 ***"<<endl;
cout<<"*** ④出栈 ⑤显示链栈元素 ⑥退出***"<<endl;
cout<<"****************************************************************"<<endl;
cout<<"请选择您所希望的操作：";
cin>>i;
if(i==1)
{
InitStack();
}
else if(i==2)
{
if(top==NULL)
{
cout<<"请先初始化链表!";
}
else
{
cout<<"请输入要入栈的元素:";
cin>>x;
push(x);
}
}
else if(i==3)
{
pop();
}
else if(i==4)
{
readTop();
}
else if(i==5)
{
showStack();
}
else if(i==6)
{
j=0;
cout<<"程序结束\n";
}
}
}
链队列：
#include <stdlib.h>
#include<iostream.h>
#define TRUE 1
#define FALSE 0
typedef int QElemType;
typedef struct LNode
{
QElemType data;
struct LNode *next;
}LNode , *LinkList;
typedef struct
{
LinkList front;
LinkList rear;
}LinkQueue;//链式队列
void InitQueue_L(LinkQueue &Q)//引用做参数，Q为结构体
{//初始化队列
Q.front=Q.rear=new LNode;
if(!Q.front) {cout<<"存储分配失败！"<<endl; exit(1);}
Q.front->next=NULL;
}
int IsEmpty(LinkQueue &Q)
{
if(Q.front==Q.rear)
{
return TRUE;
}
else
{
return FALSE;
}
}
//创建队列，数据元素由键盘输入
void CreateQueue_L(LinkQueue &Q)
{
QElemType temp;
LNode *p;
cout<<"输入要插入的队列值（输入-1结束）"<<endl;
cin>>temp;
while(temp != -1)
{
p=new LNode;
p->data=temp;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
cin>>temp;
}
cout<<"创建成功！"<<endl;
}
//入队操作
int EnterQueue(LinkQueue &Q,QElemType x)
{//将数据元素x插入到队列Q中
LNode *NewNode=new LNode;
if(!NewNode) {cout<<"存储分配失败！"<<endl; exit(1);}
if(NewNode!=NULL)
{
NewNode->data=x;
NewNode->next=NULL;
Q.rear->next=NewNode;
Q.rear=NewNode;
cout<<"入队成功！"<<endl<<endl;
return(TRUE);
}
else return(FALSE); //溢出
}
//出队操作
int DeleteQueue(LinkQueue &Q,QElemType &x)
{//将队列Q的队头元素出队，并存放到x所指的存储空间中
LNode *p;
/*if(Q.front==Q.rear)
{
cout<<"该队列为空！"<<endl;
return(FALSE);
}*/
p=Q.front->next;
x=p->data;
Q.front->next=p->next; //队头元素p出队
if(Q.rear==p) //如果队中只有一个元素p，则p出队后成为空队
Q.rear=Q.front;
free(p); //释放存储空间
cout<<"出队成功！"<<endl<<endl;
return(TRUE);
}
//队列长度
int QueueLength_L(LinkQueue Q)
{
int length=0;
if(IsEmpty(Q)) cout<<"该队列为空！"<<endl;
else
{
LNode *p=new LNode;
p=Q.front->next;
while(p)
{
length++;
p=p->next;
}
}
return length;
}
//输出队列元素
void OutputQueue_L(LinkQueue Q)
{
LNode *p=new LNode;
if(!p) {cout<<"存储分配失败！"<<endl; exit(1);}
if(Q.front==Q.rear) cout<<"该队列为空！"<<endl;
else
{
p=Q.front->next;
cout<<endl;
cout<<"队列的元素依次为：";
while(p)
{
cout<<p->data<<" ";
p=p->next;
}
cout<<endl<<endl;
}
}
QElemType SearchQueue(LinkQueue &Q,int &i)
{
LNode *p=new LNode;
if(!p) {cout<<"存储分配失败！"<<endl; exit(1);}
//if(Q.front==Q.rear) cout<<"该队列为空！"<<endl;
int j=1;
p=Q.front->next;
while(p&&j<i)
{
j++;
p=p->next;
}
return p->data;
}
//销毁队列
void DestroyQueue_L(LinkQueue &Q)
{
while(Q.front)
{
Q.rear=Q.front->next;
delete Q.front;
Q.front=Q.rear;
}
}
void main()
{
int flag=1,select;
LinkQueue Q;
int x;
while(flag)
{
cout<<" ☆☆链式队列基本操作☆☆"<<endl;
cout<<" ☆1.创建队列☆ "<<endl;
cout<<" ☆2.判断链队列是否为空☆"<<endl;
cout<<" ☆3.队头元素出队☆ "<<endl;
cout<<" ☆4.新元素入队☆ "<<endl;
cout<<" ☆5.求队列长度☆ "<<endl;
cout<<" ☆6.输出队列元素☆ "<<endl;
cout<<" ☆7.查找第i个位置元素☆ "<<endl;
cout<<" ☆8.销毁队列☆ "<<endl;
cout<<" ☆9.其他键退出☆ "<<endl;
cout<<endl;
cout<<"请选择操作：";
cin>>select;
switch(select)
{
case 1:
InitQueue_L(Q);
CreateQueue_L(Q);
OutputQueue_L(Q);
break;
case 2:
if(IsEmpty(Q)) cout<<"该队列为空！"<<endl;
else cout<<"该队列不为空！"<<endl;
break;
case 3:
if(IsEmpty(Q)) {cout<<"队列为空！"<<endl; break;}
DeleteQueue(Q,x);
OutputQueue_L(Q);
break;
case 4:
if(IsEmpty(Q)) {cout<<"队列还未创建！"<<endl; break;}
cout<<"输入要入队的元素x：";
cin>>x;
EnterQueue(Q,x);
OutputQueue_L(Q);
break;
case 5:
if(IsEmpty(Q)) {cout<<"队列还未创建！"<<endl; break;}
cout<<"该链队列的长度为："<<QueueLength_L(Q)<<endl<<endl;
break;
case 8:
if(IsEmpty(Q)) {cout<<"队列还未创建！"<<endl; break;}
DestroyQueue_L(Q);
cout<<"销毁成功!"<<endl<<endl;
break;
case 7:
cout<<"请输入要查找的位置i：";
cin>>x;
if(x<1||x>QueueLength_L(Q)) {cout<<"i值不合法！"<<endl; break;}
cout<<"该元素为："<<SearchQueue(Q,x)<<endl<<endl;
break;
case 6:
OutputQueue_L(Q);
break;
default:
flag=0;
break;
}
}
}
试验运行结果如图：
栈：
队列：
链栈：
链队列：
五、实验心得与体会
通过本次上机实验，我掌握了栈的顺序和链式存储存表示与入栈、出栈操作的程序实现，以及队列的链式存储表示与入队、出队基本操作算法实现。遇到问题难以避免，认真研究代码还是可行的，最后成功做出实验。