《数据结构》课程实验 实验报告三
第三章 栈和队列的操作
实验题目： 实验三 栈和队列的操作 学号： 11416106 班级：计算机111 姓名： 张婷 指导教师： 游 静 实验完成时间： 2013.4.22 实验成绩：
实验三 栈和队列的操作
一、实验学时 2学时 二、背景知识
1.栈:
(1).入栈和进栈操作只能从栈顶一端进行; (2).LIFO(后进先出);
(3).栈的两种存储定义:顺序栈和链式栈。 2.队列:
(1).入队操作从队尾进行,出队操作从对头进行; (2).FIFO(先进先出);
(3).队列的两种存储定义:顺序队和链队。
三、目的要求
1． 掌握栈的顺序表示和实现。
Typedef struct{ SelemType *base; SelemType *base; Int stacksize; }sqstack;
2． 掌握队列的链式表示和实现以及顺序表示和实现。
链队列：
Typedef struct Qnode{ QelemType data; struct Qnode *next; } Qnode,*Queueptr; Typedef struct{ Queueptr front; Queueptr rear; }linkQueue; 顺序队列:
#define MAXQSIZE 100 Typedef struct{ Qelemtype *base; int front; int rear; }sqQueue;
四、实验内容
1． 顺序栈和循环队列的创建、入栈（队）、出栈（队）等基本操作。 2． 数制转换问题 【问题描述】
十进制数N和其它d进制数的转换是计算机实现计算的基本问题。试编制一段程序满足下列要求：对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数。 【基本要求】
首先初始化一个顺序栈，通过入栈出栈操作辅助完成数制的转换操作。 五、程序实例：顺序队列的入队和出队操作。
【问题描述】
使有数组创建队列。程序使有选项运行队列的操作，如：输入1表示元素入队，输入2表示元素出队，输入3表示结束程序运行，并且将队列剩余元素输出。 【基本要求】
首先使有数组创建队列，然后编写入队函数和出队函数，最后编写主函数。 【测试数据】
如：输入队列的元素是：[2][3][4][5][6]
取出队列的元素是：[2]
剩余队列的元素是：[3][4][5][6]
【实现提示】
#define MAXQUEUE 10 /* 队列的最大容量 */
int queue[MAXQUEUE]; /* 队列的数组定义 */ int front = -1; /* 队头 */ int rear = -1; /* 队尾 */ /*―――――――――――入队―――――――――――*/ int enqueue(int value) {
if ( rear >= MAXQUEUE ) /* 检查队列是否全满 */ return -1; /* 无法存入 */ rear++; /* 队尾指针前移 */ queue[rear] = value; /* 存入队列 */ }
/*―――――――――――出队―――――――――――*/ int dequeue() {
if ( front == rear ) /* 检查队列是否为空 */ return -1; /* 无法取出 */ front++; /* 队头指针前移 */ return queue[front]; /* 队列取出 */ }
六、实验结果 1、第一题 顺序栈实现 #include
#define ElementType char #define maxsize 40 typedef struct {
ElementType data[maxsize]; int top;
} SqStackTp;
int InitStack(SqStackTp *sq) {
sq->top=0;
return(1); }
int Push(SqStackTp *sq,DataType x) {
if(sq->top== maxsize-1) {
printf(\栈满\}
else{
sq->top++;
sq->data[sq->top]=x; return(1); } }
int Pop(SqStackTp *sq,DataType *x){ if (sq->top==0) {
printf(\下溢\}
else {
*x=sq->data[sq->top]; sq->top--; return(1);} }
int EmptyStack(SqStackTp *sq){ if (sq->top==0) return(1); else return(0); }
/*主函数*/ void main(){ SqStackTp sq; ElementType ch; InitStack(&sq);
for (ch='A';ch<='A'+12;ch++){ Push(&sq,ch); printf(\}
printf(\
while(!EmptyStack(&sq)) {
Pop(&sq,&ch);printf(\}
printf(\
队列的实现
#include
#define MAX 5 /* 队列的最大容量 */
/*―――――――――――队列定义―――――――――――*/ Struct queue{ int *base; int front; int rear; }；
Typedef struct queue Queue;
/*―――――――――――建队―――――――――――*/ queue* initqueue(Queue *q){
q->base-new int [MAX];
if(!Q->base){
cout<<”建队失败，内存申请不成功”< q->front=q->rear=0; return q; } /*―――――――――――入队―――――――――――*/ int enqueue(Queue *q,int value){ q->base[q->rear]=value; if((q->rear+1)%MAX==q->front){ cout<<”队已满”; return -1; } q->rear=(q->rear+1)%MAX; return value; } /*―――――――――――出队―――――――――――*/ int dequeue(Queue *q){ if ( q->front ==q-> rear ) { /* 检查队列是否为空 */ cout<<”队已空”< } /* 无法取出 */ int x; x=q->base[(q->front)%=MAX]; q->front++; /* 队头指针前移 */ return x; /* 队列取出 */ }