实验二栈和队列一、实验目的1、掌握栈的特点(先进后出FILO)及基本操作，如入栈、出栈等，栈的顺序存储结构和链式存储结构，以便在实际问题背景下灵活应用。
2、掌握队列的特点(先进先出FIFO)及基本操作,如入队、出队等，队列顺序存储结构、链式存储结构和循环队列的实现，以便在实际问题背景下灵活应用。
二、实验内容1、顺序栈的实现和运算；2、循环队列的实现和运算；3、栈的运用—十进制转八进制运算。
三、实验要求1、学生用C++/C完成算法设计和程序设计并上机调试通过；2、撰写实验报告，提供实验测试数据和实验结果；3、分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度，并简要给出算法设计小结和心得。
四、实验准备1、掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用任务中正确选用它们；2、熟练掌握顺序栈和循环队列的基本操作实现算法，特别应注意栈满和栈空的条件以及它们的描述方法，循环队列中队满和队空的描述方法。
3、在学习顺序栈的基本操作实现算法时，应注意：在书上给出的结构定义是采用了一种动态管理方式（不够时，可以再分配），但在C 语言中，用数组来存储顺序栈，是静态分配，即不能随机分配空间，这点易引起大家的误解。
五、实验步骤1、编程实现顺序栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能：(1)初始化顺序栈；(2)给定一个元素，将此元素压入此栈中；(3)将栈顶一个元素弹出此栈。
2、编写一个程序实现循环队列的各种基本运算，并在此基础上设计一个主程序，完成如下功能：(1)初始化循环队列；(2)给定一个元素，将此元素插入此队列中；(3)将队头一个元素出队。
3、栈的运用实例十进制转八进制。
六、实验参考代码1、顺序栈的实现和运算；#include <stdio.h>#include <stdlib.h>#define OK 1#define ERROR 0#define OVERFLOW -2typedef int ElemType;typedef int Status;//----- 栈的顺序存储表示-----#define STACK_INIT_SIZE 100 // 存储空间的初始分配量#define STACKINCREMENT 10 // 存储空间的分配增量typedef struct {ElemType *base;ElemType *top;int stacksize;} SqStack;// 构造一个空栈SStatus InitStack(SqStack &S){S.base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));if(!S.base) exit (OVERFLOW);S.top = S.base;S.stacksize = STACK_INIT_SIZE;return OK;}// 判栈S是否为空栈Status StackEmpty(SqStack S){if (S.top==S.base) return OK;else return ERROR;}//入栈函数Status Push (SqStack &S, ElemType e) {if(S.top - S.base >= S.stacksize){S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)* sizeof(ElemType)); if(!S.base) exit (OVERFLOW);S.top = S.base + S.stacksize;S.stacksize += STACKINCREMENT;}* S.top++ = e;return OK;}//出栈函数Status Pop (SqStack &S, ElemType &e) {if(S.top == S.base) return ERROR;e = * --S.top;return OK;}//输出顺序栈函数void OutStack(SqStack S){ int *p;if(S.top == S.base){printf("这是一个空栈！");}elsefor(p= S.top-1; p>= S.base;p--)printf("%6d", *p);printf("\n");}//主函数void main(){ SqStack s;int cord; ElemType a;printf("第一次使用必须初始化！\n");do{printf("\n 主菜单\n");printf(" 1 初始化顺序栈");printf(" 2 插入一个元素");printf(" 3 删除栈顶元素");printf(" 4 结束程序运行");printf("\n------------------------------------------------------------------------------\n"); printf("请输入您的选择( 1, 2, 3, 4)");scanf("%d",&cord);printf("\n");switch(cord){ case 1:InitStack(s);OutStack(s);break;case 2:printf("请输入要插入的数据元素：a=");scanf("%d",&a);Push(s,a);printf("%d 进栈之后的栈：",a);OutStack(s);break;case 3:Pop(s,a);printf("栈顶元素%d 出栈之后的栈：",a);OutStack(s);break;case 4:exit(0);}}while (cord<=4);}2、循环队列的实现和运算；#include <stdio.h>#include <stdlib.h>#define OK 1#define ERROR 0#define OVERFLOW -2typedef int QElemType;typedef int Status;//----- 队列的顺序存储表示-----#define MAXQSIZE 100 // 存储空间的初始分配量typedef struct {QElemType *base;int front;int rear;} SqQueue;// 构造一个空队列QStatus InitQueue(SqQueue &Q){Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType)); if(!Q.base)exit(OVERFLOW);Q.front=Q.rear=0;return OK;}//判队列是否为空Status QueueEmpty (SqQueue Q) {if(Q.rear==Q.front) return OK;else return ERROR ;}//入队函数Status EnQueue (SqQueue &Q, QElemType e) {if((Q.rear+1)%MAXQSIZE==Q.front) return ERROR;Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXQSIZE;return OK;}//出队函数Status DeQueue (SqQueue &Q, QElemType &e) {if(Q.rear==Q.front) return ERROR;e=Q.base[Q.front];Q.front=(Q.front+1)%MAXQSIZE;return OK;}//输出循环队列函数void OutQueue(SqQueue Q)if(Q.front == Q.rear){printf("这是一个空队列！");}else{n= (Q.rear- Q.front+ MAXQSIZE) % MAXQSIZE;i= 1;while ( i<= n){printf("%6d", Q.base[(Q.front+i-1)% MAXQSIZE] );i++;}printf("\n");}}//主函数void main(){ SqQueue q;int cord; QElemType a;printf("第一次使用必须初始化！\n");do{printf("\n 主菜单\n");printf(" 1 初始化循环队列");printf(" 2 进队一个元素");printf(" 3 出队一个元素");printf(" 4 结束程序运行");printf("\n------------------------------------------------------------------------------\n"); printf("请输入您的选择( 1, 2, 3, 4)");scanf("%d",&cord);printf("\n");switch(cord){ case 1:InitQueue(q); //调用初始化算法;OutQueue(q);break;case 2:printf("请输入要插入的数据元素：a=");scanf("%d",&a);EnQueue (q, a); //调用进队算法;printf("%d 进队之后的队列：",a);OutQueue(q);break;case 3:DeQueue (q, a); //调用出队算法;printf("队头元素%d 出队之后的队列：",a);OutQueue(q);break;exit(0);}}while (cord<=4);}3、栈的应用—十进制转八进制#include <stdio.h>#include <stdlib.h>#define OK 1#define ERROR 0#define OVERFLOW -2typedef int ElemType;typedef int Status;#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef struct {ElemType *base;ElemType *top;int stacksize;} SqStack;// 构造一个空栈SStatus InitStack(SqStack &S){S.base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));if(!S.base) exit (OVERFLOW);S.top = S.base;S.stacksize = STACK_INIT_SIZE;return OK;}// 判栈S是否为空栈Status StackEmpty(SqStack S){if (S.top==S.base) return OK;else return ERROR;}//入栈函数Status Push (SqStack &S, ElemType e) {if(S.top - S.base >= S.stacksize){S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)* sizeof(ElemType)); if(!S.base) exit (OVERFLOW);S.top = S.base + S.stacksize;S.stacksize += STACKINCREMENT;}* S.top++ = e;return OK;}//出栈函数Status Pop (SqStack &S, ElemType &e) {if(S.top == S.base) return ERROR;e = * --S.top;return OK;}//十进制转八进制函数void conversion(){ SqStack S;int n,e;InitStack(S);printf("请输入一个十进制数：");scanf("%d",&n);while(n){Push(S,n%8);n=n/8;}printf("转换之后的八进制数为：");while(!StackEmpty(S)){Pop(S, e);printf("%d",e);}printf("\n");}void main(){conversion();}（注：文档可能无法思考全面，请浏览后下载，供参考。
栈和队列从数据结构的角度看:它们和线性表相同从数据类型的角度看:它们和线性表不同线性表栈队列Insert(L, i, x) Insert(S, n+1, x) Insert(Q,n+1, x) ( 1≤ i ≤ n+1)Delete(L, i) Delete(S, n) Delete(Q, 1)( 1≤ i ≤ n)3.1 栈的类型定义ADT Stack{数据对象：D＝{ a i | a i ∈ElemSet, i=1,2,...,n, n≥0 }数据关系：R1＝{ <a i-1, a i >| a i-1, a i∈D, i=2,...,n }约定a n端为栈顶，a1 端为栈底。
基本操作：InitStack(&S)操作结果：构造一个空栈S。
DestroyStack(&S)初始条件：栈S已存在。
操作结果：栈S被销毁。
ClearStack(&S)初始条件：栈S已存在。
操作结果：将S清为空栈。
StackEmpty(S)初始条件：栈S已存在。
操作结果：若栈S为空栈，则返回TRUE，否则FALE。
StackLength(S)初始条件：栈S已存在。
操作结果：返回S的元素个数，即栈的长度。
GetTop(S, &e)初始条件：栈S已存在且非空。
操作结果：用e返回S的栈顶元素。
Push(&S, e)初始条件：栈S已存在。
操作结果：插入元素e为新的栈顶元素。
Pop(&S, &e)初始条件：栈S已存在且非空。
操作结果：删除S的栈顶元素，并用e返回其值。
} ADT Stack3.2 栈的应用举例例一、数制转换十进制数N和其他d进制数的转换是计算机实现计算的基本问题，其解决方法很多，其中一个简单算法基于下列原理：N = (N div d)×d + N mod d(其中：div 为整除运算，mod 为求余运算）例如：（1348)10 = (2504)8，其运算过程如下：N N div 8 N mod 81348 168 4168 21 021 2 52 0 2假设现要编制一个满足下列要求的程序：对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数。
数据结构——线性结构之栈和队列⼀、栈（⼀）定义栈是只能通过访问它的⼀端来实现数据存储和检索的⼀种线性数据结构。
对于栈的修改要按照先进后出的原则进⾏，因此，栈⼜被称为后进先出（LIFO）的线性表。
（⼆）基本运算初始化：创建⼀个空栈。
判断栈是否为空：如果栈为空，返回“真”，否则返回“假”。
⼊栈：将元素x加⼊栈顶，并更新栈顶指针。
出栈：将栈顶元素删除，并更新栈顶指针。
可以返回栈顶元素。
读取栈顶元素：返回栈顶元素，但不修改栈顶指针。
（三）存储结构顺序存储：⽤⼀组地址连续的存储单元存储⾃栈顶到栈底的数据元素。
采⽤这种存储结构的栈，称为顺序栈。
链式存储：⽤链表作为存储结构的栈，称为链栈。
链表的头指针就是栈顶指针。
（四）应⽤表达式求值括号匹配将递归过程转变为⾮递归过程（五）顺序栈代码#define TRUE 1#define FALSE 0#define ERROR -1#define NULL -2typedef int bool;typedef int ElementType;Stack CreateStack();bool IsFull(Stack S);bool IsEmpty(Stack S);bool Push(Stack S, ElementType X);ElementType Pop(Stack S);typedef int Position;struct SNode {ElementType *Data; /* 存储元素的数组 */Position Top; /* 栈顶指针 */int MaxSize; /* 堆栈最⼤容量 */};typedef struct SNode *Stack;Stack CreateStack( int MaxSize ){Stack S = (Stack)malloc(sizeof(struct SNode));S->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));S->Top = -1;S->MaxSize = MaxSize;return S;}bool IsFull( Stack S ){return (S->Top == S->MaxSize-1);}int Push( Stack S, ElementType X ){if ( IsFull(S) ) {printf("堆栈满");return FALSE;}else {S->Data[++(S->Top)] = X;return TRUE;}}bool IsEmpty( Stack S ){return (S->Top == -1);}ElementType Pop( Stack S ){if ( IsEmpty(S) ) {printf("堆栈空");return ERROR; /* ERROR是ElementType的特殊值，标志错误 */}elsereturn ( S->Data[(S->Top)--] );}（六）链栈代码#define TRUE 1#define FALSE 0#define ERROR -1#define NULL -2typedef int bool;typedef int ElementType;Stack CreateStack();bool IsEmpty(Stack S);bool Push(Stack S, ElementType X);ElementType Pop(Stack S);typedef struct SNode *PtrToSNode;struct SNode {ElementType Data;PtrToSNode Next;};typedef PtrToSNode Stack;Stack CreateStack( ){ /* 构建⼀个堆栈的头结点，返回该结点指针 */Stack S;S = (Stack)malloc(sizeof(struct SNode));S->Next = NULL;return S;}bool IsEmpty ( Stack S ){ /* 判断堆栈S是否为空，若是返回true；否则返回false */return ( S->Next == NULL );}bool Push( Stack S, ElementType X ){ /* 将元素X压⼊堆栈S */PtrToSNode TmpCell;TmpCell = (PtrToSNode)malloc(sizeof(struct SNode));TmpCell->Data = X;TmpCell->Next = S->Next;S->Next = TmpCell;return TRUE;}ElementType Pop( Stack S ){ /* 删除并返回堆栈S的栈顶元素 */PtrToSNode FirstCell;ElementType TopElem;if( IsEmpty(S) ) {printf("堆栈空");return ERROR;}else {FirstCell = S->Next;TopElem = FirstCell->Data;S->Next = FirstCell->Next;free(FirstCell);return TopElem;}}⼆、队列（⼀）定义队列是只能通过访问它的⼀端来实现数据存储和检索的⼀种线性数据结构。
