作者：命运之光
专栏：数据结构
实验内容
实验三栈和队列
实验环境：VisualC++
实验目的：
1、掌握栈和队列的定义；
2、掌握栈和队列的操作特点。
实验内容：
Q是一个队列，S是一个空栈，实现将队列中的元素逆置的算法。（使用顺序存储结构实现）
实验提示：
由于队列的一系列操作不可能将其中的元素逆置，而栈可以将入栈的元素逆序提取出来，因此我们可以让队列中的元素逐个地出队列，入栈；全部入栈后再逐个出栈，入队列。
实验三 栈和队列
一、需求分析
任务：建立队列和栈来实现元素逆置
1.建立队列
2.建立栈
3.主函数调用队列和栈实现元素逆置
二、概要设计
1.通过结构体建立队列
typedef struct {
ElemType *base;
int front;
int rear;
}SqQueue;建立队列首先要在结构体中定义
头节点front
尾节点rear
由于为确保实际修改传入值所以这里都用指针来传参定义ElemType *base;
2.通过结构体创建栈
typedef struct {
ElemType *base;
ElemType *top;
int stacksize;
}SqStack;建立栈首先要在结构体中定义
栈顶ElemType *top;
栈底ElemType *base;
栈的大小int stacksize;
3.主程序
int main() {
InitQueue(Q);
ElemType e;
int num;
cout << "****************栈逆置队列元素****************" << endl << endl;
cout << "请输入初始化队列元素个数:";
cin >> num;
for (int i = 0; i < num; i++) {
cout << "请输入第" << i + 1 << "个元素:";
cin >> e;
EnQueue(Q, e);
}
algo(Q);
cout << "栈逆置队列后元素如下：";
while (!QueueEmpty(Q))
{
DeQueue(Q, e);
cout << e;
}
cout << endl << endl;
return 0;
}通过InitQueue(Q);先初始化队列
输入cin >> num;
入队列EnQueue(Q, e);
将队列中的元素逆置DeQueue(Q, e);
输出结果cout << e;
三、详细设计
1.初始化队列
status InitQueue(SqQueue &Q) { //初始化队列
Q.base = (ElemType*)malloc(MAXQSIZE * sizeof(ElemType));
if (!Q.base)exit(OVERFLOW);
Q.front = Q.rear = 0;
return OK;
}2.入队
status EnQueue(SqQueue &Q, ElemType e) { //入队
if ((Q.rear + 1) % MAXQSIZE == Q.front)
return ERROR;//队满
Q.base[Q.rear] = e;
Q.rear = (Q.rear + 1) % MAXQSIZE;
return OK;
}3.出队
status DeQueue(SqQueue &Q, ElemType &e) { //出队
if (Q.front == Q.rear)return ERROR; //队空
e = Q.base[Q.front];
Q.front = (Q.front + 1) % MAXQSIZE;
return OK;
}4.判断是否为空队列
status QueueEmpty(SqQueue Q) {//是否为空队
return Q.rear == Q.front;
}5.初始化栈
status 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;
}6.入栈
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;
}7.出栈
status Pop(SqStack &S, ElemType &e) {//出栈
if (S.top == S.base)exit(UNDERFLOW);
e = *(S.top=S.top-1);
return OK;
}8.判断栈是否为空
status StackEmpty(SqStack S) {//是否为空栈
return S.base == S.top;
}9.栈实现队的首尾逆置
void algo(SqQueue &Q) {//栈实现队的首尾逆置
ElemType e;
InitStack(S);
cout << "栈逆置队列前元素如下：";
while (!QueueEmpty(Q)) {
DeQueue(Q, e);
cout << e;
Push(S, e);
}
cout << endl;
while (!StackEmpty(S)) {
Pop(S, e);
EnQueue(Q, e);
}
}10.主函数
int main() {
InitQueue(Q);
ElemType e;
int num;
cout << "****************栈逆置队列元素****************" << endl << endl;
cout << "请输入初始化队列元素个数:";
cin >> num;
for (int i = 0; i < num; i++) {
cout << "请输入第" << i + 1 << "个元素:";
cin >> e;
EnQueue(Q, e);
}
algo(Q);
cout << "栈逆置队列后元素如下：";
while (!QueueEmpty(Q))
{
DeQueue(Q, e);
cout << e;
}
cout << endl << endl;
return 0;
}四、调试分析
简单分析：算法进行了入队出队入栈出栈在入队的操作符合实验要求。
总结经验和体会：手写队列和手写栈实现起来相对简单，实验中所遇到的难点是传参问题如何在入队后出队将出队的值再次入栈使其值不变，出栈时实现元素的逆置。第一次操作时遇到的问题是字符型于整型转化出现了问题输入1输出的却是1049改为字符型解决后，最后的问题就是出队入栈无法实现元素的逆置，最后通过专门在栈中写出元素逆置的算法勉强实现。
运行截图：
五、测试结果
输入
1 2 3 4 5 6 7 8 9
输出
9 8 7 6 5 4 3 2 1
运行截图：
附录：源程序代码（带注释）
# include <malloc.h>
#include <stdio.h>
#include <iostream>
using namespace std;
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define UNDERFLOW -2
#define STACK_INIT_SIZE 80
#define STACKINCREMENT 10
typedef int status;
#define ElemType char
typedef struct {
ElemType *base;
ElemType *top;
int stacksize;
}SqStack;
SqStack S;
#define MAXQSIZE 80
typedef struct {
ElemType *base;
int front;
int rear;
}SqQueue;
SqQueue Q;
status 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;
}
status InitQueue(SqQueue &Q) { //初始化队列
Q.base = (ElemType*)malloc(MAXQSIZE * sizeof(ElemType));
if (!Q.base)exit(OVERFLOW);
Q.front = Q.rear = 0;
return OK;
}
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 EnQueue(SqQueue &Q, ElemType e) { //入队
if ((Q.rear + 1) % MAXQSIZE == Q.front)
return ERROR;//队满
Q.base[Q.rear] = e;
Q.rear = (Q.rear + 1) % MAXQSIZE;
return OK;
}
status Pop(SqStack &S, ElemType &e) {//出栈
if (S.top == S.base)exit(UNDERFLOW);
e = *(S.top=S.top-1);
return OK;
}
status DeQueue(SqQueue &Q, ElemType &e) { //出队
if (Q.front == Q.rear)return ERROR; //队空
e = Q.base[Q.front];
Q.front = (Q.front + 1) % MAXQSIZE;
return OK;
}
status StackEmpty(SqStack S) {//是否为空栈
return S.base == S.top;
}
status QueueEmpty(SqQueue Q) {//是否为空队
return Q.rear == Q.front;
}
void algo(SqQueue &Q) {//栈实现队的首尾逆置
ElemType e;
InitStack(S);
cout << "栈逆置队列前元素如下：";
while (!QueueEmpty(Q)) {
DeQueue(Q, e);
cout << e;
Push(S, e);
}
cout << endl;
while (!StackEmpty(S)) {
Pop(S, e);
EnQueue(Q, e);
}
}
int main() {
InitQueue(Q);
ElemType e;
int num;
cout << "****************栈逆置队列元素****************" << endl << endl;
cout << "请输入初始化队列元素个数:";
cin >> num;
for (int i = 0; i < num; i++) {
cout << "请输入第" << i + 1 << "个元素:";
cin >> e;
EnQueue(Q, e);
}
algo(Q);
cout << "栈逆置队列后元素如下：";
while (!QueueEmpty(Q))
{
DeQueue(Q, e);
cout << e;
}
cout << endl << endl;
return 0;
}适用于：
大一数据结构实验课实验报告——栈和队列（C语言版）
