文档介绍：2018年5月24日
数据结构讲义
1
栈和队列
2018年5月24日
数据结构讲义
2
重点:
;
栈的顺序存储结构及运算实现;
栈的链式存储结构及运算实现;
;
队列的顺序存储结构及运算实现;
队列的链式存储结构及运算实现。
;
循环队列的队空、队满判断条件;
循环队列上的插入、删除操作。
2018年5月24日
数据结构讲义
3
栈
2018年5月24日
数据结构讲义
4
栈的定义及基本运算
: 栈是限制在表的一端进行插入和删除的线性表。允许插入、删除的这一端称为栈顶,另一个固定端称为栈底。当表中没有元素时称为空栈。
右图所示栈中有三个元素,
进栈的顺序是a1、a2、a3,当
需要出栈时其顺序为a3、a2、
a1,所以栈又称为后进先出的
线性表(Last In First Out),
简称 LIFO表。
(此处可出小题)
2018年5月24日
数据结构讲义
5
练****br/>(1)一个栈的输入序列为123,则栈的输出序列不可能的是______。
A、123 B、213 C、321 D、312
(2)一个栈的输入序列为123,则栈的可能的输出序列有______种。
A、3 B、4 C、5 D、6
(3)一个栈的输入序列是abcd,则栈的输出序列abcd是__________(可能的/不可能的)。
2018年5月24日
数据结构讲义
6
:
⑴栈初始化:Init_Stack(s)
⑵判栈空:Empty_Stack(s)
操作结果是若s为空栈返回为1,否则返回为0。
⑶入栈: Push_Stack(s,x)
操作结果是在栈s的顶部插入一个新元素x,x成为新的栈顶元素。
⑷出栈:Pop_Stack(s)
在栈s存在且非空的情况下,操作结果是将栈s的顶部元素从栈中删除。
⑸读栈顶元素:Top_Stack(s)
在栈s存在且非空情况下,操作结果是读栈顶元素,栈不变化。
2018年5月24日
数据结构讲义
7
栈的存储实现和运算实现 顺序栈
:
栈中的数据元素用一个预设的足够长度的一维数组来实现:datatype data[MAXSIZE],栈底位置可以设置在数组的任一个端点,而栈顶是随着插入和删除而变化的,用一个int top 来作为栈顶的指针,指明当前栈顶的位置,将data和top封装在一个结构中,
顺序栈的类型描述如下:
#define MAXSIZE 1024
typedef struct
{datatype data[MAXSIZE];
int top;
}SeqStack;
定义一个指向顺序栈的指针: SeqStack *s;
2018年5月24日
数据结构讲义
8
:
通常0下标端设为栈底,这样空栈时栈顶指针top=-1; 入栈时,栈顶指针加1,即s->top++; 出栈时,栈顶指针减1,即s->top--。栈操作的示意图如下:
2018年5月24日
数据结构讲义
9
算法实现
:建立栈空间,然后初始化栈顶指针
2018年5月24日
数据结构讲义
10