数据结构复习-栈和队列
第三章栈和队列
从数据结构的角度看: 它们和线性表相同
从数据类型的角度看: 它们和线性表不同
线性表栈队列
Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x)
n+1)≤ i ≤( 1
Delete(L, i) Delete(S, n) Delete(Q, 1)
n)≤ i ≤ ( 1
3.1 栈的类型定义
ADT Stack {
数据对象：D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 }
数据关系：R1＝{
约定an 端为栈顶，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 Stack
3.2 栈的应用举例
例一、数制转换
十进制数N和其他d进制数的转换是计算机实现计算的基本问题，其解决方法很多，其中一个简单算法基于下列原理：
N = (N div d)×d + N mod d
(其中：div 为整除运算，mod 为求余运算）
例如：（1348)10 = (2504)8 ，其运算过程如下：
N N div 8 N mod 8
1348 168 4
168 21 0
21 2 5
2 0 2
假设现要编制一个满足下列要求的程序：对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数。由于上述计算过程是从低位到高位顺序产生八进制数的各个数位，而打印输出，一般来说应从高位到低位进行，恰好和计算过程相反。因此，若将计算过程中得到的八进制数的各位顺序进栈，则按出栈序列打印输出的即为与输入对应的八进制数。
void conversion () {
// 对于输入的任意一个非负十进制整数，打印输出
// 与其等值的八进制数
InitStack(S); // 构造空栈
scanf ("%d",N);
while (N) {
Push(S, N % 8);
N = N/8;
}
while (!StackEmpty(S)) {
Pop(S,e);
printf ( "%d", e );
}
} // conversion
这是利用栈的后进先出特性的最简单的例子。在这个例子中，栈操作的序列是直线式的，即先一味地入栈，然后一味地出栈。也许，有的读者会提出疑问：用数组直接实现不也很简单吗？仔细分析上述算法不难看出，栈的引入简化了程序设计的问题，划分了不同的关注层次，使思考范围缩小了。而用数组不仅掩盖了问题的本质，还要分散精力去考虑数组下标增减等细节问题。
例二、括号匹配的检验
假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，即（［］（））或［（［］［］）］等为正确的格式，［（］）或（［（））或(( )])均为不正确的格式。检验括号是否匹配的方法可用"期待的急迫程度"这个概念来描述。例如考虑下列括号序列：
[ ( [ ] [ ] ) ]
1 2 3 4 5 6 7 8
分析可能出现的不匹配的情况:
1) 到来的右括弧非是所―期待‖的;
2) 到来的是―不速之客‖;
3) 直到结束，也没有到来所―期待‖的。
status matching(string& exp) {
// 检验表达式中所含括弧是否正确嵌套，若是，则返回
// OK，否则返回ERROR
int state = 1;
while (i<=length(exp) && state) {
swith of exp[i] {
case 左括弧: { Push(S,exp[i]); i++; break; }
case ")":
{ if (NOT StackEmpty(S) && GetTop(S) = "(")
{ Pop(S,e); i++; }
else { state = 0 }
break;
}
…… }
}
if ( state && StackEmpty(S) ) return OK
else return ERROR;
}
例三、行编辑程序问题
一个简单的行编辑程序的功能是：接受用户从终端输入的程序或数据，并存入用户的数据区。
每接受一个字符即存入用户数据区‖不恰当。
较好的做法是，设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区。允许用户输入出差错，并在发现有误时可以及时更正。
例如，可用一个退格符―#‖表示前一个字符无效；可用一个退行符―@‖，表示当前行中的字符均无效。
例如，假设从终端接受了这样两行字符：
whli##ilr#e（s#*s)
outcha@putchar(*s=#++);
则实际有效的是下列两行：
while (*s)
putchar(*s++);
void LineEdit() {
// 利用字符栈S，从终端接收一行并传送至调用过程
// 的数据区。
InitStack(S); //构造空栈S
ch = getchar(); //从终端接收第一个字符
while (ch != EOF) { //EOF为全文结束符
while (ch != EOF && ch != '\n') {
switch (ch) {
case '#' : Pop(S, c); break;
// 仅当栈非空时退栈
case '@': ClearStack(S); break; // 重置S为空栈
default : Push(S, ch); break;
// 有效字符进栈，未考虑栈满情形
}
ch = getchar(); // 从终端接收下一个字符
}
将从栈底到栈顶的字符传送至调用过程的数据区；
ClearStack(S); // 重置S为空栈
if (ch != EOF) ch = getchar();
}
DestroyStack(S);
}
例四、迷宫求解
求迷宫中从入口到出口的所有路径是一个经典的程序设计问题。由于计算机解迷宫时，通常用的是―穷举求解‖的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此，在求迷宫通路的算法中应用―栈‖也就是自然而然的事了。
假设迷宫如下图所示:
# # # # # # # # # #
# $ $ $ # #↓→#
# $ $ $ # #↓#
$ $ # # #←↓#
# # # # #↓#
# # #↓→→#
# #↓→→# #
# # #↓# # # # #
#Θ→→→#
# # # # # # # # # #
假设―当前位置‖指的是―在搜索过程中某一
时刻所在图中某个方块位置‖，则求迷宫中一条路
径的算法的基本思想是：若当前位置"可通"，则纳
入"当前路径"，并继续朝―下一位置‖探索，即切
换―下一位置‖为―当前位置‖，如此重复直至到
达出口；若当前位置―不可通‖，则应顺着―来向‖
退回到―前一通道块‖，然后朝着除―来向‖之外的其他方向继续探索；若该通道块的四周四个方块均―不可通‖，则应从―当前路径‖上删除该通道块。所谓―下一位置‖指的是―当前位置‖四周四个方向（东、南、西、北）上相邻的方块。假设以栈S记录―当前路径‖，则栈顶中存放的是―当前路径上最后一个通道块‖。由此，―纳入路径‖的操作即为―当前位置入栈‖；―从当前路径上删除前一通道块‖的操作即为―出栈‖。
求迷宫中一条从入口到出口的路径的算法可简单描述如下：
设定当前位置的初值为入口位置；
do｛
若当前位置可通，
则｛将当前位置插入栈顶； // 纳入路径
若该位置是出口位置，则结束；
// 求得路径存放在栈中
否则切换当前位置的东邻方块为新的当前位置；
｝
否则{
若栈不空且栈顶位置尚有其他方向未被探索，
则设定新的当前位置为: 沿顺时针方向旋转
找到的栈顶位置的下一相邻块；
若栈不空但栈顶位置的四周均不可通，
则｛删去栈顶位置； // 从路径中删去该通道块
若栈不空，则重新测试新的栈顶位置，
直至找到一个可通的相邻块或出栈至栈空；
｝
｝while (栈不空）；
在此，尚需说明一点的是，所谓当前位置可通，指的是未曾走到过的通道块，即要求该方块位置不仅是通道块，而且既不在当前路径上（否则所求路径就不是简单路径），也不是曾经纳入过路径后又从路径上删除的通道块（否则只能在死胡同内转圈）。
typedef struct {
int ord; // 通道块在路径上的―序号‖
PosType seat; // 通道块在迷宫中的―坐标位置‖
int di; // 从此通道块走向下一通道块的―方向‖
} SElemType; // 栈的元素类型
Status MazePath ( MazeType maze, PosType start,
PosType end ) {
// 若迷宫maze中从入口start到出口end的通道，
// 则求得一条存放在栈中（从栈底到栈顶），并返回
// TRUE；否则返回FALSE
InitStack(S); curpos = start;
// 设定―当前位置‖为―入口位置‖
curstep = 1; // 探索第一步
do {
if (Pass (curpos)) {
// 当前位置可以通过，即是未曾走到过的通道块
FootPrint (curpos); // 留下足迹
e = ( curstep, curpos, 1 );
Push (S,e); // 加入路径
if ( curpos == end ) return (TRUE);
// 到达终点（出口）
curpos = NextPos ( curpos, 1 );
/ 下一位置是当前位置的东邻
curstep++; // 探索下一步
}
else { // 当前位置不能通过
if (!StackEmpty(S)) {
Pop (S,e);
while (e.di==4 && !StackEmpty(S)) {
MarkPrint (e.seat); Pop (S,e);
// 留下不能通过的标记，并退回一步
} // while
if (e.di<4) {
e.di++; Push ( S, e);
// 换下一个方向探索
curpos = NextPos (curpos, e.di );
// 设定当前位置是该新方向上的相邻块
} // if
} // if
} // else
} while ( !StackEmpty(S) );
return (FALSE);
} // MazePath
例五、表达式求值
限于二元运算符的表达式定义:
表达式::= (操作数) + (运算符) + (操作数)
操作数::= 简单变量| 表达式
简单变量:: = 标识符| 无符号整数
在计算机中，表达式可以有三种不同的标识方法
设 Exp = S1 + OP + S2
则称 OP + S1 + S2 为表达式的前缀表示法
称 S1 + OP + S2 为表达式的中缀表示法
称 S1 + S2 + OP 为表达式的后缀表示法
可见，它以运算符所在不同位置命名的。
? d / e) - b + (c ?例如: Exp = a f
c /
d
e f-? a b ?前缀式: +
? d / e - b + c ?中缀式: a f
? f - c d e / ?后缀式: a b +
结论:
1) 操作数之间的相对次序不变;
2) 运算符的相对次序不同;
3) 中缀式丢失了括弧信息，致使运算的次序不确定;
4) 前缀式的运算规则为:连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式;
5) 后缀式的运算规则为:
运算符在式中出现的顺序恰为表达式的运算顺序;λ
每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式;λ
如何从后缀式求值？λ
先找运算符，后找操作数
如何从原表达式求得后缀式？λ
分析―原表达式‖ 和―后缀式‖中的运算符:
f? d / e - c ?原表达式: a + b
+ d e /?后缀式: a b c -?f
** / ?-运算符# ( +
优先数 -1 0 1 1 2 2
每个运算符的运算次序要由它之后的一个运算符来定，若当前运算符的优先数小，则暂不进行; 否则立即进行。
表达式求值的规则:
1) 设立运算符栈和操作数栈;
2) 设表达式的结束符为―#‖,予设运算符栈的栈底为―#‖
3) 若当前字符是操作数，则进操作数栈;
4) 若当前运算符的优先数高于栈顶运算符，则进栈;
5) 否则，退出栈顶运算符作相应运算;
6) ―(‖对它之前后的运算符起隔离作用，―)‖可视为自相应左括弧开始的表达式的结束符。
算法描述如下:
OperandType EvaluateExpression() {
// 算术表达式求值的算符优先算法。设OPTR和OPND
// 分别为运算符栈和运算数栈，OP为运算符集合。
InitStack (OPTR); Push (OPTR, '#');
initStack (OPND); c = getchar();
while (c!= '#' || GetTop(OPTR)!= '#') {
if (!In(c, OP)) { Push((OPND, c); c = getchar(); }
// 不是运算符则进栈
else
switch (precede(GetTop(OPTR), c) {
case '<': // 栈顶元素优先权低
Push(OPTR, c); c = getchar();
break;
case '=': // 脱括号并接收下一字符
Pop(OPTR, x); c = getchar();
break;
case '>'# // 退栈并将运算结果入栈
Pop(OPTR, theta);
Pop(OPND, b); Pop(OPND, a);
Push(OPND, Operate(a, theta, b));
break;
} // switch
} // while
return GetTop(OPND);
} // EvaluateExpression
例六、实现递归
在高级语言编制的程序中，调用函数与被调用函数之间的链接和信息交换必须通过栈例进行。
当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三件事:
1) 将所有的实在参数、返回地址等信息传递给被调用函数保存;
2) 为被调用函数的局部变量分配存储区;
3) 将控制转移到被调用函数的入口。
从被调用函数返回调用函数之前，应该完成:
1) 保存被调函数的计算结果;
2) 释放被调函数的数据区;
3) 依照被调函数保存的返回地址将控制转移到调用函数。
多个函数嵌套调用的规则是:后调用先返回
此时的内存管理实行―栈式管理‖
递归过程指向过程中占用的数据区，称之为递归工作栈
每一层的递归参数合成一个记录，称之为递归工作记录
栈顶记录指示当前层的执行情况，称之为当前活动记录
栈顶指针，称之为当前环境指针
例如:
void hanoi (int n, char x, char y, char z)
// 将塔座x上按直径由小到大且至上而下编号为1至n
// 的n个圆盘按规则搬到塔座z上，y可用作辅助塔座。
1 {
2 if (n==1)
3 move(x, 1, z); // 将编号为１的圆盘从x移到z
4 else {
5 hanoi(n-1, x, z, y); // 将x上编号为１至n-1的圆
// 盘移到y, z作辅助塔
6 move(x, n, z); // 将编号为n的圆盘从x移到z
7 hanoi(n-1, y, x, z); // 将y上编号为１至n-1的圆盘
// 移到z, x作辅助塔
8 }
9 }
3.3 栈类型的实现
顺序栈
类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针。链栈
利用链表实现栈，注意链表中指针的方向是从栈顶到栈底。
# include LinkList.h
template
class stack {
private :
List
public :
// constructor
stack(void);
// access method
BOOL stackEmpty(void);
int stackLength(void);
ElemType* getTop(void);
// modification method
void Push( ElemType* item);
ElemType* Pop(void);
void clearStack(void);
};
template
void stack
{
stackList.insFirst(item);
}
template
ElemType* stack
{
if stackList.listEmpty( ) return NULL;
else return stackList.delFirst( )
}
3.4 队列的类型定义
ADT Queue {
数据对象：D＝{ai | ai∈ElemSet, i=1,2,...,n, n≥0}
数据关系：R1＝{ | ai-1, ai ∈D, i=2,...,n}
约定其中a1 端为队列头，
an 端为队列尾。
基本操作：
InitQueue(&Q)
操作结果：构造一个空队列Q。
DestroyQueue(&Q)
初始条件：队列Q已存在。
操作结果：队列Q被销毁，不再存在。
ClearQueue(&Q)
初始条件：队列Q已存在。
操作结果：将Q清为空队列。
QueueEmpty(Q)
初始条件：队列Q已存在。
操作结果：若Q为空队列，则返回TRUE，
否则返回FALSE。
QueueLength(Q)
初始条件：队列Q已存在。
操作结果：返回Q的元素个数，即队列的长度。
GetHead(Q, &e)
初始条件：Q为非空队列。
操作结果：用e返回Q的队头元素。
EnQueue(&Q, e)
初始条件：队列Q已存在。
操作结果：插入元素e为Q的新的队尾元素。
DeQueue(&Q, &e)
初始条件：Q为非空队列。
操作结果：删除Q的队头元素，并用e返回其值。
} ADT Queue
3.5 队列类型的实现
链队列——链式映象
# include LinkList.h
template
class Queue {
private :
List
public :
// constructor
Queue(void):queueList( );
~Queue(void)
// access method
BOOL queueEmpty(void)
{ return queueList.listEmpty( ) }
int queueLength(void)
{ return queueList.listSize( ) }
ElemType* getHead(void);
// modification method
void enQueue( ElemType* pitem);
ElemType* deQueue(void);
void clearQueue(void);
};
template
void Queue
queueList.addT ail(pitem);
}
template
ElemType* Queue
{
if queueList.listEmpty( ) return NULL;
else return queueList.delFirst( )
}
循环队列——顺序映象
const int MaxQSize = 100;
template
class Queue {
private :
int front, rear, curSize, maxSize;
ElemType* qList;
public :
// constructor
Queue(void);
~Queue(void)
// access method
BOOL queueEmpty(void);
BOOL queueFULL(void);
int queueLength(void);
ElemType* getHead(void);
// modification method
void enQueue( ElemType* item);
ElemType* deQueue(void);
void clearQueue(void);
};
3.6 队列应用举例——排队问题的系统仿真
一、需求分析和规格说明
编制一个事件驱动仿真程序以模拟理发馆内一天的活动，要求输出在一天的营业时间内，到达的顾客人数、顾客在馆内的平均逗留时间和排队等候理发的平均人数以及在营业时间内空椅子的平均数。假设理发馆内设有N把理发椅，一天内连续营业T小时。在T小时内顾客到达的时间及顾客理发所需时间均随机生成，过了营业时间，不再有顾客进门，但仍需继续为已进入店内的顾客理发，直至最后一名顾客离开为止。
二、概要设计
1. 主程序为:
void BarberShop_Simulation( int chairNum, int CloseTime) {
// 理发店业务模拟，统计一天内顾客在店内逗留的平均时间
// 和顾客在等待理发时排队的平均长度以及空椅子的平均数
OpenForDay; // 初始化
while MoreEvent do {
EventDrived(OccurTime, EventType); // 事件驱动
switch (EventType) {
case 'A' : CustomerArrived; break; // 处理到达事件
case 'D' : CustomerDeparture; break; // 处理离开事件
default : Invalid;
} // switch
} // while
CloseForDay; // 计算平均逗留时间和排队的平均长度
} // BarberShop_Simulation
2. 数据类型为:
ADT Event (事件) {
数据对象: D = { 事件的发生时刻，事件类型}
数据关系: R = { }
基本操作:
Initiate(&E,oT, eT);
操作结果: 产生一个发生时间为oT, 事件类型为eT
的事件E;
GetOccurTime(ev);
初始条件: 事件ev已存在，
操作结果: 返回该事件的发生时间;
GetEventType(ev);
初始条件: 事件ev已存在;
操作结果: 返回该事件的类型;
}
ADT customer(顾客) {
数据对象: D = { 进门时刻，理发所需时间};
数据关系: R = { }
基本操作:
Initiate(&P,aT, cT);
操作结果: 产生一个进门时刻为aT, 理发时间为cT
的顾客P;
GetArrivalTime(Ps);
初始条件: 顾客Ps已存在，
操作结果: 返回该顾客的进门时刻;
GetCutTime(Ps);
初始条件: 顾客Ps已存在;
操作结果: 返回该顾客的理发时间;
}
ADT orderedList(有序表) {
数据对象: 是上述定义的事件的集合
数据关系: 按事件的发生时刻自小至大有序
基本操作:
在线性表的操作的基础上添加一个有序表的插入
Insert(&OL, x)
初始条件: 有序表OL已存在;
操作结果: 在有序表中插入x, 并保持表的有序性;
}
ADT (数据元素为上述定义的顾客的)队列
三、详细设计
class Event {
private:
int occurTime;
char eventType;
public:
Event(int oT, char tp):occurTime(oT), eventType(tp) {} int evTime(void) { return occurTime }
char evType(void) { return eventType }
}
class Customer {
private:
int arrivalTime;
int cutTime;
public:
Customer(int aT, char cT):
arrivalTime(oT), cutTime(ct) { }
int avTime(void) { return arrivalTime }
int cuTime(void) { return cutTime }
}
template
class orderedList : public List
{
public:
orderedList(void); // 构造函数，初始化一个空表
int locate(ElemType* pitem);
// 在有序表中查询数据元素pitem, 若存在，则移
// 动当前指针指向该结点并返回1，否则移动当前
// 指针指向第一个大于它的结点并返回0
void insert( ElemType* item);
// 插入数据元素item, 并保持表的有序性
}
template
void orderedList
insert(ElemType* item)
{
if ( List
{ List
}
orderedList
Queue
void BarberShop_Simulation( int N, int CloseTime) {
OpenForDay;
while (Not evList.Empty) {
en = evList.delFirst;
swith en.evType {
A′: CustomerArr ived(en);'case break;
D′: CustomerDeparture(en); break;'case default: Invalid; break;
}
}
CloseForDay;
}
void CustomerArrived(Event en ) {
//
Event* newAEvent, newDEvent;
Customer* newCustomer;
++CustomerNum;
Random(durtime, intertime);
nextAT = en.evTime + intertime;
if (nextAT newAEvent = new Event( nextAT, ?A‘); evList.insert(newEvent); } if (FreeChair) { dT = en.evTime + durtime; newDEvent = new Event(dT, ?D‘); ev.List.insert(newDEvent); TotalTime += durtime; --FreeChair; } else { newCustomer = new Customer(en.evTime, durtime); Q.enQueue } TotalQLength += Q.queueLength; } // CustomerArrived void CustomerDeparture(Event en) { // Event* newDEv; if (Q.queueEmpty) ++FreeChair; else { customer *cm = Q.deQueue; nextDT = en.evTime + cm.cuTime; newDEv = new Event(nextDT, ?D‘); evList.insert(newDEv); TotalTime += (en.evTime – cm.avTime + cm.cuTime); } FreeChairNum += FreeChair; } // CustomerDeparture 第3章栈和队列 一、选择题 1.栈结构通常采用的两种存储结构是（A ）。 A、顺序存储结构和链表存储结构 B、散列和索引方式 C、链表存储结构和数组 D、线性链表结构和非线性存储结构 2.设栈ST 用顺序存储结构表示，则栈ST 为空的条件是（ B ） A、ST.top-ST.base<>0 B、ST.top-ST.base==0 C、ST.top-ST.base<>n D、ST.top-ST.base==n 3.向一个栈顶指针为HS 的链栈中插入一个s 结点时，则执行（ C ） A、HS->next=s; B、s->next=HS->next；HS->next=s; C、s->next=HS；HS=s; D、s->next=HS；HS=HS->next; 4.从一个栈顶指针为HS 的链栈中删除一个结点，用x 保存被删除结点的值，则执行（ C） A 、x=HS；HS=HS->next; B 、HS=HS->next；x=HS->data; C 、x=HS->data；HS=HS->next; D 、s->next=Hs；Hs=HS->next; 5.表达式a*(b+c)-d 的后缀表达式为（ B ） A、abcdd+- B、abc+*d- C、abc*+d- D、-+*abcd 6.中缀表达式A-（B+C/D）*E 的后缀形式是（ D ） A、AB-C+D/E* B、ABC+D/E* C、ABCD/E*+- D、ABCD/+E*- 7.一个队列的入列序列是1，2，3，4，则队列的输出序列是（ B ） A、4，3，2，1 B、1，2，3，4 C、1，4，3，2 D、3，2，4，1 8.循环队列SQ 采用数组空间SQ.base[0,n-1]存放其元素值，已知其头尾指针分别是front 和rear，则判定此循环队列为空的条件是（） A、Q.rear-Q.front==n B、Q.rear-Q.front-1==n C、Q.front==Q.rear D、Q.front==Q.rear+1 9.循环队列SQ 采用数组空间SQ.base[0,n-1]存放其元素值，已知其头尾指针分别是front 和rear，则判定此循环队列为满的条件是（） A、Q.front==Q.rear B、Q.front!=Q.rear C、Q.front==(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n 10.若在一个大小为6 的数组上实现循环队列，且当前rear 和front 的值分别为0 和3，当从 队列中删除一个元素，再加入两个元素后，rear 和front 的值分别为（） A、1，5 B、2, 4 C、4，2 D、5，1 11.用单链表表示的链式队列的队头在链表的（）位置 A、链头 B、链尾 C、链中 12.判定一个链队列Q（最多元素为n 个）为空的条件是（） A、Q.front==Q.rear B、Q.front!=Q.rear C、Q.front==(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n 13.在链队列Q 中，插入s 所指结点需顺序执行的指令是（） A 、Q.front->next=s；f=s; B 、Q.rear->next=s；Q.rear=s; 贵州大学实验报告 学院：计信学院专业：网络工程班级：091班姓名XXX 学号XXXXXXXXX 实验组 5 实验时间2011.12.02 指导教师XXXXX 成绩 实验项目名称 队列的实现 实 验目的1．掌握队列的思想及其存储实现。2．掌握队列的常见算法的程序实现。 实验原理1.根据实验内容编程，上机调试、得出正确的运行程序。 2. 编译运行程序，观察运行情况和输出结果。 3. 写出实验报告（包括源程序和运行结果）。 实验内容 1．采用链式存储实现队列的初始化、入队、出队操作。 2．采用顺序存储实现循环队列的初始化、入队、出队操作。 3．在主函数中设计一个简单的菜单，分别测试上述算法。 实验数据及其步骤链式存储队列： #include 实验编号：3四川师大《数据结构》实验报告2016年10月29日 实验三栈和队列及其应用_ 一．实验目的及要求 （1）掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运用它们； （2）本实验训练的要点是“栈”的观点及其典型用法； （3）掌握问题求解的状态表示及其递归算法，以及由递归程序到非递归程序的转化方法。 二．实验内容 （1）编程实现栈在两种存储结构中的基本操作（栈的初始化、判栈空、入栈、出栈等）； （2）应用栈的基本操作，实现数制转换（任意进制）； （3）编程实现队列在两种存储结构中的基本操作（队列的初始化、判队列空、入队列、出队列）； （4）利用栈实现任一个表达式中的语法检查（括号的匹配）。 （5）利用栈实现表达式的求值。 注：（1）～（3）必做，（4）～（5）选做。 三．主要仪器设备及软件 （1）PC机 （2）Dev C++ ,Visual C++, VS2010等 四．实验主要流程、基本操作或核心代码、算法片段（该部分如不够填写，请另加附页）（1）编程实现栈在两种存储结构中的基本操作（栈的初始化、判栈空、入栈、出栈等）； A.顺序储存： 代码部分： 栈" << endl; cout << " 2.出栈" << endl; cout << " 3.判栈空" << endl; cout << " 4.返回栈顶部数据" << endl; cout << " 5.栈长" << endl; cout << " 0.退出系统" << endl; cout << "你的选择是：" ; } 链式储存： 代码部分： 栈"< 数据结构：栈和队列 单选题： 1.在一个具有n个单元的顺序栈中，假定以地址低端作为栈底，以top作为栈顶指针，则当做退栈处 理时，top变化为_____。 A. top不变 B. top＝-n C. top＝top-1 D.top=top+1 2.向顺序栈中压入元素时，是_____。 A.先移动栈顶指针，后存入元素 B.先存入元素，后移动栈顶指针 3.在一个顺序存储的循环队列中，队首指针指向队首元素的_____。 A.前一个位置 B.后一个位置 C.队首元素位置 4.若进栈序列为1,2,3,4,进栈过程中可以出栈，则_____不可能是一个出栈序列。 A.3,4,2,1 B.2,4,3,1 C.1,4,3,2 D.3,2,1,4 5.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾指针，则判断队 空的条件是_____。 A.front= =rear+1 B.front+1= =rear C.front= =rear D.front= =0 6.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾指针，则判断队 满的条件是_____。 A.\rear % n= =front B.(rear-1) % n= =front C.(rear-1) % n= =rear D.(rear+1) % n= =front 7.向一个栈项指针为hs的链栈中插入一个*s结点时，则执行_____。 A.hs->next=s; B.s->next=hs->next; hs->next=s; C.s->next=hs；hs=s; D.s->next=hs; hs=hs->next; 8.在一个链队列中，假定front和rear分别为队首指针和队尾指针，则进行插入*s结点的操作时应执 行_____。 A.front->next=s; front=s; B.rear->next=s; rear=s; C.front=front->next; D.front=rear->next; 9.栈的特点是_______队的特点是______ A.先进先出 B.先进后出B|A 10.栈和队列的共同点是_______。 A.都是先进后出 B.都是先进先出 C.只允许在端点处插入和删除元素 D.没有共同点 11.一个栈的进栈序列是a,b,c,d,e,则栈的不可能的输出序列是________。 A.edcba B.decba C.dceab D.abcde 12.若己知一个栈的进栈序列是1,2,3,…,n,其输出序列为p1,p2,p3,…,pn,若p1=n,则pi(1 实验二堆栈和队列 实验目的： 1.熟悉栈这种特殊线性结构的特性； 2.熟练并掌握栈在顺序存储结构和链表存储结构下的基本运算； 3.熟悉队列这种特殊线性结构的特性； 3.熟练掌握队列在链表存储结构下的基本运算。 实验原理： 堆栈顺序存储结构下的基本算法； 堆栈链式存储结构下的基本算法； 队列顺序存储结构下的基本算法； 队列链式存储结构下的基本算法； 实验内容： 第一题链式堆栈设计。要求 （1）用链式堆栈设计实现堆栈，堆栈的操作集合要求包括：初始化StackInitiate（S）,非空否StackNotEmpty(S)，入栈StackiPush(S,x),出栈StackPop（S,d）,取栈顶数据元素StackTop(S,d); （2）设计一个主函数对链式堆栈进行测试。测试方法为：依次把数据元素1，2，3，4，5入栈，然后出栈并在屏幕上显示出栈的数据元素； （3）定义数据元素的数据类型为如下形式的结构体， Typedef struct { char taskName[10]; int taskNo; }DataType; 首先设计一个包含5个数据元素的测试数据，然后设计一个主函数对链式堆栈进行测试，测试方法为：依次吧5个数据元素入栈，然后出栈并在屏幕上显示出栈的数据元素。 第二题对顺序循环队列，常规的设计方法是使用対尾指针和对头指针，对尾指针用于指示当前的対尾位置下标，对头指针用于指示当前的対头位置下标。现要求： （1）设计一个使用对头指针和计数器的顺序循环队列抽象数据类型，其中操作包括：初始化，入队列，出队列，取对头元素和判断队列是否为空； （2）编写主函数进行测试。 程序代码： 第一题： （1）源程序"LinStack.h"如下： #define NULL 0 typedef struct snode { DataType data; struct snode *next; } LSNode; /*（1）初始化StackInitiate(LSNode ** head) */ void StackInitiate(LSNode ** head) /*初始化带头结点链式堆栈*/ 第三章栈和队列试题 一、单项选择题 1.栈的插入和删除操作在（）进行。 A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置 2.当利用大小为n的数组顺序存储一个栈时，假定用top==n表示栈空，则向这个栈插入一个元素时， 首先应执行（）语句修改top指针。 A. top++; B. top--; C. top = 0; D. top; 3.若让元素1,2,3依次进栈，则出栈次序不可能出现（）种情况。 A. 3, 2, 1 B. 2, 1, 3 C. 3, 1, 2 D. 1, 3, 2 4.在一个顺序存储的循环队列中，队头指针指向队头元素的（）位置。 A. 前一个 B. 后一个 C. 当前 D. 后面 5.当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（）。 A. n-2 B. n-1 C. n D. n+1 6.从一个顺序存储的循环队列中删除一个元素时，需要（）。 A. 队头指针加一 B. 队头指针减一 C. 取出队头指针所指的元素 D. 取出队尾指针所指的元素 7.假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear，则判断队空的条件为（）。 A. front+1 == rear B. rear+1 == front C. front == 0 D. front == rear 8.假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为（）。 A. front == rear B. front != NULL C. rear != NULL D. front == NULL 9.设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想在链式栈的栈顶插入一 个由指针s所指的结点，则应执行操作（）。 A. top->link = s; B.s->link = top->link; top->link = s; C. s->link = top; top = s; D. s->link = top; top = top->link; 10.设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想摘除链式栈的栈顶结点， 并将被摘除结点的值保存到x中，则应执行操作（）。 A. x = top->data; top = top->link; B. top = top->link; x = top->data; C. x = top; top = top->link; D. x = top->data; 11.设循环队列的结构是 #define MaxSize 100 typedef int ElemType; 数据结构练习第三章栈和队列 一、选择题 1．栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2．向顺序栈中压入新元素时，应当（）。 A．先移动栈顶指针，再存入元素 B．先存入元素，再移动栈顶指针C．先后次序无关紧要 D．同时进行 3．允许对队列进行的操作有( )。 A. 对队列中的元素排序 B. 取出最近进队的元素 C. 在队头元素之前插入元素 D. 删除队头元素 4．用链接方式存储的队列，在进行插入运算时( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 5．设用链表作为栈的存储结构则退栈操作（）。 A. 必须判别栈是否为满 B. 必须判别栈是否为空 C. 判别栈元素的类型 D.对栈不作任何判别 6．设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为（）。 A.front->next=s；front=s； B. s->next=rear；rear=s； C. rear->next=s；rear=s； D. s->next=front；front=s； 7．设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（）。 A.top=top+1; B. top=top-1; C. top->next=top; D. top=top->next; 8．队列是一种（）的线性表。 A. 先进先出 B. 先进后出 C. 只能插入 D. 只能删除 9．设输入序列1、2、3、…、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是（）。 A. n-i B. n-1-i C. n+l -i D.不能确定 10．设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为（）。 A. 5，3，4，6，1，2 B. 3，2，5，6，4，1 C. 3，1，2，5，4，6 D. 1，5，4，6，2，3 11．队列的删除操作是在（）进行。 A．队首 B．队尾 C．队前 D．队后 12．当利用大小为N 的数组顺序存储一个栈时，假定用top = = N表示栈空，则退栈时，用（）语句修改top指针。 A．top++; B．top=0; C．top--; D．top=N; 13．队列的插入操作是在（）进行。 ?、实验目的 1. 了解队列的特性。 2. 掌握队列的顺序表示和实现。 3. 掌握队列的链式表示和实现。 1、实验内容 实验3. 3队列的顺序表示和实现 编写一个程序实现顺序队列的各种基本运算（采用循环队列）， 主程序，完成如下功能： ⑴ 初始化队列。 ⑵ 建立顺序队列。 ⑶ 入队。 ⑷ 岀队。 (5) 判断队列是否为空。 ⑹ 取队头元素。 (7) 遍历队列。 实验3.4队列的链式表示和实现 编写一个程序实现链队列的各种基本运算，并在此基础上设计 能： (1) 初始化并建立链队列 ⑵ 入链队列。 ⑶ 岀链队列。 ⑷ 遍历链队列。 #i nclude int Ini tQueue(SqQueue &Q) { Q.base=(i nt*)malloc(MAXQSIZE*sizeof(i nt)); if(!Q.base)exit(O); Q.fro nt=Q.rear=0; return 0; }//初始化顺序队列 int QueueLe ngth(SqQueue Q) { int i; i=(Q.rear-Q.fro nt+MAXQSIZE)%MAXQSIZE; printf(“队列长度％5d\n",i); if(i)printf(" 队列非空“)； else printf(" 队列为空"); return 0; }//判断队列是否为空 int En Queue(SqQueue &Q,i nt e) { if((Q.rea 叶1)%MAXQSIZE==Q.fro nt)return 0; Q.base[Q.rear]=e; Q.rear=(Q.rea r+1)%MAXQSIZE; return 0; }//将元素e入队 int DeQueue(SqQueue & Q,i nt e) { if(Q.fro nt==Q.rear)return 0; e=Q.base[Q.fro nt]; prin tf("%5d\n",e); Q.fron t=(Q.fr on t+1)%MAXQSIZE; return 0; }// 删除元素e并返回其值 南京信息工程大学实验（实习）报告 实验（实习）名称栈和队列日期2017.11.8 得分指导老师崔萌萌 系计算机系专业软件工程年级2016 班次(1) 姓名学号 一、实验目的 1、学习栈的顺序存储和实现，会进行栈的基本操作 2、掌握递归 3、学习队列的顺序存储、链式存储，会进行队列的基本操作 4、掌握循环队列的表示和基本操作 二、实验内容 1、用栈解决以下问题： （1）对于输入的任意一个非负十进制数，显示输出与其等值的八进制数，写出程序。（2）表达式求值，写出程序。 2、用递归写出以下程序： （1）求n！。 （2）汉诺塔程序，并截图显示3、4、5个盘子的移动步骤,写出移动6个盘子的移动次数。 3、编程实现：（1）创建队列，将asdfghjkl依次入队。（2）将队列asdfghjkl依次出队。 4、编程实现创建一个最多6个元素的循环队列、将ABCDEF依次入队，判断循环队列是否队满。 三、实验步骤 1.栈的使用 1.1 用栈实现进制的转换： 代码如下： #include printf("转换为%d进制： ",radix); while(n) { s.push(n%radix); n /= radix; } while(!s.empty()) { //非空 printf("%d",s.top()); s.pop(); } printf("\n"); return 0; } 运行结果如下： 2.2 求表达式的值 代码如下： #include 《数据结构》课程实验报告 一、实验目的和要求 （1）熟悉C语言的上机环境，进一步掌握C语言的结构特点。 （2）掌握队列的顺序表示和实现。 二、实验环境 Windows7 ,VC 三、实验内容及实施 实验三：队列 【实验要求】 构建一个循环队列, 实现下列操作 1、初始化队列(清空)； 2、入队； 3、出队; 4、求队列长度； 5、判断队列是否为空； 【源程序】 #include Q.base=new int[MAXSIZE]; Q.front=Q.rear=0; return OK; }//队列的初始化 int EnQueue(SqQueue &Q,int e) { if((Q.rear+1)%MAXSIZE==Q.front) return ERROR; Q.base[Q.rear]=e; Q.rear=(Q.rear+1)%MAXSIZE; return OK; }//队列的入队 int DeQueue(SqQueue &Q,int &e) { if(Q.front==Q.rear) return ERROR; e=Q.base[Q.front]; Q.front=(Q.front+1)%MAXSIZE; return OK; }//队列的出队 int QueueLength(SqQueue &Q) { int i; i=(Q.rear-Q.front+MAXSIZE)%MAXSIZE; return i; }//求队列长度 void JuQueue(SqQueue &Q) { if(Q.rear==Q.front) printf("队列为空"); else printf("队列不为空"); }//判断队列是否为空 void QueueTraverse(SqQueue &Q) 习题三栈和队列 一单项选择题 1. 在作进栈运算时,应先判别栈是否(① ),在作退栈运算时应先判别栈是否(② )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为(③ )。 ①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2 2．若已知一个栈的进栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，...，pn，若p1＝3，则p2为( )。 A 可能是2 B 一定是2 C 可能是1 D 一定是1 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.设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4, s6, s5,s1,则栈的容量至少应该是（） A.2 B. 3 C. 5 D.6 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. 执行完下列语句段后，i值为：（） int f(int x) { return ((x>0) ? x* f(x-1):2);} int i ; i =f(f(1)); A．2 B. 4 C. 8 D. 无限递归 7. 表达式3* 2^(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为（），其中^为乘幂。 A. 3,2,4,1,1；(*^(+*- B. 3,2,8；(*^- C. 3,2,4,2,2；(*^(- D. 3,2,8；(*^(- 8. 用链接方式存储的队列，在进行删除运算时（）。 A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改 9. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（）的数据结构。 A．队列 B．多维数组 C．栈 D. 线性表 10．设C语言数组Data[m+1]作为循环队列SQ的存储空间， front为队头指针，rear为队尾指针，则执行出队操作的语句为（） A.front=front+1 B. front=（front+1）% m C.rear=(rear+1)%(m+1) D. front=(front+1)%(m+1) 11.循环队列的队满条件为 ( ) A. (sq.rear+1) % maxsize ==(sq.front+1) % maxsize; B. (sq.front+1) % maxsize ==sq.rear C. (sq.rear+1) % maxsize ==sq.front D.sq.rear ==sq.front 实验4 病人看病模拟程序 【问题描述】 编写一个程序，反映病人到医院看病，排队看医生的情况。在病人排队的过程中，主要重复两件事： （1）病人到达诊室，将病历本交给护士，排到等待队列中候诊。（2）护士从等待队列中取出下一位病人的病历，该病人进入诊室就诊。 要求模拟病人等待就诊这一过程。程序采用菜单方式，其选项及功能说明如下： （1）排队――输入排队病人的病历号，加入病人排队队列中。（2）就诊――病人排队队列中最前面的病人就诊，并将其从队列中删除； （3）查看排队――从对首到队尾列出所有的排队病人的病历号；（4）不再排队，余下一次就诊――从对首到队尾列出所有的排队病人的病历号，并退出运行； （5）下班――退出运行； #include typedef struct { QNode *front,*rear; }QuType; //链队类型 void seedoctor() //模拟病人看病的过程 { int sel,flag=1,find,no; QuType *qu; QNode *p; qu=(QuType *)malloc(sizeof(QuType)); //创建空队 qu->front=qu->rear=NULL; while(flag==1) { printf("1:排队 2：就诊 3：查看排队 4：不再排队，余下依次就诊 5：下班请选择："); scanf("%d",&sel); switch(sel) { case 1: printf(">>输入病历号："); do { scanf("%d",&no); find=0; 实验二栈和队列 一、实验目的 1. 掌握栈的顺序表示和实现 2. 掌握队列的链式表示和实现 二、实验内容 1. 编写一个程序实现顺序栈的各种基本运算。 2. 实现队列的链式表示和实现。 三、实验步骤 1. 初始化顺序栈 2. 插入元素 3. 删除栈顶元素 4. 取栈顶元素 5. 遍历顺序栈 6. 置空顺序栈 7. 初始化并建立链队列 8. 入链队列 9. 出链队列 10. 遍历链队列 四、实现提示 1. /*定义顺序栈的存储结构*/ typedef struct { ElemType stack[MAXNUM]; int top; }SqStack; /*初始化顺序栈函数*/ void InitStack(SqStack *p) {q=(SqStack*)malloc(sizeof(SqStack) /*申请空间*/) /*入栈函数*/ void Push(SqStack *p,ElemType x) {if(p->top 注意事项： 在磁盘上创建一个目录，专门用于存储数据结构实验的程序。因为机房机器有还原卡，请同学们将文件夹建立在最后一个盘中，以学号为文件夹名。 实验四队列的表示与操作 一、实验目的 1。掌握队列的掌握队列的类型定义,掌握循环队列的表示与实现方法 2．掌握队列的基本操作：判空、元素入队、出队，删除队头元素 基本操作： InitQueue()构造一个空队列Q QueueEmpty(Q) 判断队列是否为空 QueueLenght(Q)返回队列Q的元素个数，即队列的长度 GetHead(Q,&e)取队列Q的队头元素，并用e返回 InQueue(&Q,e) 将元素e入队列 OutQueue(&Q,&e)删除非空队列Q的队头元素，并用e返回其值 二、实验要求 1．认真阅读和掌握本实验的算法。 2．上机将本算法实现。 3．将程序补完整，打印出程序的运行结果，并结合程序进行分析。 三、实验内容 程序：设计一个循环队列的顺序表示和实现的演示程序 参考程序如下： #include 《数据结构》课程实验报告 实验名称栈和队列实验序号实验日期 姓名院系班级学号 专业指导教师成绩 教师评语 一、实验目的和要求 (1)理解栈和队列的特征以及它们之间的差异，知道在何时使用那种数据结构。 (2)重点掌握在顺序栈上和链栈上实现栈的基本运算算法，注意栈满和栈空的条件。 (3)重点掌握在顺序队上和链队上实现队列的基本运算算法，注意循环队队列满和队空的条件。 (4)灵活运用栈和队列这两种数据结构解决一些综合应用问题。 二、实验项目摘要 编写一个程序algo3-1.cpp，实现顺序栈的各种基本运算，并在此基础上设计一个主程序并完成如下功能：（1）初始化栈s； （2）判断栈s是否非空； （3）依次进栈元素a,b,c,d,e； （4）判断栈s是否非空； （5）输出栈长度； （6）输出从栈顶到栈底元素； （7）输出出栈序列； （8）判断栈s是否非空； （9）释放栈。 编写一个程序algo3-3.cpp，实现顺序环形队列的各种基本运算，并在此基础上设计一个主程序并完成如下功能： （1）初始化队列q； （2）判断队列q是否非空； （3）依次进队列a,b,c； （4）出队一个元素，输出该元素； （5）输出队列q的元素个数； （6）依次进队列元素d,e,f； （7）输出队列q的元素个数； （8）输出出队序列； （9）释放队列。 三、实验预习内容 栈的顺序存储结构及其基本运算实现（初始化栈，销毁栈，求栈的长度，判断栈是否为空，进栈，取栈顶元素，显示栈中元素） 队列的顺序存储结构及其基本运算实现（初始化队列，销毁队列，判断队列是否为空，入队列，出队列） 三、实验结果与分析 3-1 #define maxsize 100 #include 栈和队列 1 简述栈和线性表的区别。 2 简述栈和队列这两种数据结构的相同点和不同点。 3 如果进栈的元素序列为A，B，C，D，则可能得到的出栈序列有多少种？写出全部的可能序列。 4 如果进栈的元素序列为1，2，3，4，5，6，能否得到4，3，5，6，1，2和1，3，5，4，2，6的出栈序列？并说明为什么不能得到或如何得到。 5 写出下列程序段的运行结果（栈中的元素类型是char）： main( ) { SEQSTACK s,*p; char x, y; p = &s; initstack(p); x = ′c′; y = ′k′; push(p,x); push(p,′a′); push(p,y); x = pop(p); push(p,′t′); push(p,x); x = pop(p); push(p,′s′); while(!empty(p)) { y = pop(p); printf(″%c″,y);} printf(″%c＼n″,x); } 6 将一个非负十进制整数转换成二进制数，用非递归算法和递归算法来实现。 7 写一算法将一顺序栈中的元素依次取出，并打印元素值。 8 设单链表中存放着n个字符，试编一算法，判断该字符串是否有中心对称关系，例如xyzzyx，xyzyx都算是中心对称的字符串。 9 写出下列程序段的运行结果（队列中的元素类型是char）： main( ) { SEQQUEUE a, *q; char x, y; q = &a; x=′e′; y=′c′; initqueue(q); enqueue(q,′h′); enqueue(q,′r′); enqueue(q,y); x = dequeue(q); 《数据结构》实验指导及报告书 2014 / 2015 学年第 1学期 姓名： 学号： 班级： 指导教师：徐江 计算机科学与工程学院 2014 实验二栈和队列 一、实验目的 1、掌握栈的结构特性及其入栈，出栈操作； 2、掌握队列的结构特性及其入队、出队的操作，掌握循环队列的特点及其操作。 二、实验内容和要求 1、阅读下面程序，将函数Push和函数Pop补充完整。要求输入元素序列1 2 3 4 5 e，运行结果如下所示。 #include 数据结构实验报告 实验名称：实验2——栈和队列 学生姓名： 班级： 班内序号： 学号： 日期： 一、实验要求 1、实验目的：进一步掌握指针、模板类、异常处理的使用 掌握栈的操作的实现方法 掌握队列的操作的实现方法 学习使用栈解决实际问题的能力 学习使用队列解决实际问题的能力 2、实验内容： 根据栈和队列的抽象数据类型的定义，按要求实现一个栈或一个队列。要求： 实现一个共享栈 实现一个链栈 实现一个循环队列 实现一个链队列 编写测试main()函数测试线性表的正确性 二、程序分析 2.1 存储结构 顺序栈、链栈和顺序队列 顺序栈链栈顺序队列 2.2 关键算法分析 A、实现一个共享栈： a、伪代码实现 入栈操作：如果栈满，则抛出上溢异常； 判断是插在栈1还是栈2，如果在栈1插入，则栈顶指针top1加1，在top1处 填入x，如果在栈2插入，则栈顶指针top2加1，在top2处填入x。 出栈操作：如果栈空，则抛出下溢异常； 判断是栈1出栈还是栈2，如果是栈1，则输出栈1栈顶元素，并且top1减1， 如果是栈2，则输出栈2栈顶元素，并且top2加1。 得到栈顶元素操作：如果栈空，则抛出下溢异常； 判断是栈1出栈还是栈2，如果是栈1，则输出栈1栈顶元素，如果是栈2，则 输出栈2栈顶元素。 b、算法实现： void shareseqstack::push(int x,int pushnumber)//进栈操作 {if(top1+1==top2)//异常处理 throw "上溢"; if(pushnumber==1)//判断栈1还是栈2 data[++top1]=x; if(pushnumber==2) data[--top2]=x; } void shareseqstack::pop(int popnumber)//出栈操作 {if(popnumber==1) //异常处理 { if(top1==-1) throw "下溢";完整版数据结构习题集第3章栈和队列
数据结构-实验队列的实现
数据结构_实验三_栈和队列及其应用
数据结构：栈和队列学习资料
数据结构堆栈与队列实验报告
数据结构第三章栈和队列3习题
数据结构练习 第三章 栈和队列
数据结构实验——队列(附程序)
数据结构栈和队列实验报告.doc
数据结构-队列实验报告
数据结构栈和队列习题及答案
数据结构实验4队列
数据结构栈和队列
数据结构实验4 队列的表示与操作
数据结构栈和队列实验报告
《数据结构练习题》栈和队列
《数据结构》实验二 栈和队列
数据结构实验二题目一栈和队列实验报告
- 数据结构栈和队列实验报告
- 数据结构课程实验实训报告--堆栈和队列的基本操作。
- 数据结构实验-栈和队列
- 数据结构堆栈与队列实验报告
- 数据结构实验三栈和队列及其应用
- 数据结构_实验三_栈和队列及其应用
- 《数据结构》栈和队列实验报告
- 2数据结构实验报告二(栈和队列及其应用)
- 数据结构栈和队列实验报告
- 栈和队列实验报告
- 数据结构栈和队列实验报告
- 数据结构(栈及队列)实验报告 C语言版
- 栈和队列的基本操作及其应用数据结构实验报告书
- 数据结构_实验三_栈和队列及其应用
- 数据结构课程设计实验报告-栈和队列的用
- 数据结构栈和队列C语言实现
- 数据结构栈与队列的实验报告
- 数据结构试验栈和队列
- 数据结构栈和队列实验报告
- 数据结构栈和队列实验报告.doc