数据结构003-栈和队列

1、1 1 栈栈1.11.21.31.4、 栈的应用栈的应用 2 队列队列2.3、2.4、2.5、2.6、2 通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性表。 栈和队列是两种操作受限的线性表，是两种常用的数据类型。 线性表线性表 栈栈 队列队列 Insert(i, x) Insert(n, x) Insert(n, x) 0in Delete(i) Delete(n-1) Delete(0) 0in-13线性表线性表可以对输入序列求逆可以对输入序列求逆出栈出栈Pop入栈入栈Pushtopbottoma0an-2an-14【思考题思考题】：设有编号为1，2，3，4的四辆列车，顺序进一

2、个栈式结构的站台，具体写出这四辆列车开出车站的所有可能的顺序。1. 1、2、3、4； 2. 1、2、4、3；3. 1、3、2、4； 4. 1、3、4、2；5. 1、4、3、2；6. 2、1、3、4；7. 2、1、4、3； 8. 2、3、4、1；9. 2、3、1、4 ； 10. 2、4、3、1；11. 3、2、1、4； 12. 3、2、4、1；13. 3、4、2、1； 14. 4、3、2、1。 5ADT Stack Data: . Operator: 栈初始化 入栈Pushpush( T x ); 出栈Poppop( ); 判断栈是否空IsEmptyIsEmpty( ); 读取栈顶元素peekp

3、eek ( ); 置空栈clearclear( ); 判断栈是否满IsFullIsFull( );6/栈接口，描述栈抽象数据类型栈接口，描述栈抽象数据类型public interface IStackpublic void clear();public boolean isEmpty();public int length();public Object peek();public void push(Object x) throws Exception;public Object pop();实现此接口的方法有两种实现此接口的方法有两种: 顺序栈顺序栈链栈链栈7DATA：object sta

4、ckElem ; /栈元素数组栈元素数组int top; /栈顶栈顶 (int curLen)int maxSize; /栈最大容量栈最大容量 (int stackElem.length)topstackElem0 1 2 3 4 5 6 7 8 9 maxSize-1bottom入栈入栈：stackElemtop+= x出栈：出栈：return stackElem-top 栈空：栈空：top= 0 栈满：栈满：top=maxSize入栈？入栈？ 出栈？出栈？栈空？栈空？栈满？栈满？栈的长度？栈的长度？栈顶元素？栈顶元素？8public class SqStack implements ISt

5、ack private Object stackElem; / 栈栈存储空间存储空间 private int top; / 非空栈中始终表示栈顶元素的下一个位置，当栈为空时其值为非空栈中始终表示栈顶元素的下一个位置，当栈为空时其值为0 public SqStack(int maxSize) / 构造一个存储空间容量为maxSize的栈 top = 0; / 初始化top为0 stackElem = new ObjectmaxSize;/ 为栈分配为栈分配maxSize个存储单元个存储单元 public void clear() top = 0; / 将一个已经存在的栈置成空 public bo

6、olean isEmpty() return top = 0; / 测试栈是否为空 public int length() return top; / 求栈中的数据元素个数并由函数返回其值 public Object peek() / 查看栈顶对象而不移除它，返回栈顶对象 if (!isEmpty() return stackElemtop - 1; / 若栈不空，返回栈若栈不空，返回栈顶元素顶元素 else return null; / 若栈为空，返回 null 9/ 移除栈顶对象并作为此函数的值返回该对象 public Object pop() if (top = 0) return nu

7、ll;/ 栈为栈为空，返回空，返回null else return stackElem-top; / 栈非空栈非空, 修改栈顶指针，并返回栈顶元素修改栈顶指针，并返回栈顶元素 / 把项压入栈顶 public void push(Object o) throws Exception if (top = stackElem.length) throw new Exception(“栈栈已已满满”); /栈满，输出栈满，输出异常异常 else stackElemtop+ = o; / 栈未满，o赋给栈顶元素后，top增110/栈顶指针相遇栈顶指针相遇/栈顶指针退到栈底栈顶指针退到栈底b0 t0 t1

8、 b10 maxSize-1Vtopbottombottomtop11n不设头结点不设头结点；n第一个结点即为栈顶。第一个结点即为栈顶。n链式栈无栈满问题，空间可扩充；链式栈无栈满问题，空间可扩充；n插入插入（入栈）（入栈）与删除与删除（出栈）只能（出栈）只能在栈顶处执行；在栈顶处执行；n链式栈的栈顶在链头；链式栈的栈顶在链头；top栈底元素栈底元素当 top = NULL 时，表示空栈栈顶元素栈顶元素datanext12链式栈的入栈和出栈链式栈的入栈和出栈public class LinkStack implements IStack private Node top; 13public c

9、lass LinkStack implements IStack private Node top; / 栈顶元素的引用栈顶元素的引用 public void clear() top = null; / 将一个已经存在的栈置成空 public boolean isEmpty() return top = null; / 测试栈是否为空 public int length() / 求栈中的数据元素个数并由函数返回其值 Node p = top; / 初始化,p指向栈顶结点,length为计数器 int length = 0; while (p != null) p = p.getNext();

10、+length; return length; public Object peek() / 查看栈顶对象而不移除它，返回栈顶对象 if (!isEmpty() return top.getData();/ 返回栈顶元素返回栈顶元素 else return null; 。14public Object pop() / 移除栈顶对象并作为此函数的值返回该对象 if (!isEmpty() Node p = top;/ p指向栈顶结点 top = top.getNext(); return p.getData(); else return null;public void push(Object

11、x) / 把项压入栈顶 Node p = new Node(x); / 构造一个新的结点构造一个新的结点 p.setNext(top); top = p;/ 改变栈顶结点。15 栈是嵌套调用机制的实现基础 使用栈以非递归方式实现递归算法 16 【例例】将一个十进制数转换为二进制数将一个十进制数转换为二进制数如：18 18/2=9 + 0 9/2=4 + 1 4/2=2 + 0 2/2=1 + 0 18 10010 100000 ？001017【例例】：判断表达式中圆括号是否匹配：判断表达式中圆括号是否匹配18例例2：使用栈计算表达式的值：使用栈计算表达式的值中缀表达式1+2*(3-4)+519

12、（1）将中缀表达式转换为后缀表达式）将中缀表达式转换为后缀表达式1. 设立一个运算符栈运算符栈；2. 若若当前字符是操作数，则直接发送给后缀式当前字符是操作数，则直接发送给后缀式;3. 若若当前字符为当前字符为运算符运算符时，若运算符栈为空或运算符栈非空且时，若运算符栈为空或运算符栈非空且该运算符优先级该运算符优先级高于高于栈顶运算符，则栈顶运算符，则进栈；进栈；否则，否则，退出栈顶退出栈顶运算符发送给后缀式；运算符发送给后缀式；4. 若当前字符是左括号“（”时，将其压进运算符栈;5. 若当前字符是右括号“）”时，反复将栈顶符号弹出反复将栈顶符号弹出，并送往后缀表达式，直到栈顶符号是左括号为止

13、，再将左括号出栈并丢弃。6. 若读取完毕，则将栈中剩余的所有运算符弹出并送往后缀表达式。2021（2）后缀表达式求值）后缀表达式求值 1) 设立一个操作数栈； 2) 从左到右依次读入后缀表达式中的字符:若当前字符是操作数，则压入操作数栈。若当前字符是运算符，则从栈顶弹出两个操作数参与运算，并将运算结果压入操作数栈内。2223 1 栈栈1.11.21.31.4、 栈的应用栈的应用 2 队列队列2.3、2.4、2.5、2.6、24定义：删除操作只能在一端（队首）进行，而插入操作只能定义：删除操作只能在一端（队首）进行，而插入操作只能在另一端（队尾）进行的线性表。在另一端（队尾）进行的线性表。概念：

14、队首（概念：队首（frontfront）、队尾（）、队尾（rearrear）、出列、入列）、出列、入列特点：按先进先出（特点：按先进先出（FIFOFIFO）的原则进行操作。）的原则进行操作。a0a1 an-2an-1与栈类似，队列的封闭性非常好与栈类似，队列的封闭性非常好栈能对输入序列部分或全局起求逆作用，而队列对输栈能对输入序列部分或全局起求逆作用，而队列对输入序列起缓冲作用，队列的应用非常广泛入序列起缓冲作用，队列的应用非常广泛出列出列入列入列队首（队首（front）队队尾尾 rear。25public interface IQueue /队列队列java接口描述接口描述 public v

15、oid clear(); /队列直空队列直空public boolean isEmpty(); /队列判空队列判空public int length(); /求队列长度求队列长度public Object peek();/取队首元素取队首元素public void offer(Object x) throws Exception;/入列（入队）入列（入队）public Object poll(); /出列（出队）出列（出队） 。实现此接口的方法有两种实现此接口的方法有两种: 顺序队列顺序队列链式队列链式队列26front=rear空队列front rearA A入列入列Afront rearB

16、入列入列A Bfront rearC, D入列入列A B C Dfront rearA出列出列B C Dfront rearB出列出列C Dfront rearE,F,G入列入列C D E F GC D E F Gfront rearH入列入列,溢出溢出。queueElem队首元素？队尾元素？队空条件？队满条件？入队操作？出队操作？27 队首元素？queueElemfront 队尾元素？queueElemrear-1 队空条件？ front=rear 队满条件？ rear=queueElem.length 入队操作？ queueElemrear+=x; 出队操作？ return queueEl

17、em front+;282901234567frontrear空队列空队列队列初始化：队列初始化：front = rear = 0;队空条件：队空条件：front = rear;队满条件：队满条件：(rear+1) % maxSize = frontmaxSize8。front = rear; 区分队空或队满？区分队空或队满？ 三种方法：少用一个元素空间、标志变量、计数变量（参见教材）三种方法：少用一个元素空间、标志变量、计数变量（参见教材）3001234567frontrearA入列入列队列初始化：队列初始化：front = rear = 0;队空条件：队空条件：front = rear;队

18、满条件：队满条件：(rear+1) % maxSize = frontAmaxSize8rear3101234567frontrearB B、C C入列入列队列初始化：队列初始化：front = rear = 0;队空条件：队空条件：front = rear;队满条件：队满条件：(rear+1) % maxSize = frontABmaxSize8Crearrear3201234567frontrearA A、B B出列出列队列初始化：队列初始化：front = rear = 0;队空条件：队空条件：front = rear;队满条件：队满条件：(rear+1) % maxSize = fr

19、ontABmaxSize8Cfrontfront3301234567rearD、E、F、G、H、I 入列入列队列初始化：队列初始化：front = rear = 0;队空条件：队空条件：front = rear;队满条件：队满条件：(rear+1) % maxSize = frontmaxSize8CfrontDEFG HIrear34front=(front+1) % length;rear=(rear+1) % length;35循环队列的类定义循环队列的类定义public class CircleSqQueue implements IQueue private Object queue

20、Elem; / 队列存储空间队列存储空间 private int front;/ 队头的引用，若队列不空，指向队列头元素队头的引用，若队列不空，指向队列头元素 private int rear;/ 队尾的引用，若队列不空，指向队列尾元素的下一个位置队尾的引用，若队列不空，指向队列尾元素的下一个位置 public CircleSqQueue(int maxSize) / 循环队列类的构造函数 front = rear = 0;/ 队头、队尾初始化为0 queueElem = new ObjectmaxSize; /为队列分配为队列分配maxSize个存储单元个存储单元 public void c

21、lear() front = rear = 0; / 将队列置空 public boolean isEmpty() return front = rear; / 队列判空 public int length() / 求队列中的数据元素个数并由函数返回其值 return (rear - front + queueElem.length) % queueElem.length; public Object peek() / 查看队列头但不移除它，队列空则返回 null if (front = rear) return null; / 队列为空，返回队列为空，返回null else return q

22、ueueElemfront; / 返回队列头返回队列头元素元素 36/ 把指定的元素插入队列public void offer(Object o) throws Exception if (rear + 1) % queueElem.length = front) / 队列满队列满 throw new Exception(队列已满队列已满);/ 输出异常输出异常 else / 队列未满队列未满 queueElemrear = o; / rear加1后，o赋给栈顶元素 rear = (rear + 1) % queueElem.length; / 修改队尾指针 / 移除队列的头并作为此函数的值返

23、回该对象，如果此队列为空，则返回 nullpublic Object poll() if (front = rear) return null; / 队列为空队列为空 else Object t = queueElemfront;/ 取出队列头元素 front = (front + 1) % queueElem.length;/ 更改队头位置 return t;/ 返回队列头元素返回队列头元素 。37n链式队列与单链表相似，但链式队列与单链表相似，但不设头结点不设头结点；n第一个结点即为队首，最后一个结点为队尾。第一个结点即为队首，最后一个结点为队尾。n插入（入列）操作只能在队尾进行，删除（出

24、列）操作只插入（入列）操作只能在队尾进行，删除（出列）操作只能在队首进行。能在队首进行。front当 front = NULL 时，表示空队列reardatanext队首元素队首元素队尾元素队尾元素。38public class LinkQueue implements IQueue /链式队列类链式队列类 private Node front, rear; 39public class LinkQueue implements IQueue private Node front;/ 队头的引用队头的引用 private Node rear;/ 队尾的引用，指向队尾元素队尾的引用，指向队尾元素

25、 public LinkQueue() front = rear = null; / 链队列类的构造函数 public void clear() front = rear = null; / 队列置空 public boolean isEmpty() return front = null; / 队列判空 public int length() / 求队列中的数据元素个数并由函数返回其值 Node p = front; int length = 0;/ 队列的长度队列的长度 while (p != null) p = p.getNext(); +length; return length; public Object peek() / 返回队列顶对象，队列为空，则返回 null if (front != null) return front.getData();/ 返回队列元素返回队列元素 e