文档介绍：第3章栈和队列
数据结构
赵龙文 ******@scut.
1
主要内容
1 栈
、栈的抽象数据类型及其基本操作
、栈的数组存储表示—顺序栈
、栈的链表存储表示—链式栈
、栈的应用
2 队列
、队列的抽象数据类型
、队列的数组存储表示- 顺序队列
、循环队列(Circular Queue)
、队列的链接存储表示—链式队列
、优先级队列(Priority Queue)
、队列的应用
2
栈和队列
通常称,栈和队列是限定插入和删除只能在表的“端点”进行的线性表。
栈和队列是两种操作受限的线性表,是两种常用的数据类型。
线性表栈队列
Insert(i, x) Insert(n, x) Insert(n, x)
0≤i≤n
Delete(i) Delete(n-1) Delete(0)
0≤i≤n-1
3
1、栈(Stack)
定义:
只允许在一端插入和删除的线性表。
概念:
栈顶(top);
栈底(bottom);
入栈(Push);
出栈(Pop);
特点:
后进先出(LIFO)
可以对输入序列求逆
出栈
Pop
入栈
Push
top
bottom
a0
an-2
an-1
4
【思考题】:
设有编号为1,2,3,4的四辆列车,顺序进一个栈式结构的站台,具体写出这四辆列车开出车站的所有可能的顺序。
1、2、3、4;
1、2、4、3;
1、3、2、4;
1、3、4、2;
1、4、3、2;
2、1、3、4;
2、1、4、3;
2、3、4、1;
2、3、1、4 ;
2、4、3、1;
3、2、1、4;
3、2、4、1;
3、4、2、1;
4、3、2、1。
5
、栈的抽象数据类型及其基本操作
ADT Stack {
Data: ......
Operator:
栈初始化
入栈Push push( T x );
出栈Pop pop( );
判断栈是否空IsEmpty IsEmpty( );
读取栈顶元素peek peek ( );
置空栈clear clear( );
判断栈是否满IsFull IsFull( );
}
6
栈的抽象数据类型(Java)
//栈接口,描述栈抽象数据类型
public interface IStack{
public void clear();
public boolean isEmpty();
public int length();
public Object peek();
public void push(Object x) throws Exception;
public Object pop();
}
实现此接口的方法有两种:
顺序栈
链栈
7
、栈的数组存储表示—顺序栈
DATA:
object stackElem[ ]; //栈元素数组
int top; //栈顶(int curLen)
int maxSize; //栈最大容量(int )
top
stackElem
0 1 2 3 4 5 6 7 8 9 maxSize-1
bottom
入栈:stackElem[top++]= x
出栈:return stackElem[--top]
栈空:top= 0
栈满:top=maxSize
入栈? 出栈?
栈空? 栈满? 栈的长度? 栈顶元素?
8
顺序栈的类定义
public class SqStack implements IStack {
private Object[] stackElem; // 栈存储空间
private int top; // 非空栈中始终表示栈顶元素的下一个位置,当栈为空时其值为0
public SqStack(int maxSize) { // 构造一个存储空间容量为maxSize的栈
top = 0; // 初始化top为0
stackElem = new Object[maxSize]; // 为栈分配maxSize个存储单元
}
public void clear() {top = 0; } // 将一个已经存在的栈置成空
public boolean isEmpty() { return top == 0; } // 测试栈是否为空
public int length() { return top; } // 求栈中的数据元素个数并由函数返回其值
public Object peek() { // 查看栈顶对象而不移除它,返回栈顶对象
if