你的位置:首页 > Java教程

[Java教程]数据结构Java实现07


一、队列的概念:

  队列(简称作队,Queue)也是一种特殊的线性表,队列的数据元素以及数据元素间的逻辑关系和线性表完全相同,其差别是线性表允许在任意位置插入和删除,而队列只允许在其一端进行插入操作在其另一端进行删除操作

队列中允许进行插入操作的一端称为队尾,允许进行删除操作的一端称为队头。队列的插入操作通常称作入队列,队列的删除操作通常称作出队列

下图是一个依次向队列中插入数据元素a0,a1,...,an-1后的示意图:

faf7d1e6-07b1-44bb-9752-5fcc113a0648

上图中,a0是当前 队头数据元素,an-1是当前 队尾数据元素。

为了避免当只有一个元素时,对头和队尾重合使得处理变得麻烦,所以引入两个指针:front指针指向队头元素,rear指针指向队尾元素的下一个位置,这样的话,当front指针等于rear时,此队列不是还剩一个元素,而是空队列。

 

二、队列的抽象数据类型:

数据集合:

  队列的数据集合可以表示为a0,a1,…,an-1,每个数据元素的数据类型可以是任意的类型。

操作集合:

(1)入队列append(obj):把数据元素obj插入队尾。

(2)出队列delete():把队头数据元素删除并由函数返回。

(3)取队头数据元素getFront():取队头数据元素并由函数返回。

(4)非空否isEmpty():非空否。若队列非空,则函数返回false,否则函数返回true。

 

三、循环顺序队列:

线性表有顺序存储和链式存储,队列是一种特殊的线性表,同样也存在这两种存储方式。我们先来看一下队列的顺序存储。

1、顺序队列的“假溢出”:

607ede1a-91b5-4ac9-8850-07078379fddb

上图中,front指针指向队头元素,rear指针指向队尾元素的下一个位置。图(d)中b、c、d出队后,front指针指向元素e,rear指针在数组外面。假设这个队列的总个数不超过5个,但目前如果接着入队的话,因数组末尾元素已经被占用,再向后加就会产生数组越界的错误,可实际上队列在下标为0、1、2、3、4的地方还是空闲的,我们把这种现象叫做“假溢出”。

2、循环顺序队列:

    所以解决假溢出的办法就是后面满了,就再从头开始,也就是头尾相接的循环。我们把队列的这种逻辑上首尾相连的顺序存储结构称为循环队列

如何判断循环队列究竟是空的还是满的:

  现在问题又来了,我们之前说,空队列时,front指针等于rear指针,那么现在循环队列满的时候,也是front等于rear,那么如何判断循环队列究竟是空的还是满的?有如下办法:

  • 办法1:设置一个标志位flag。初始时置flag=0;每当入队列操作成功就置flag=1;每当出队列操作成功就置flag=0。则队列空的判断条件为:rear == front && tag==0;队列满的判断条件为:rear = = front && tag= =1。
  • 办法2:保留一个元素的存储空间。此时,队列满时的判断条件为  (rear + 1) % maxSize == front;队列空的判断条件还是front == rear。
  • 办法3:设计一个计数器count,统计队列中的元素个数。此时,队列满的判断条件为:count > 0 && rear == front ;队列空的判断条件为count == 0。

我们在接下来的代码中采用方法3来实现。

 

3、代码实现:(循环顺序队列的创建)

(1)Queue.java:(队列接口)

 1 //队列接口 2 public interface Queue { 3  4   //入队 5   public void append(Object obj) throws Exception; 6  7   //出队 8   public Object delete() throws Exception; 9 10   //获得队头元素11   public Object getFront() throws Exception;12 13   //判断对列是否为空14   public boolean isEmpty();15 }

(2)CircleSequenceQueue.java:(循环顺序队列)

 1 //循环顺序队列 2 public class CircleSequenceQueue implements Queue { 3  4   static final int defaultSize = 10; //默认队列的长度 5   int front; //队头 6   int rear;  //队尾 7   int count; //统计元素个数的计数器 8   int maxSize; //队的最大长度 9   Object[] queue; //队列10 11   public CircleSequenceQueue() {12     init(defaultSize);13   }14 15   public CircleSequenceQueue(int size) {16     init(size);17   }18 19   public void init(int size) {20     maxSize = size;21     front = rear = 0;22     count = 0;23     queue = new Object[size];24   }25 26   @Override27   public void append(Object obj) throws Exception {28     // TODO Auto-generated method stub29     if (count > 0 && front == rear) {30       throw new Exception("队列已满!");31     }32     queue[rear] = obj;33     rear = (rear + 1) % maxSize;34     count++;35   }36 37   @Override38   public Object delete() throws Exception {39     // TODO Auto-generated method stub40     if (isEmpty()) {41       throw new Exception("队列为空!");42     }43     Object obj = queue[front];44     front = (front + 1) % maxSize;45     count--;46     return obj;47   }48 49   @Override50   public Object getFront() throws Exception {51     // TODO Auto-generated method stub52     if (!isEmpty()) {53       return queue[front];54     } else {55       return null;56     }57   }58 59   @Override60   public boolean isEmpty() {61     // TODO Auto-generated method stub62     return count == 0;63   }64 65 }

(3)Test.java:

 1 public class Test { 2   public static void main(String[] args) throws Exception { 3  4     CircleSequenceQueue queue = new CircleSequenceQueue(); 5     queue.append("a"); 6     queue.append("b"); 7     queue.append("c"); 8     queue.append("d"); 9     queue.append("e");10     queue.append("f");11 12     queue.delete();13     queue.delete();14 15     queue.append("g");16 17     while (!queue.isEmpty()) {18       System.out.println(queue.delete());19     }20   }21 }

运行效果:

251fa2d6-120f-4b20-8754-f7a795b20cf1 

 

4、循环队列应用:

  使用顺序循环队列和多线程实现一个排队买票的例子。而且,我们只允许这个队伍中同时排队的只有10个人,那就需要用到队列了。

    生产者(等候买票)

    消费者 (买票离开)

这里面我们需要用到上面的Queue.java类和CircleSequenceQueue.java类。

代码结构:

62c99e55-fe55-41d0-8794-7a74a37ca826

(3)WindowQueue.java:

 1 //卖票窗口 2 public class WindowQueue { 3  4   //卖票的队列 5   int maxSize = 10; 6   CircleSequenceQueue queue = new CircleSequenceQueue(maxSize); 7   int num = 0; //统计卖票的数量,一天最多卖100张票。 8   boolean isAlive = true; //判断是否继续卖票。 9 10   //排队买票11   public synchronized void producer() throws Exception {12     if (queue.count < maxSize) {13       queue.append(num++); //等待买票的数量加114       System.out.println("第" + num + "个客户排队等待买票!");15       this.notifyAll();//唤醒卖票的线程16     } else {17       try {18         System.out.println("队列已满...请等待!");19         this.wait();//队列满时,排队买票线程等待。20       } catch (Exception ex) {21         ex.printStackTrace();22       }23     }24   }25 26   //卖票27   public synchronized void consumer() throws Exception {28     if (queue.count > 0) {29       Object obj = queue.delete();30       int temp = Integer.parseInt(obj.toString());31       System.out.println("第" + (temp + 1) + "个客户买到票离开队列!");32       //如果当前队列为空,并且卖出票的数量大于等于100,说明卖票结束33       if (queue.isEmpty() && this.num >= 100) {34         this.isAlive = false;35       }36       this.notifyAll(); //唤醒排队买票的线程。37     } else {38       try {39         System.out.println("队列已空...请等待!");40         this.wait();//队列空时,卖票线程等待。41       } catch (Exception ex) {42         ex.printStackTrace();43       }44     }45   }46 }

(4)Producer.java:

 1 //买票者 2 public class Producer implements Runnable { 3  4   WindowQueue queue; 5  6   public Producer(WindowQueue queue) { 7     this.queue = queue; 8   } 9 10   @Override11   public void run() {12     // TODO Auto-generated method stub13     while (queue.num < 100) {14       try {15         queue.producer();16       } catch (Exception ex) {17         ex.printStackTrace();18       }19     }20   }21 22 }

(5)Consumer.java:

//卖票者public class Consumer implements Runnable {  WindowQueue queue;  public Consumer(WindowQueue queue) {    this.queue = queue;  }  @Override  public void run() {    // TODO Auto-generated method stub    while (queue.isAlive) {      try {        queue.consumer();      } catch (Exception ex) {        ex.printStackTrace();      }    }  }}

 (6)test.java:

 1 public class Test { 2  3   public static void main(String[] args) throws Exception { 4  5     WindowQueue queue = new WindowQueue(); 6  7     Producer p = new Producer(queue);//注意一定要传同一个窗口对象 8     Consumer c = new Consumer(queue); 9 10     //排队买票线程11     Thread pThread = new Thread(p);12     //卖票线程13     Thread cThread = new Thread(c);14 15     pThread.start(); //开始排队买票16     cThread.start(); //开始卖票17   }18 19 }

注意第07行的注释。

运行效果:

bb9b709e-bc10-48ab-89e6-260ca38ae5d2

  

四、链式队列:

    链式队列其实就是特殊的单链表,只不过它只能尾进头出而已。链式队列的存储结构如下图所示:

6c1486eb-a189-413f-bce1-a8f516aede26

1、链式队列的实现:

(1)Node.java:结点类

 1 //结点类 2 public class Node { 3  4   Object element; //数据域 5   Node next; //指针域 6  7   //头结点的构造方法 8   public Node(Node nextval) { 9     this.next = nextval;10   }11 12   //非头结点的构造方法13   public Node(Object obj, Node nextval) {14     this.element = obj;15     this.next = nextval;16   }17 18   //获得当前结点的后继结点19   public Node getNext() {20     return this.next;21   }22 23   //获得当前的数据域的值24   public Object getElement() {25     return this.element;26   }27 28   //设置当前结点的指针域29   public void setNext(Node nextval) {30     this.next = nextval;31   }32 33   //设置当前结点的数据域34   public void setElement(Object obj) {35     this.element = obj;36   }37 38   public String toString() {39     return this.element.toString();40   }41 }

(2)Queue.java:

 1 //队列接口 2 public interface Queue { 3  4   //入队 5   public void append(Object obj) throws Exception; 6  7   //出队 8   public Object delete() throws Exception; 9 10   //获得队头元素11   public Object getFront() throws Exception;12 13   //判断对列是否为空14   public boolean isEmpty();15 }

(3)LinkQueue.java:

 1 public class LinkQueue implements Queue { 2  3   Node front; //队头 4   Node rear; //队尾 5   int count; //计数器 6  7   public LinkQueue() { 8     init(); 9   }10 11   public void init() {12     front = rear = null;13     count = 0;14   }15 16   @Override17   public void append(Object obj) throws Exception {18     // TODO Auto-generated method stub19     Node node = new Node(obj, null);20 21     //如果当前队列不为空。22     if (rear != null) {23       rear.next = node; //队尾结点指向新结点24     }25 26     rear = node; //设置队尾结点为新结点27 28     //说明要插入的结点是队列的第一个结点29     if (front == null) {30       front = node;31     }32     count++;33   }34 35   @Override36   public Object delete() throws Exception {37     // TODO Auto-generated method stub38     if (isEmpty()) {39       new Exception("队列已空!");40     }41     Node node = front;42     front = front.next;43     count--;44     return node.getElement();45   }46 47   @Override48   public Object getFront() throws Exception {49     // TODO Auto-generated method stub50     if (!isEmpty()) {51       return front.getElement();52     } else {53       return null;54     }55   }56 57   @Override58   public boolean isEmpty() {59     // TODO Auto-generated method stub60     return count == 0;61   }62 63 }

(4)Test.java:

 1 public class Test { 2  3   public static void main(String[] args) throws Exception { 4  5     LinkQueue queue = new LinkQueue(); 6     queue.append("a"); 7     queue.append("b"); 8     queue.append("c"); 9     queue.append("d");10     queue.append("e");11     queue.append("f");12 13     queue.delete();14     queue.delete();15 16     queue.append("g");17 18     while (!queue.isEmpty()) {19       System.out.println(queue.delete());20     }21   }22 }

运行效果:

7ee743ea-3e2a-4795-b7b3-10dfef4f3e9b 

 

2、链式队列的应用:

题目:

  编写一个判断一个字符串是否是回文的算法。

思路:

  设字符数组str中存放了要判断的字符串。把字符数组中的字符逐个分别存入一个队列和栈中,然后逐个出队和出栈比较出队的字符与出栈的字符是否相同,若全部相等则该字符串为回文。

代码实现:

  这里面需要用到上面一段中的LinkQueue类。代码结构如下:

3a04b30d-6ed1-4556-a408-afc8b4c6068a

(4)Stack.java:栈接口

 1 //栈接口 2 public interface Stack { 3  4   //入栈 5   public void push(Object obj) throws Exception; 6  7   //出栈 8   public Object pop() throws Exception; 9 10   //获得栈顶元素11   public Object getTop() throws Exception;12 13   //判断栈是否为空14   public boolean isEmpty();15 }

(5)LinkStack.java:

 1 public class LinkStack implements Stack { 2  3   Node head; //栈顶指针 4   int size; //结点的个数 5  6   public LinkStack() { 7     head = null; 8     size = 0; 9   }10 11   @Override12   public Object getTop() throws Exception {13     // TODO Auto-generated method stub14     return head.getElement();15   }16 17   @Override18   public boolean isEmpty() {19     // TODO Auto-generated method stub20     return head == null;21   }22 23   @Override24   public Object pop() throws Exception {25     // TODO Auto-generated method stub26     if (isEmpty()) {27       throw new Exception("栈为空!");28     }29     Object obj = head.getElement();30     head = head.getNext();31     size--;32     return obj;33 34   }35 36   @Override37   public void push(Object obj) throws Exception {38     // TODO Auto-generated method stub39     head = new Node(obj, head);40     size++;41   }42 43 }

(6)Test.java:测试类

 1 public class Test { 2  3   public static void main(String[] args) throws Exception { 4  5     String str1 = "ABCDCBA"; //是回文 6     String str2 = "ABCDECAB"; //不是回文 7  8     try { 9       if (Test.isHuiWen(str1)) {10         System.out.println(str2 + ":是回文!");11       } else {12         System.out.println(str2 + ":不是回文!");13       }14     } catch (Exception ex) {15       ex.printStackTrace();16     }17   }18 19 20   //方法:判断字符串是否回文21   public static boolean isHuiWen(String str) throws Exception {22     int n = str.length();23     LinkStack stack = new LinkStack();//创建堆栈24     LinkQueue queue = new LinkQueue();//创建队列25     for (int i = 0; i < n; i++) {26       stack.push(str.subSequence(i, i + 1)); //把字符串每个字符压进堆栈27       queue.append(str.subSequence(i, i + 1));//把字符串每个字符压入队列28     }29     while (!queue.isEmpty() && !stack.isEmpty()) {30       if (!queue.delete().equals(stack.pop())) { //出队列,出栈,同时判断是否相同31         return false;32       }33     }34 35     return true;36   }37 38 }

  

3、循环队列和链式队列的比较:

(1)从时间上看,它们的基本操作都是常数时间,即O(1)的。不过循环队列是事先申请好空间,使用期间不释放;而链式队列,每次申请和释放结点也会存在一定的时间开销,如果入栈和出栈比较频繁,则两者还是有细微的差别。

(2)从空间上看,循环队列必须有一个固定的长度,所以就有了存储元素个数和空间浪费的问题。而链式队列不存在这个问题,尽管它需要一个指针域,会产生一些空间上的开销,但也可以接受。所以在空间上,链式队列更加灵活。

总结:总的来说,在可以确定队列长度的最大值的情况下,建议用循环队列,如果你无法估计队列的长度,那就用链式队列。

 

五、优先级队列:

  优先级队列是带有优先级的队列。

    用顺序存储结构实现的优先级队列称作顺序优先级队列

    用链式存储结构存储的优先级队列称作链式优先级队列

顺序优先级队列顺序循环队列相比主要有两点不同

(1)对于顺序优先级队列来说,出队列操作不是把队头数据元素出队列,而是把队列中优先级最高的数据元素出队列。(入队操作没区别)

(2)对于顺序优先级队列来说,数据元素由两部分组成,一部分是原先意义上的数据元素,另一部分是优先级。通常设计优先级为int类型的数值,并规定数值越小优先级越高

 

1、顺序优先队列的实现:

设计顺序优先级队列分为两个类:

  数据元素类

  优先级队列类

代码实现:

(1)Element.java:

 1 //优先级队列元素类 2 public class Element { 3  4   private Object element; // 数据 5   private int priority; // 优先级 6  7   public Element(Object obj, int priority) { 8     this.element = obj; 9     this.priority = priority;10   }11 12   public Object getElement() {13     return element;14   }15 16   public void setElement(Object element) {17     this.element = element;18   }19 20   public int getPriority() {21     return priority;22   }23 24   public void setPriority(int priority) {25     this.priority = priority;26   }27 28 }

 (2)Queue.java:

 1 //队列接口 2 public interface Queue { 3  4   //入队 5   public void append(Object obj) throws Exception; 6  7   //出队 8   public Object delete() throws Exception; 9 10   //获得队头元素11   public Object getFront() throws Exception;12 13   //判断对列是否为空14   public boolean isEmpty();15 }

(3)PrioritySequenceQueue.java:

 1 //优先级队列 2 public class PrioritySequenceQueue implements Queue { 3  4   static final int defaultSize = 10; //默认队列长度 5   int front; //队头 6   int rear; //队尾 7   int count; //计数器 8   int maxSize; //队列最大长度 9   Element[] queue; //队列10 11   public PrioritySequenceQueue() {12     init(defaultSize);13   }14 15   public PrioritySequenceQueue(int size) {16     init(size);17   }18 19   public void init(int size) {20     maxSize = size;21     front = rear = 0;22     count = 0;23     queue = new Element[size];24   }25 26   @Override27   public void append(Object obj) throws Exception {28     // TODO Auto-generated method stub29     //如果队列已满30     if (count >= maxSize) {31       throw new Exception("队列已满!");32     }33     queue[rear] = (Element) obj;34     rear++;35     count++;36   }37 38   @Override39   public Object delete() throws Exception {40     // TODO Auto-generated method stub41     if (isEmpty()) {42       throw new Exception("队列为空!");43     }44     //默认第一个元素为优先级最高的。45     Element min = queue[0];46     int minIndex = 0;47     for (int i = 0; i < count; i++) {48       if (queue[i].getPriority() < min.getPriority()) {49         min = queue[i];50         minIndex = i;51       }52     }53 54     //找的优先级别最高的元素后,把该元素后面的元素向前移动。55     for (int i = minIndex + 1; i < count; i++) {56       queue[i - 1] = queue[i]; //移动元素57     }58     rear--;59     count--;60     return min;61   }62 63   @Override64   public Object getFront() throws Exception {65     // TODO Auto-generated method stub66     if (isEmpty()) {67       throw new Exception("队列为空!");68     }69     //默认第一个元素为优先级最高的。70     Element min = queue[0];71     int minIndex = 0;72     for (int i = 0; i < count; i++) {73       if (queue[i].getPriority() < min.getPriority()) {74         min = queue[i];75         minIndex = i;76       }77     }78     return min;79   }80 81   @Override82   public boolean isEmpty() {83     // TODO Auto-generated method stub84     return count == 0;85   }86 87 }

2、代码测试:

  设计一个程序模仿操作系统的进程管理问题。进程服务按优先级高的先服务,优先级相同的先到先服务的原则管理。

  模仿数据包含两个部分:进程编号和优先级。如下有五个进程:

    1      30

    2      20

    3      40

    4      20

    5      0       ----------优先级最高,先服务

(4)Test.java:

 1 public class Test { 2  3   public static void main(String[] args) throws Exception { 4  5     PrioritySequenceQueue queue = new PrioritySequenceQueue(); 6     Element temp; 7  8     //五个进程入队 9     queue.append(new Element(1, 30));10     queue.append(new Element(2, 20));11     queue.append(new Element(3, 40));12     queue.append(new Element(4, 20));13     queue.append(new Element(5, 0));14 15     //按照优先级出队。16     System.out.println("编号 优先级");17     while (!queue.isEmpty()) {18       temp = (Element) queue.delete();19       System.out.println(temp.getElement() + " " + temp.getPriority());20     }21   }22 }

运行效果:

f22bc718-69dd-488e-a893-dd93109da4cf