文档库

最新最全的文档下载
当前位置:文档库 > 队列及其应用

队列及其应用

西南石油大学上机实验报告

队列及其应用

一、实验目的

1.掌握队列存储结构及其基本运算的实现。

2.利用队列设计应用算法并实现。

二、实验内容

已知Q是一个非空队列,S是一个空栈。仅用队列和栈的ADT函数和少量工作变量,编写一个算法,将队列Q中的所有元素逆置。

栈的ADT函数有:

void InitStack(stack &s); 初始化空栈

void Push(stack &s,SElemType value); 新元素value进栈

SElemType Pop(stack &s); 出栈,返回栈顶值

bool StackEmpty(stack s); 判栈空否

队列的 ADT函数有:

void enQueue(queue &q,SElemType value); 元素value进队

SElemType deQueue(queue &q); 出队列,返回队头值

bool QueueEmptyQ(queue q); 判队列空否

三、实验说明

1.栈的基本函数可以使用实验3中已有函数。

2.要求显示逆置前后队列中元素。

四、算法实现

#include

#include

#define OK 1

#define OVERFLOW -1

#define ERROR 0

typedef struct //定义栈

{

int *base;

int *top;

int stacksize;

}SqStack;

typedef struct QNode //对栈中数据的存放

{

int data;

struct QNode *next;

}QNode,*QueuePtr;

typedef struct //定义队列

{

QueuePtr front;

QueuePtr rear;

}LinkQueue;

int InitStack(SqStack &S) //初始化栈

{

S.base=(int*)malloc(100*sizeof(int));

if(!S.base)exit(OVERFLOW);

S.top=S.base;

S.stacksize=100;

return OK;

}

int Push(SqStack &S,int e) //定义入栈

{

if(S.top-S.base>=S.stacksize)

{

S.base=(int *)realloc(S.base,(S.stacksize+100)*sizeof(int));

if(!S.base)exit(OVERFLOW);

S.top=S.base+S.stacksize;

S.stacksize+=100;

}

*S.top++=e;

return OK;

}

int Pop(SqStack &S) //定义出栈

{

int e;

if(S.top==S.base)

return ERROR;

e=*--S.top;

return e;

}

int StackEmpty(SqStack &S) //判断栈空

{

if (S.top-S.base==0) return(1);

else return(0);

}

int makeEmpty(SqStack &S) //清空栈

{

while(S.top!=S.base)

Pop(S);

return OK;

}

int InitQueue(LinkQueue &Q) //初始化队列

{

Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));

if(!Q.front)exit(OVERFLOW);

Q.front->next=NULL;

return OK;

}

int EnQueue(LinkQueue &Q,int e) //元素入队

{

QueuePtr p;

p=(QueuePtr)malloc(sizeof(QNode));

if(!p)exit(OVERFLOW);

p->data=e;

p->next=NULL;

Q.rear->next=p;

Q.rear=p;

return OK;

}

int DeQueue(LinkQueue &Q) //元素出队

{

int e;

QueuePtr p;

if(Q.front==Q.rear)

return ERROR;

p=Q.front->next;

e=p->data;

Q.front->next=p->next;

if(Q.rear==p)

Q.rear=Q.front;

free(p);

return e;

}

int QueueEmpty(LinkQueue &Q) //判断队列是否为空{

if(Q.front==Q.rear)

return(1);

else return(0);

}

void main()

{

SqStack s;

LinkQueue q;

int n,data,value;

InitStack(s);

InitQueue(q);

if(StackEmpty(s)) //若栈不为空,则清空该栈makeEmpty(s);

if(QueueEmpty(q))

{

printf("请输入队列的长度:");

scanf("%d",&n);

printf("请输入队列中的元素:\n");

for(int i=0;i

{

scanf("%d",&data);

EnQueue(q,data);

}

}

QueuePtr p;

p=q.front->next;

printf("队列为:");

while(p) //输出队列中的元素

{

printf("%d ",p->data);

p=p->next;

}

printf("\n");

for(int i=0;i

{

value=DeQueue(q);

Push(s,value);

}

for(i=0;i

{

value=Pop(s);

EnQueue(q,value);

}

printf("逆序后的队列为:");

for(i=0;i

{

data=DeQueue(q);

printf("%d ",data);

}

printf("\n");

}

五、程序运行界面

队列及其应用

六、实验总结

掌握队列存储结构及其基本运算的实现,并且利用队列设计应用算法并实现。这个实验中的函数调用用得比较多。