栈和队列的应用举例

攀枝花学院数据结构第三次实验

实验二 栈和队列的应用

1、实验目的

（1）熟练掌握栈和队列的结构，以及这两种数据结构的特点；

（2）能够在两种存储结构上实现栈的基本运算，特别注意栈满和栈空的判断条件及描述方法；

（3）熟练掌握链队列和循环队列的基本运算，并特别注意队列满和队列空的判断条件和描述方法；

2、实验内容

利用栈的基本操作实现将任意一个十进制整数转化为R进制整数.

3、实验步骤

（1）理解栈的基本工作原理；

（2）仔细分析实验内容，给出其算法和流程图； （3）用C语言实现该算法；

（4）给出测试数据，并分析其结果； （5）在实验报告册上写出实验过程。

4、实验帮助

算法为：

1) 定义栈的顺序存取结构

2) 分别定义栈的基本操作（初始化栈、判栈为空、出栈、入栈等） 3) 定义一个函数用来实现上面问题： 十进制整数X和R作为形参 初始化栈

只要X不为0重复做下列动作

将X % R入栈 X=X/R

只要栈不为空重复做下列动作

栈顶出栈 输出栈顶元素

程序代码：

# include # include

typedef struct zan {

int data[100]; int top; }seqstack;

//置空栈

seqstac

实验二 栈和队列的操作与应用

【实验目的】

1．熟练掌握栈和队列的特点

2．掌握栈的定义和基本操作，熟练掌握顺序栈的操作及应用

3．掌握对列的定义和基本操作，熟练掌握链式队列的操作及应用, 掌握环形队列的入队和出队等基本操作

4． 加深对栈结构和队列结构的理解，逐步培养解决实际问题的编程能力1．掌握线性表的两类存储结构（顺序存储结构和链式存储结构）的描述方法。

【实验内容】

1．定义顺序栈，完成栈的基本操作：空栈、入栈、出栈、取栈顶元素;

2．实现十进制数与八进制数的转换，十进制数与十六进制数的转换和任意进制之间的转换;

3．定义链式队列，完成队列的基本操作：入队和出队;·

··1 亲亲1··················11112

【实验指导】

1.利用栈的顺序存储结构,设计一组输入数据（假定为一组整数），能够对顺序栈进行如下操作：

（1） 初始化一个空栈，分配一段连续的存储空间，且设定好栈顶和栈底; （2）完成一个元素的入栈操作，修改栈顶指针; （3）完成一个元素的出栈操作，修改栈顶指针; （4）读取栈顶指针所指向的元素的值;

（5） 将十进制数N 和其它d 进制数的转换是计算机实现计算的基本问题，其解决方案很多，其中最简单方法基于

第三章栈和队列练习题

一、单项选择题

1．一个顺序栈一旦被声明，其占用空间的大小（ ）。 A．已固定 B．可以改变 C．不能固定 D．动态变化 2．链栈和顺序栈相比，有一个比较明显的缺点，即（ ）。 A．插入操作更加方便 B．通常不会出现栈满的情况 C．不会出现栈空的情况 D．删除操作更加方便 3．用单链表表示的链式队列的队头在链表的（ ）位置。 A．链头 B．链尾 C．链中 D．任意位置

4．在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入缓冲区中，而打印机则从缓冲区中取出数据打印，该缓冲区应该是一个（ ）结构。

A．堆栈 B．队列 C．数组 D．先性表

5．若已知一个栈的入栈序列是1，2，3，…，30，其输出序列是p1,p2,p3,…pn，若p1=30，则p10为（ ）。

A．11 B．20 C．19 D．21

6．循环队列A[m] 存放其元素，用front和rear分别表示队头及队尾，则循环队列满的条件是（ ）。

A．（rear+1)%m=front

实验二 栈和队列的操作与应用

【实验目的】

1．熟练掌握栈和队列的特点

2．掌握栈的定义和基本操作，熟练掌握顺序栈的操作及应用

3．掌握对列的定义和基本操作，熟练掌握链式队列的操作及应用, 掌握环形队列的入队和出队等基本操作

4． 加深对栈结构和队列结构的理解，逐步培养解决实际问题的编程能力1．掌握线性表的两类存储结构（顺序存储结构和链式存储结构）的描述方法。

【实验内容】

1．定义顺序栈，完成栈的基本操作：空栈、入栈、出栈、取栈顶元素;

2．实现十进制数与八进制数的转换，十进制数与十六进制数的转换和任意进制之间的转换;

3．定义链式队列，完成队列的基本操作：入队和出队;·

··1 亲亲1··················11112

【实验指导】

1.利用栈的顺序存储结构,设计一组输入数据（假定为一组整数），能够对顺序栈进行如下操作：

（1） 初始化一个空栈，分配一段连续的存储空间，且设定好栈顶和栈底; （2）完成一个元素的入栈操作，修改栈顶指针; （3）完成一个元素的出栈操作，修改栈顶指针; （4）读取栈顶指针所指向的元素的值;

（5） 将十进制数N 和其它d 进制数的转换是计算机实现计算的基本问题，其解决方案很多，其中最简单方法基于

第三章栈和队列练习题

一、单项选择题

1．一个顺序栈一旦被声明，其占用空间的大小（ ）。 A．已固定 B．可以改变 C．不能固定 D．动态变化 2．链栈和顺序栈相比，有一个比较明显的缺点，即（ ）。 A．插入操作更加方便 B．通常不会出现栈满的情况 C．不会出现栈空的情况 D．删除操作更加方便 3．用单链表表示的链式队列的队头在链表的（ ）位置。 A．链头 B．链尾 C．链中 D．任意位置

4．在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入缓冲区中，而打印机则从缓冲区中取出数据打印，该缓冲区应该是一个（ ）结构。

A．堆栈 B．队列 C．数组 D．先性表

5．若已知一个栈的入栈序列是1，2，3，…，30，其输出序列是p1,p2,p3,…pn，若p1=30，则p10为（ ）。

A．11 B．20 C．19 D．21

6．循环队列A[m] 存放其元素，用front和rear分别表示队头及队尾，则循环队列满的条件是（ ）。

A．（rear+1)%m=front

栈和队列

一、选择题

1、一个栈的输入序列为：a，b，c，d，e，则栈的不可能输出的序列是（ C ）。

A. a,b,c,d,e B. d,e,c,b,a C. d,c,e,a,b D. e,d,c,b,a 2、判断一个循环队列Q（最多n个元素）为满的条件是（ C ）。

A. Q->rear==Q->front B. Q->rear==Q->front+1 C. Q->front==(Q->rear+1)%n D. Q->front==(Q->rear-1)%n 3、设计一个判别表达式中括号是否配对的算法，采用（ D ）数据结构最佳。 A. 顺序表 B. 链表 C. 队列 D. 栈 4、

5、一个栈的输入序列为：1,2,3,4，则栈的不可能输出的序列是（ D ）。

A. 1243 B. 2134 C. 1432 D. 4312 E. 3214 6、若用一个大小为6的数组来实现循环队列，且当rear和front的值分别为0，3。当从队列中删除一个元素，再加入两个元素后，re

实验三 栈和队列

一、实验目的

1.了解栈和队列的特性。 2.掌握栈的顺序表示和实现。 3.掌握栈的链式表示和实现。 4.掌握队列的顺序表示和实现。 5.掌握队列的链式表示和实现。

6.掌握栈和队列在实际问题中的应用。

二、实验内容

实验2.1栈的顺序表示和实现

编写一个程序实现顺序栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能：

(1)初始化顺序栈。 (2)插入元素。 (3)删除栈顶元素。 (4)取栈顶元素。 (5)遍历顺序栈。 (6)置空顺序栈。

实验2. 2栈的链式表示和实现

编写一个程序实现链栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能：

(1)初始化链栈。 (2)链栈置空。 (3)入栈。 (4)出栈。

(5)取栈顶元素。 (6)遍历链栈。

实验2. 3队列的顺序表示和实现

编写一个程序实现顺序队列的各种基本运算（采用循环队列），并在此基础上设计一个主程序，完成如下功能： (1)初始化队列。 (2)建立顺

电子信息工程学院2013级《数据结构》实验报告

姓名

学号

实验项目 实验内容 栈和队列及其应用（I） 1．采用顺序存储结构，实现栈的存储和基本操作。 栈的抽象数据类型定义参见教材第45页。 栈的顺序存储结构定义参见教材第46页。 2．采用顺序存储结构，实现队列的存储和基本操作 队列的抽象数据类型定义参见教材第59页。 队列的顺序存储结构定义参见教材第64页。 算法设计与程序实现： 算法分析 本次实验主函数采用顺序结构，主函数调用自己编写的头文件DataStructure_LinearList.h中的相关功能函数，完成实验要求。 程序实现步骤： 1、顺序栈结构的基本操作：首先初始化一个顺序栈结构，然后输入需入栈的元素个数N，通过一个循环依次输入N个元素，在输入的同时调用入栈函数,这样就完成了N个元素的入栈操作，随后调用返回栈顶元素的函数，返回栈顶元素，接着通过循环调用出栈函数完成出栈操作，最后销毁栈结构。当然在进行入栈和出栈操作时，会使用判断栈是否为空、对栈进行遍历等操作，这样就实现了对栈的基本操作。 2、栈结构的基本应用：（1）将输入的十进制数转换为二进制数。首先初始化一个栈结构，构造一个空栈，然后输入十进制数N，根据

实验二 栈和队列的基本操作及其应用

一、实验内容

回文判断

[问题描述]

对于一个从键盘输入的字符串，判断其是否为回文。回文即正反序相同。如“abba”是回文，而“abab”不是回文。

[基本要求]

（1）数据从键盘读入； （2）输出要判断的字符串；

（3）利用栈的基本操作对给定的字符串判断其是否是回文，

若是则输出“Yes”，否则输出“No”。

二、概要设计 算法设计：

实验要求用栈的基本基本操作实现判断是否为回文，则必须定

义栈的初始化和出栈、入栈；另外为了判断是否是回文，则定义一个数组，便于比较。在字符串输入的时候，保证同时进入数组和栈里。因为栈的后进先出的输出特性，在比较的时候，用while语句判断：当栈输出的元素和数组的对应的元素相等，就继续比较，直到比较完毕，相等则输出YES，在比较的过程中，若有一个不相等，则输出NO。而判断while语句结束的条件有两个:一是在比较的过程中，如果有不相等的两个元素，输出“NO”，跳出while语句；二是正常结束，即字符串和栈里储存的元素完全相等，则输出YES。

流程图：

计科 092

刘亚红

20090814212

开始

定 义 数 组 初始化栈

输入字符c

s!='#' 否 是 将字符同时进入 数组和栈

输入字符c i加1

栈为不空

软件114班李大宝 201100834416

数 据 结 构 实 验 报 告

（二） 姓名: 李 大 宝 学院：计算机学院 班级：软件114班

第1页

软件114班李大宝 201100834416

实验 二 栈和队列的基本操作实现及其应用 一、实验目的

1、熟练掌握栈和队列的基本操作在两种存储结构上的实现。 2、会用栈和队列解决简单的实际问题。

二、实验内容

题目一

试写一个算法，判断依次读入的一个以@为结束符的字符序列，是否为回文。所谓“回文“是指正向读和反向读都一样的一字符串,如“321123”或“ableelba”。

一、相关常量及结构定义：

# define STACK_INIT_SIZE 100 # define STACKINCREMENT 10 # define OK 1 # define ERROR 0

typedefcharSElemType; //把char类型定义为SElemType //栈类型定义

typedefstructSqStack

{ SElemType *base; //栈底

SE