文档介绍：堆栈和队列的基本操作
实践教学
*******************
软件学院
2012学年秋季学期
上机实验 报告册
课程名称:_________________________
实验名称:_________________________
指导教师:_________________________
小组成员: ***********
********** ***********
********** ***********
堆栈和队列的基本操作(上机二)
一 实验目的
;
;
;
;
二 实验原理
堆栈顺序存储结构下的基本算法
堆栈链式存储结构下的基本算法
队列顺序存储结构下的基本算法
队列顺序存储结构下的基本算法
1、堆栈的定义:堆栈是一种只允许在表的一端进行插入和删除运算的特殊
的线性表。允许进行插入和删除运算的一端称为栈顶，另一端称为栈底，
当链表中没有元素时，称为空栈。
2、堆栈的插入运算称为入栈或者进栈，删除运算称为出栈或者退栈，栈顶
的当前位置是动态的，标识栈顶当前位置的指针称为栈顶指针。每次进栈
的数据元素都放在原当前栈顶元素之前成为新的栈顶元素，每次退栈的数
最后进入堆栈的数据元素总是最先退出堆栈。 据元素都是原当前栈顶元素，
3、堆栈的存储结构:
(1) 顺序存储结构:栈的顺序存储结构称为顺序栈。顺序栈的本质是顺
序表的简化。
(2) 链式存储结构:栈的链式存储结构称为链栈，通常用单链表示。链
栈的插入和删除操作只需处理栈顶的情况。
4、队列的定义:队列是允许在表的一端进行插入，而在表的另一端进行删
除的特殊线性表。允许进行插入的一端称为队尾，允许进行删除的一端称
为队头。队列的插入运算称为进队或者入队，删除运算称为出队或者离
队，因此队列又称为先进先出表。
5、队列的存储结构
队列的存储结构同线性表一样，可以分为顺序结构和链式结构。 (1) 顺序存储结构:用顺序存储结构存储队列称为顺序队列。顺序队列会出现假溢出问题，解决办法是用首尾相接的书顺序存储结构，称为循环队列。在队列中，只要涉及队头或者队尾指针的修改都要对其求模。
:用链式存储结构存储的队列称为链队列。链队列的基本(2) 链式存储结构
操作的实现基本上也是单链表操作的简化。通常附设头结点，并设置队头指针指向头结点，队尾指针指向终端结点。插入数据时只考虑在链队列的尾部进行，删除数据时只考虑在链队列的头部进行。
三 实验内容
进行堆栈(包括顺序结构、链式结构)和队列的基本操作:初始化栈、判 断栈空、出栈、取出栈顶元素、入栈、显示栈中所有元素等运算。
四 程序代码:
链式队列:
#include<>
#include<>
#define NULL 0
typedef int QElemType; typedef struct QNode{
QElemType data;
struct QNode *next; } QNode,*QueuePtr;
typedef struct{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
void CreateQueue(LinkQueue *Q) { int a;
QueuePtr p;
p=(QueuePtr)malloc(sizeof(QNode));
if(!p) printf("创建失败") ;
else
{p->next=NULL;
Q->front=p;
Q->rear=p;
scanf("%d",&a);
while(a!=-1)
{
p=(QueuePtr)malloc(sizeof(QNode));
p->next=NULL;
if(!p) printf("创建失败") ;
else
{ p->data=a;
Q->rear->next=p;
Q->rear=p;
scanf("%d",&a);
}
}
}
}
void PrintfQueue(LinkQueue *Q) {
QueuePtr p;
for(p=Q->front->next;p!=NULL;p=p->next)
{
printf(" %d",p->data);
}