(九) 优先级队列
一、什么是优先级队列？
它是一种带有优先级的队列，是一种比栈和队列更为专用的数据结构。
有一个队首和队尾。
在队首删除数据元素，顺序插入元素到队列的合适位置。
队列中的每一个数据元素按照关键字的值有序排列。
约定：关键字最小的数据元素（或者在某些实现中要求数据是最大的）具有最高优先级。
----------------------------------------------------------------------
二、优先级队列使用顺序和链两个存储结构那个更好呢？
可采用顺序和链式两种存储结构。
考虑到优先级队列，既要保证能够快速的访问到优先级高的数据，又要保证可以实现快速的插入操作。所以通常以链式存储结构来实现优先级队列。
数据级别的高低依据优先数来鉴定，优先数越小，优先级别就越大。
----------------------------------------------------------------------
三、优先级队列中结点的数据域data类【PriorityData】
package data.linear_table.node; //优先队列中结点类的data类：数据域的值 public class PriorityQData { public Object elem ; //结点的数据元素值 public int priority ; //结点的优先数 //构造函数 public PriorityQData (Object elem , int priority ) { this.elem = elem ; this.priority = priority ; } }
package data.linear_table.stack_queue; import data.linear_table.node.Node; import data.linear_table.node.PriorityQData; //优先队列【常以链式存储结构实现】 public class PriorityQueue implements IQueue { private Node front ; //队首的引用 private Node rear ; //队尾的引用 //优先队列类的构造函数 public PriorityQueue () { front = rear = null ; } //队列置空 @Override public void clear() { front = rear = null ; } //判断队列是否为空 @Override public boolean isEmpty() { return front == null; } //求队列长度 @Override public int length() { Node p = front ; int length = 0 ; while (p != null ){ //一直查到队尾 p = p.next ; length++ ; } return length ; } //读取首元素 @Override public Object peek() { if (front == null ){ return null; }else { return front.data ; //返回队首结点的数据域值 } } //入队 @Override public void offer(Object x) { // {...} } //出队 @Override public Object poll() { // {... } return null ; } //输出队列中的所有元素 public void display() { if (!isEmpty()) { Node p = front ; while (p != null ) { PriorityQData q = (PriorityQData) p.data; System.out.println(q.elem+" " + q.priority); p = p.next ; } //从队首到队尾 }else { System.out.println("此队列为空！"); } } }
算法：出队
//出队 @Override public Object poll() { if (front == null){ return null; }else { Node p = front ; //保存记录要被删除的队首元素 front = front.next ; //队首指向下一个元素 return p.data ; } }
算法：入队【数字越小，优先级越高】
情况1：队首插入（p如果指向队首front,表示新结点的优先级数字小）
情况2：队尾插入（q为null 或p 等于队尾rear）
情况3：在两个元素的中间插入
//入队 @Override public void offer(Object x) { PriorityQData pn = (PriorityQData) x ; Node s = new Node(pn) ; //构造一个新结点 //如果队列为空 if (front == null) { front = rear = s ; //修改队列首结点 }else { // 1) 移动：按照优先级进行移动，优先级大就需要移动 Node p = front ; //用于记录下一个 Node q = front ; //用于记录前驱（之前的） // 队首不为null ,并且新结点的优先级 >= 队列结点的优先级【两者进行比较】 while (p != null && pn.priority >= ((PriorityQData)p.data).priority ) { //满足， q = p ; //记录前驱 p = p.next ; //指向下一个 } // 2) 插入 // 2.1 情况一： 新结点的优先级比队尾还低 if (p == null ) { // p，遍历到下一个结点为空，表示遍历到了队列尾部 rear.next = s; //将新结点加入到队尾,队尾指针域next,指向新结点 rear = s ; //修改队尾指针 // 情况二 ： 新结点的优先级比队首还高 }else if (p == front ) { s.next = front ; //将新结点加入到队首，新结点s指向队首front front = s ; //修改队首指针 // 情况三 ： 新结点位于两个结点的中间 }else { //新结点加入到队列中部 q.next = s ; //q是s的前驱结点，则s是q的下一个结点 s.next = p ; // s的下一个结点是p,则s为于 q 和 p 之间 } } }
(十) 每日一练
41. 队列的插入操作在（ ）进行。
A．队头
B．队尾
C．队头或队尾
D．在任意指定位置
----------------------------------------------
42. 队列的删除操作在（ ）进行。
A．队头
B．队尾
C．队头或队尾
D．在任意指定位置
----------------------------------------------
43. 栈的插入操作在（ ）进行。
A．栈顶
B．栈底
C．栈顶或栈底
D．在任意指定位置
----------------------------------------------
44. 一个队列的入队序列是 2，4，6，8，则队列的输出序列是（ ）。
A．8，6，4，2
B．2，4，6，8
C．4，2，8，6
D．6，4，2，8
----------------------------------------------
45. 一个队列的入队序列是 5，6，7，8，则队列的输出序列是（ ）。
A. 5 6 7 8
B. 8 7 6 5
C. 7 8 6 5
D.可能有多种情况
----------------------------------------------
46. 一个栈的进栈序列是 1，2，3，4，则不可能的出栈序列是（ ）（进出栈操作可以交替进行）。
A．3，2，4，1
B．1，4，2，3 1 4 3 2
C．4，3，2，1
D．3，2，1，4
----------------------------------------------
47. 一个栈的进栈序列是 5，6，7，8，则栈的不可能的出栈序列是（ ）（进出栈操作可以交替进行）
A．5，8，6，7 5 8 7 6
B．7，6，8，5
C．7，6，5，8
D．8，7，6，5
----------------------------------------------
48. 一个栈的进栈序列是 a，b，c，d，e，则栈的不可能输出序列是（ ）（进栈出栈可以交替进行）。
A．dceab ain bin cin din dout cout ein eout bout aout --> dceba
B．edcba ain bin cin din ein eout dout cout bout aout --> edcba
C．decba ain bin cin din dout ein eout cout bout aout --> decba
D．abcde ain aout bin bout cin cout din dout ein eout --> abcde
----------------------------------------------
49. 以下说法不正确的是（ ）。
A．顺序栈中，栈满时再进行进栈操作称为“上溢”
B．顺序栈中，栈空时再作出栈栈操作称为“下溢”
C．顺序队列中，当尾指针已经超越队列存储空间的上界，则一定是队列已满。（假溢出）
D．顺序队列中，队列的头指针和尾指针均超越队列存储空间的上界，则队列已空
----------------------------------------------
50. 以下说法不正确的是（ ）。
A．栈的特点是后进先出
B．队列的特点是先进先出
C．栈的删除操作在栈底进行，插入操作在栈顶进行。 栈顶删除
D．队列的插入操作在队尾进行，删除操作在队头进行
----------------------------------------------
51. 以下说法正确的是（ ）。
A．栈的特点是先进先出，队列的特点是先进后出
B．栈和队列的特点都是先进后出
C．栈的特点是先进后出，队列的特点是先进先出
D．栈和队列的特点都是先进先出
----------------------------------------------
52. 以下说法正确的是（ ）。
A．栈的特点是先进先出，队列的特点是先进后出
B．栈和队列的特点都是先进后出
C．栈的特点是先进后出，队列的特点是先进先出
D．栈和队列的特点都是先进先出
----------------------------------------------
53. 元素 2，4，6，8 按顺序依次进栈，则该栈的不可能输出序列是（ ）（进栈出栈可以交替进行）。
A．8，6，4，2 2in 4in 6in 8in 8out 6out 4out 2out --> 8642
B．2，4，6，8 2in 2out 4in 4out 6in 6out 8in 8out --> 2468
C．4，2，8，6 2in 4in 4out 2out 6in 8in 8out 6out --> 4286
D．8，6，2，4 8642
----------------------------------------------
54. 元素 2，4，6 按顺序依次进栈，则该栈的不可能的输出序列是（ ）。
A. 6 4 2 2in 4in 6in 6out 4out 2out --> 642
B. 6 2 4 642
C. 4 2 6 2in 4in 4out 2out 6in 6out --> 426
D. 2 6 4 2in 2out 4in 6in 6out 4out --> 264
----------------------------------------------
55. 栈的插入删除操作在（ ）进行。
A．栈底
B．任意位置
C．指定位置
D．栈顶
----------------------------------------------
56. 栈和队列的相同点是（ ）。
A．都是后进先出
B．都是后进后出
C．逻辑结构与线性表不同
D．逻辑结构与线性表相同，都是操作规则受到限制的线性表
----------------------------------------------
57. 从一个栈顶指针为 top 的链栈中插入一个由 P 指向的新结点时，则执行的操作是（）。
A．p.setNext(top); top=p;
B．top=p; p.setNext(top);
C．top.setNext(p); p=top;
D．top.setNext(p); p=top;
-----------------------------------------------------------------------
58. 设 top 是一个链栈的栈顶指针，栈中每个结点由一个数据域 data 和指针域 next 组成，
设用 x 接收栈顶元素，则出栈操作为（ ）。
A．x=top.getData(); top=top.getNext();
B．top=top.getNext();x=top.getData();
C．x=top.getNext(); top=top.getData();
D．top.setNext(top); x=top.getData();
-----------------------------------------------------------------------
59. 在一个链队列中，假设 f 和 r 分别为队头和队尾指针，则插入 s 所指结点的运算为（ ）。
A．f．setNext(s); f=s;
B．r.setNext（s）; r=s;
C．s．setNext(r); r=s;
D．s.setNext(f); f=s;
-----------------------------------------------------------------------
60. 在一个链队列中，假设 f 和 r 分别为队头和队尾指针，则删除一个结点的运算为（ ）。
A．r=f.getNext();
B．r=r.getNext();
C．f=r.getNext();
D．f=f.getNext();
-----------------------------------------------------------------------
61. 在一个循环队列中，队列的空间大小为 length, 设对头指针为 front, 队尾指针为 rear,
按照教材采用减少一个存储元素的方法，以下那个能判断队列已满。 （ ）
A. (rear+1)%length==front;
B. rear==front;
C. rear%length==front ;
D. (rear-1)%length==front;
-----------------------------------------------------------------------
62. 若一个栈用数组 data[1..n]存储,初始栈顶指针 top 为 n, 则如元素 x 进栈的正确操作是：（ ）
A. top++; data[top]=x;
B. data[top]=x;top++;
C. top--;data[top]=x ;
D. data[top]=x;top--;
