数据结构栈和队列.docx

文档介绍：实验二 栈和队列
一、实验目的
1、掌握栈的特点 (先进后出 FILO)及基本操作，如入栈、出栈等，栈的顺序存储结构和链式存储结构，以便在实际问题背景下灵活应用。
2、掌握队列的特点 (先进先出 FIFO)及基本操作 ,如入队、出队等，队列顺序存储结构、链式存储结构和循环队列的实现，以便在实际问题背景下灵活应用。
二、 实验内容
1、顺序栈的实现和运算；
2、循环队列的实现和运算；
3、栈的运用 —十进制转八进制运算。三、实验要求
1、学生用 C++/C 完成算法设计和程序设计并上机调试通过；
2、撰写实验报告，提供实验测试数据和实验结果；
3、分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度， 并简要给出算法设计小结和心得。
四、实验准备
1、掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用任务中正确选用它们；
2、熟练掌握顺序栈和循环队列的基本操作实现算法，特别应注意栈满和栈空的条件以及它们的描述方法，循环队列中队满和队空的描述方法。
3、在学****顺序栈的基本操作实现算法时，应注意：在书上给出的结构定义是采 用了一种动态管理方式（不够时，可以再分配），但在 C 语言中，用数组来存
储顺序栈，是静态分配，即不能随机分配空间，这点易引起大家的误解。五、实验步骤
1、编程实现顺序栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能：
初始化顺序栈；
给定一个元素，将此元素压入此栈中； (3)将栈顶一个元素弹出此栈。
2、编写一个程序实现循环队列的各种基本运算， 并在此基础上设计一个主程序， 完成如下功能：
初始化循环队列；
给定一个元素，将此元素插入此队列中； (3)将队头一个元素出队。
3、栈的运用实例 十进制转八进制。六、实验参考代码
1、顺序栈的实现和运算；
#include <> #include <> #define OK 1
#define ERROR 0
#define OVERFLOW -2 typedef int ElemType; typedef int Status;
//----- 栈的顺序存储表示 -----
#define STACK_INIT_SIZE 100 // 存储空间的初始分配量#define STACKINCREMENT 10 // 存储空间的分配增量typedef struct {
ElemType *base; ElemType *top; int stacksize;
} SqStack;
// 构造一个空栈 S
Status InitStack(SqStack &S){
= (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType)); if(!) exit (OVERFLOW);
= ;
= STACK_INIT_SIZE; return OK;
}
// 判栈 S是否为空栈
Status StackEmpty(SqStack S){ if (==) return O