数据结构之队列

时间:2020-12-29 17:37:44

概述

在java5中新增加了java.util.Queue接口,用以支持队列的常见操作。Queue接口与List、Set同一级别,都是继承了Collection接口。
Queue使用时要尽量避免Collection的add()和remove()方法,而是要使用offer()来加入元素,使用poll()来获取并移出元素。它们的优
点是通过返回值可以判断成功与否,add()和remove()方法在失败的时候会抛出异常。 如果要使用前端而不移出该元素,使用
element()或者peek()方法。

代码实现

值得注意的是LinkedList类实现了Queue接口,因此我们可以把LinkedList当成Queue来用。

我们知道,在数组中,若知道数据项的下标,便可立即访问该数据项,或者通过顺序搜索数据项,访问到数组中的各个数据项。但是栈和队列不同,它们的访问是受限制的,即在特定时刻只有一个数据项可以被读取或者被删除。众所周知,栈是先进后出,只能访问栈顶的数据,队列是先进先出,只能访问头部数据。这里不再赘述。

    栈的主要机制可以用数组来实现,也可以用链表来实现,下面用数组来实现栈的基本操作:

[java] view plain copy 数据结构之队列数据结构之队列
  1. public class ArrayStack {  
  2.     private long[] a;  
  3.     private int size; //栈数组的大小  
  4.     private int top; //栈顶  
  5.   
  6.     public ArrayStack(int maxSize) {  
  7.         this.size = maxSize;  
  8.         this.a = new long[size];  
  9.         this.top = -1//表示空栈  
  10.     }  
  11.       
  12.     public void push(long value) {//入栈  
  13.         if(isFull()) {  
  14.             System.out.println("栈已满!");  
  15.             return;  
  16.         }  
  17.         a[++top] = value;  
  18.     }  
  19.       
  20.     public long peek() {//返回栈顶内容,但不删除  
  21.         if(isEmpty()) {  
  22.             System.out.println("栈中没有数据");  
  23.             return 0;  
  24.         }  
  25.         return a[top];  
  26.     }  
  27.       
  28.     public long pop() { //弹出栈顶内容,删除  
  29.         if(isEmpty()) {  
  30.             System.out.println("栈中没有数据!");  
  31.             return 0;  
  32.         }  
  33.         return a[top--];          
  34.     }  
  35.       
  36.     public int size() {  
  37.         return top + 1;  
  38.     }  
  39.       
  40.     public boolean isEmpty() {  
  41.         return (top == -1);  
  42.     }  
  43.       
  44.     public boolean isFull() {  
  45.         return (top == size -1);  
  46.     }  
  47.       
  48.     public void display() {  
  49.         for(int i = top; i >= 0; i--) {  
  50.             System.out.print(a[i] + " ");  
  51.         }  
  52.         System.out.println("");  
  53.     }  
  54. }  

    数据项入栈和出栈的时间复杂度均为O(1)。这也就是说,栈操作所消耗的时间不依赖于栈中数据项的个数,因此操作时间很短。栈不需要比较和移动操作。

    队列也可以用数组来实现,不过这里有个问题,当数组下标满了后就不能再添加了,但是数组前面由于已经删除队列头的数据了,导致空。所以队列我们可以用循环数组来实现,见下面的代码:

[java] view plain copy 数据结构之队列数据结构之队列
  1. public class RoundQueue {  
  2.     private long[] a;  
  3.     private int size;   //数组大小  
  4.     private int nItems; //实际存储数量  
  5.     private int front;  //头  
  6.     private int rear;   //尾  
  7.   
  8.     public RoundQueue(int maxSize) {  
  9.         this.size = maxSize;  
  10.         a = new long[size];  
  11.         front = 0;  
  12.         rear = -1;  
  13.         nItems = 0;  
  14.     }  
  15.       
  16.     public void insert(long value) {  
  17.         if(isFull()){  
  18.             System.out.println("队列已满");  
  19.             return;  
  20.         }  
  21.         rear = ++rear % size;  
  22.         a[rear] = value; //尾指针满了就循环到0处,这句相当于下面注释内容        
  23.         nItems++;  
  24. /*      if(rear == size-1){ 
  25.             rear = -1; 
  26.         } 
  27.         a[++rear] = value; 
  28. */  
  29.     }  
  30.       
  31.     public long remove() {  
  32.         if(isEmpty()) {  
  33.             System.out.println("队列为空!");  
  34.             return 0;  
  35.         }  
  36.         nItems--;  
  37.         front = front % size;  
  38.         return a[front++];  
  39.     }  
  40.       
  41.     public void display() {  
  42.         if(isEmpty()) {  
  43.             System.out.println("队列为空!");  
  44.             return;  
  45.         }  
  46.         int item = front;  
  47.         for(int i = 0; i < nItems; i++) {  
  48.             System.out.print(a[item++ % size] + " ");  
  49.         }  
  50.         System.out.println("");  
  51.     }  
  52.       
  53.     public long peek() {  
  54.         if(isEmpty()) {  
  55.             System.out.println("队列为空!");  
  56.             return 0;  
  57.         }  
  58.         return a[front];  
  59.     }  
  60.       
  61.     public boolean isFull() {  
  62.         return (nItems == size);  
  63.     }  
  64.       
  65.     public boolean isEmpty() {  
  66.         return (nItems == 0);  
  67.     }  
  68.       
  69.     public int size() {  
  70.         return nItems;  
  71.     }  
  72. }  

    和栈一样,队列中插入数据项和删除数据项的时间复杂度均为O(1)。

    还有个优先级队列,优先级队列是比栈和队列更专用的数据结构。优先级队列与上面普通的队列相比,主要区别在于队列中的元素是有序的,关键字最小(或者最大)的数据项总在队头。数据项插入的时候会按照顺序插入到合适的位置以确保队列的顺序。优先级队列的内部实现可以用数组或者一种特别的树——堆来实现。堆可参考第8节内容。这里用数组实现优先级队列。

[java] view plain copy 数据结构之队列数据结构之队列
  1. public class PriorityQueue {  
  2.     private long[] a;  
  3.     private int size;  
  4.     private int nItems;//元素个数  
  5.       
  6.     public PriorityQueue(int maxSize) {  
  7.         size = maxSize;  
  8.         nItems = 0;  
  9.         a = new long[size];  
  10.     }  
  11.       
  12.     public void insert(long value) {  
  13.         if(isFull()){  
  14.             System.out.println("队列已满!");  
  15.             return;  
  16.         }  
  17.         int j;  
  18.         if(nItems == 0) { //空队列直接添加  
  19.             a[nItems++] = value;  
  20.         }  
  21.         else{//将数组中的数字依照下标按照从大到小排列  
  22.             for(j = nItems-1; j >= 0; j--) {  
  23.                 if(value > a[j]){  
  24.                     a[j+1] = a[j];  
  25.                 }  
  26.                 else {  
  27.                     break;  
  28.                 }  
  29.             }  
  30.             a[j+1] = value;  
  31.             nItems++;  
  32.         }  
  33.     }  
  34.       
  35.     public long remove() {  
  36.         if(isEmpty()){  
  37.             System.out.println("队列为空!");  
  38.             return 0;  
  39.         }  
  40.         return a[--nItems];  
  41.     }  
  42.       
  43.     public long peekMin() {  
  44.         return a[nItems-1];  
  45.     }  
  46.       
  47.     public boolean isFull() {  
  48.         return (nItems == size);  
  49.     }  
  50.       
  51.     public boolean isEmpty() {  
  52.         return (nItems == 0);  
  53.     }  
  54.       
  55.     public int size() {  
  56.         return nItems;  
  57.     }  
  58.   
  59.     public void display() {  
  60.         for(int i = nItems-1; i >= 0; i--) {  
  61.             System.out.print(a[i] + " ");  
  62.         }  
  63.         System.out.println(" ");  
  64.     }  
  65. }