栈和队列的应用（算法与数据结构课程设计）

栈和队列的应用

一、问题描述

栈和队列是一种常见的数据结构，是两种非常重要的线性结构，也都是线性表，它们是操作受限的的线性表，有顺序栈、链式栈、链式队列和循环队列等形式。它们广泛应用在各种软件系统中。本题就是要用这些线性结构先完成基本的应用，如回文，逆置。再编写一个简易的停车场管理系统，完成对车辆出入库的管理、停车时间的记录和管理费用的结算。

二、基本要求

1、选择顺序栈和链队列，完成回文判断、字符串的逆置； 2、选择链栈和循环队列，完成回文判断、字符串的逆置； 3、运用栈和队列，完成简易停车场管理系统，要求： （1）车辆入库管理及时间记录；

（2）车辆出库管理、时间的记录及管理费用的结算； （3）若停车场已满则车辆进入便车道等候。

三、测试数据

1、回文判断的测试数据：abcbc@； 2、字符串逆置的测试数据：abcdef； 3、停车场管理系统测试数据：

（1）输入A1、A2、A3实现车辆的入库及对便车道进行测试； （2）输入D1对车辆出库及管理费用结算进行测试 。

四、算法思想

1、（1）定义顺序栈和链队列及关于它们的基本操作，如定义栈和队列、求栈和队列的长度、入栈出栈、入队列出队列等。方便后面函数的调用，是实现程序的基石。（链栈和循环队列也是如此）

2、（1）编写函数Palindrome_Test来实现字符串的回文判断，回文是利用了栈的反序输出原则而队列则是顺序输出这个思想来实现的。往栈和队列输入同一组字符，再将它们一起输出，这样栈输出的字符就与原来的顺序相反了，而队列输出的字符与原来的顺序仍然是一样的，这样比较它们输出的字符是否相等就可以判断是否是回文了。是则输出1，不是则输出。

(2)编写函数nzhi来实现一段字符串的逆置。逆置是通过栈的反序输出来实现的。通过它将队列的一组字符串进行逆置。将队列的字符串顺序入栈然后出栈。这样得到的字符串与原来的字符串就逆置过来了。

3、（1）定义车节点的类型及栈和队列的相关操作。

（2）用栈的操作编写一个停车场，队列的操作编写一个便车道。

wilyes11收集 博客(与学习无关)：http://blog.sina.com.cn/u/1810231802

（3）编写函数Carrival实现车辆入库管理，若车库满则进入便车道，这个函数是利用栈的入栈等操作来实现的，并利用“t=localtime(&car.t);”语句记录入库时间。 （4）编写函数Carleave实现车辆出库管理并利用“t=localtime(&car.t);”语句记录出库时间，计算车辆的管理费用。若便车道内有车等候，则进入停车场，并记录此时时间。主要用到了栈的入栈出栈及队列中的入队列等操作。用“(car.t-car2.t)*charge”语句来计算车辆的管理费用。

五、模块划分。

1、定义栈和队列及其基本操作。 （1）void InitStack(SqStack *S) 初始化栈

（2）int StackLength(SqStack S)

求栈的长度

（3）void Push(SqStack *S,ElemType e)及void Pop(SqStack *S,ElemType *e) 入栈及出栈

（4）void InitQueue(LinkQueue *Q)

初始化队列

（5）int QueueLength（SqQueue Q）

求队列的长度

(6) int EnQueue(SqQueue *Q，ElemType e)及void DeQueue(LinkQueue *Q, ElemType *e)

入队列及出队列

2、 int Palindrome_Test(SqStack *S,LinkQueue Q) 判断是否为回文，是则输入1，否则输出0。 3、 void nzhi(LinkQueue Q) 实现字符串的逆置。 4、 typedef struct ParkCar 定义车节点类型。

5、 void Carrival(LinkQueue *q,ParkCar car) 实现车辆入库管理及记录时间的功能。 6、 void Carleave(LinkQueue* q,ParkCar car)

实现车辆出库管理及时间记录，管理费用的计算的功能。 7、 int main()

主函数。调用定义的函数进行操作及结果的输出。

六、数据结构//(ADT)

1、链栈 typedef int ElemType;

typedef struct SNode

wilyes11收集 博客(与学习无关)：http://blog.sina.com.cn/u/1810231802

{ ElemType Data; struct SNode *next;

}SNode *LinkStack; 循环队列typedef struct

{ElemType *base; int front; int rear;}SqQueue;

2、顺序栈typedef char ElemType;

typedef struct { ElemType *base;

ElemType *top; } SqStack; 链式队列typedef struct QNode { ElemType data; struct QNode *next; } QNode, *QueuePtr;

typedef struct { QueuePtr front; QueuePtr rear; } LinkQueue;

3、车节点

typedef struct ParkCar {char ADmark; int Plate; time_t t;

}ElemType,ParkCar;

七、源程序

1.用顺序栈和链式队列实现逆置和回文

#include #include #define N 20

typedef char ElemType; typedef struct

wilyes11收集 博客(与学习无关)：http://blog.sina.com.cn/u/1810231802

{ ElemType *base;

ElemType *top; } SqStack;

typedef struct QNode { ElemType data; struct QNode *next; } QNode, *QueuePtr;

typedef struct

{ QueuePtr front; QueuePtr rear; } LinkQueue;

void InitStack(SqStack *S)

{ S->base=(ElemType *)malloc(N*sizeof(ElemType)); if (!S->base) exit(0); S->top=S->base; }

void DestroyStack(SqStack *S) { free(S->base); }

void ClearStack(SqStack *S) { S->top=S->base; }

int StackEmpty(SqStack S) { if (S.top==S.base) return 1; else

return 0; }

int StackLength(SqStack S) { return S.top-S.base; }

void GetTop(SqStack S, ElemType *e) { if (S.top>S.base) *e=*(S.top-1); }

void Push(SqStack *S,ElemType e) { if (S->top-S->base

{ *(S->top)=e; S->top++;} else

printf(\栈满\

void Pop(SqStack *S,ElemType *e) { if (S->top>S->base)

wilyes11收集 博客(与学习无关)：http://blog.sina.com.cn/u/1810231802

S->top--; *e=*(S->top); }

void InitQueue(LinkQueue *Q)

{ Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode)); if (!(Q->front)) exit(0); Q->front->next=NULL; }

void DestroyQueue(LinkQueue *Q) { while (Q->front)

{ Q->rear=Q->front->next; free(Q->front); Q->front=Q->rear; } }

int QueueEmpty(LinkQueue Q) { if (Q.front==Q.rear) return 1; else

return 0; }

int QueueLength(LinkQueue Q) { QueuePtr p; int n=0; p=Q.front;

while (p!=Q.rear) { n++; p=p->next; } return n; }

void EnQueue(LinkQueue *Q, ElemType e) { QueuePtr p;

p=(QueuePtr)malloc(sizeof(QNode)); if (!p) exit(0);

p->data=e; p->next=NULL; Q->rear->next=p; Q->rear=p; }

void DeQueue(LinkQueue *Q, ElemType *e) { QueuePtr p;

if (Q->front!=Q->rear) { p=Q->front->next; *e=p->data;

Q->front->next=p->next;

wilyes11收集 博客(与学习无关)：http://blog.sina.com.cn/u/1810231802

本文来源：https://www.bwwdw.com/article/10of.html