03栈和队列1

第三章 栈和队列

【实训 1】栈的应用

1．实训说明

本实训是关于栈的应用，栈在各种高级语言编译系统中应用十分广泛，在本实训程序中，

利用栈的“先进后出”的特点，分析 C 语言源程序代码中的的括号是否配对正确。通过本对

本实训的学习，可以理解的基本操作的实现。

本实训要求设计一个算法，检验 C 源程序代码中的括号是否正确配对。对本算法中的栈

的存储实现，我们采用的是顺序存储结构。要求能够在某个 C源程序上文件上对所设计的算

法进行验证。

2．程序分析

（1）int initStack(sqstack **s) 初始化一个栈

（2）int push(sqstack *s,char x) 入栈，栈满时返回 FALSE

（3）char pop(sqstack *s) 出栈，栈空时返回 NULL

（4）int Empty(sqstack *s) 判断栈是否为空，为空时返回 TRUE

（5）int match(FILE *f) 对文件指针f 对指的文件进行比较括号配对检验，从文件

中每读入一个字符 ch=fgetc(f)，采用多路分支 switch(ch)进行比较：

①若读入的是“[”、“{”或“（”，则压入栈中，

②若读入的是“]”，则：若栈非空，则出栈，判断出栈符号是否等于“[”，不相

等，则返回 FALSE。

③若读入的是“}”，则：若栈非空，则出栈，判断出栈符号是否等于“{”，不相

等，则返回 FALSE。

④若读入的是“）”，则：若栈非空，则出栈，判断出栈符号是否等于“（”，不相

实验预备知识：

1．熟练运用指针进行程序设计，掌握结构体指针。

2．掌握使用结构体指针访问结构体变量。

3．掌握指针作为函数的参数使用。

4．理解栈和队列的含义、目的和处理方法。

一、实验目的

1. 理解和掌握栈和队列的类型定义方法。

2. 掌握栈和队列中的基本运算，包括创建、判空及判满、出队（栈）/入队（栈）等基本操作。

3.

学习利用栈或队列解决实际问题

二、实验要求（本次实验要求上交）

【题目1】----验证型

实现链栈各种基本运算的算法。参考代码见（文件夹4-1）

该程序主函数完成如下功能：

（1） 初始化链栈

（2） 判断链栈是否为空

（3） 元素依次入栈

（4） 输出该链栈的长度

（5） 输出从栈顶到栈底的元素

（6） 销毁该链栈

该工程的程序结构图如下图所示：

程序运行截图：

实现循环队各种基本运算的算法。参考代码见（文件夹4-2）

该程序主函数完成如下功能：

（1） 初始化队列

（2） 判断循环队是否为空

（3） 元素依次入队

（4） 队列元素出队

（5） 输出出队序列

（6） 销毁该循环队

该工程的程序结构图如下图所示：

GetPop

algo3-3.cpp exp3-3.cpp

InitQuequ enQuequ DestroyQuequ QuequEmpty deQuequ main

algo3-2.cpp exp3-2.cpp

InitStack Pop DestroyStack StackEmpty Push main 程序运行截图：

【题目2】

编写一个程序，利用栈的特性实现二进制转换为八进制。(给出了二进制转换为十进制的参考算法供大家参考，见bin_dec.c)

算法分析：

需要将二进制分三位一组进行出栈运算，然后定义一个新的栈，并把转换的八进制分别进行入栈，除了3后还有余数，在将余数运行并入栈，最后再出栈输出。

请将源程序附录于此：

#include

#include

实验一 栈和队列的应用

一、实验目的

1、掌握栈的编写和应用

2、掌握队列的编写和应用

二、实验内容

1、分别使用STL中的栈和自己编写的栈类，实现序列的反转

（1）简单修改下面代码，实现使用STL中的栈进行序列的反转，编译运行

#include

int main( )

/* Pre: The user supplies an integer n and n decimal numbers.

Post: The numbers are printed in reverse order.

Uses: The STL class stack and its methods */

{

int n;

double item;

stack numbers; // declares and initializes a stack of numbers

cout << " Type in an integer n followed by n decimal numbers."

<< endl

<< " The numbers will be printed in reverse order."

<< endl;

cin >> n;

for (int i = 0; i < n; i++) {

cin >> item;

numbers.push(item);

}

cout << endl << endl;

while (!numbers.empty( )) {

cout << numbers.top( ) << " "; numbers.pop( );

}

cout << endl;

}

提示：

（1）由于程序是用了STL（标准模板库，可以简单的看成是一个函数库，在其中有各种有用的类、函数和算法），栈在其中有实现。栈在STL中的实现用到了类模板，也就是说其栈是独立于类型的，模板提供参数化类型，也就是能将类型名作为参数传递给接收方来建立类或函数。比如stack numbers;中就是声明了一个栈，这个栈中存放的数据类型为double。

第3章 栈和队列

一、选择题

1. 对于栈操作数据的原则是（ ）。

A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序

2. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ ）。

A. 不确定 B. n-i+1 C. i D. n-i

3. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ ）

A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6

4. 输入序列为ABC，可以变为CBA时，经过的栈操作为（ ）

A. push,pop,push,pop,push,pop B. push,push,push,pop,pop,pop

C. push,push,pop,pop,push,pop D. push,pop,push,push,pop,pop

5. 若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈( i =1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（ ）。

A. top[2]-top[1]=0 B. top[1]+1=top[2]

C. top[1]+top[2]=m D. top[1]=top[2]

6. 栈在（ ）中应用。

A. 递归调用 B. 子程序调用 C. 表达式求值 D. A，Ｂ，Ｃ

7. 表达式a*(b+c)-d的后缀表达式是( )。

A．abcd*+- B. abc+*d- C. abc*+d- D. - +*abcd

8. 设计一个判别表达式中左，右括号是否配对出现的算法，采用（ ）数据结构最佳。