队列的数组实现和链式实现

1，队列ADT

package Queue;

public interface QueueADT {

public void enqueue(Object element); // 入队

public Object dequeue(); // 出队

public Object first(); // 返回队首元素

public boolean isEmpty();

public int size();

public String toString();

}

2，队列的链式实现

维护一个指向队首的front结点，一个指向队尾的rear结点，和一个标识队列大小的count变量：

 
   private 
    LinearNode front,rear; 
   // 
   指示队首和队尾 
   
 
   
 
   private 
     
   int 
    count; 
  

构造函数：

 
   public 
    LinkedQueue()
 {
 front  
   = 
     
   null 
   ;
 rear  
   = 
     
   null 
   ;
 count  
   = 
     
   0 
   ;
 } 
  

链式实现：

package Queue;

import Bag.LinearNode;

public class LinkedQueue implements QueueADT {

private LinearNode front,rear;
private int count;


public static void main(String[] args) {

LinkedQueue queue = new LinkedQueue();

System.out.println( " 依次将0到9入队，然后连续出队5次 " );
for ( int i = 0 ;i < 10 ;i ++ )
queue.enqueue(i);
for ( int i = 0 ;i < 5 ;i ++ )
queue.dequeue();
System.out.println( " 队列的大小为： " + queue.size());
System.out.println( " 队列为空吗？： " + queue.isEmpty());
System.out.println( " 队列的头为： " + queue.first());

}


public LinkedQueue()
{
front = null ;
rear = null ;
count = 0 ;
}

public int size() {
return count;
}

public boolean isEmpty() {
return (size() == 0 );
}

public void enqueue(Object element) {
LinearNode node = new LinearNode(element);
if (isEmpty())
front = rear = node;
else
{
rear.setNext(node);
rear = node;
}
count ++ ;
}

public Object dequeue() {
if (isEmpty())
{
System.out.println( " 队列中没有元素 " );
System.exit( 1 );
}

Object result = front.getElement();
front = front.getNext();
count -- ;
return result;
}

public Object first() {
return front.getElement();
}

}

结果：

依次将0到9入队，然后连续出队5次
队列的大小为： 5
队列为空吗？： false
队列的头为： 5

3，数组实现

将队列的一端固定在数组的索引0处，（注意由于队首要求固定，所以出队操作就要挨个移动元素）。维护一个整型变量count标识下一个open单元（也表示队列的当前大小）

 
   private 
    Object[] contents; 
   // 
   将队首固定在数组的0位置 
   
 
   private 
     
   int 
    rear; 
   // 
   指向下一个入队的位置，且表示队列的长度 
   
 
   private 
     
   static 
     
   int 
    SIZE  
   = 
     
   10 
   ;  
  

构造方法和数组扩展的方法：

 
   public 
    ArrayQueue()
 {
 contents  
   = 
     
   new 
    Object[SIZE];
 rear  
   = 
     
   0 
   ;
 }

 
   public 
     
   void 
    expand()
 {
 Object[] larger  
   = 
     
   new 
    Object[size() 
   * 
   2 
   ];
 
   for 
   ( 
   int 
    index  
   = 
     
   0 
   ;index  
   < 
    rear;index 
   ++ 
   )
 larger[index]  
   = 
    contents[index];

 contents  
   = 
    larger;
 } 
  

数组实现：

package Queue;

public class ArrayQueue implements QueueADT {

private Object[] contents; // 将队首固定在数组的0位置
private int rear; // 指向下一个入队的位置，且表示队列的长度
private static int SIZE = 10 ;


public static void main(String[] args) {

ArrayQueue queue = new ArrayQueue();

System.out.println( " 依次将0到24入队，然后连续出队10次 " );
for ( int i = 0 ;i < 25 ;i ++ )
queue.enqueue(i);
for ( int i = 0 ;i < 10 ;i ++ )
queue.dequeue();

System.out.println( " 队列的大小为： " + queue.size());
System.out.println( " 队列为空吗？： " + queue.isEmpty());
System.out.println( " 队列的第一个元素为： " + queue.first());
}



public ArrayQueue()
{
contents = new Object[SIZE];
rear = 0 ;
}

public void expand()
{
Object[] larger = new Object[size() * 2 ];
for ( int index = 0 ;index < rear;index ++ )
larger[index] = contents[index];

contents = larger;
}


public int size() {
return rear;
}

public boolean isEmpty() {
return (size() == 0 );
}

public void enqueue(Object element) {
if (rear == contents.length)
expand();
contents[rear] = element;
rear ++ ;
}

public Object dequeue(){
if (isEmpty())
{
System.out.println( " 队列为空 " );
System.exit( 1 );
}

Object result = contents[ 0 ];

for ( int index = 0 ;index < rear;index ++ )
contents[index] = contents[index + 1 ];
rear -- ;

return result;
}


public Object first() {
return contents[ 0 ];
}

}

结果：

依次将0到24入队，然后连续出队10次
队列的大小为： 15
队列为空吗？： false
队列的第一个元素为： 10



4，使用循环数组来实现队列

上面提到过，将队首固定在一端，在出队的时候会依次将剩下的元素往前移动一步，对于容量较大的队列，是一个很大的开销。使用循环队列可以消除元素移动带来的效率问题，用一个front和rear整型变量作为指针来滑动标记队首和队尾元素，当遇到数组末尾时，首尾相连到数组头.。再用一个count来记录队列的大小，

 
   private 
    Object[] contents;
 
   private 
     
   int 
    front,rear; 
   // 
   front为队头下标，rear为队尾的下一个元素的下标 
   
 
     
   private 
     
   int 
    count; 
   // 
   标记队列元素个数 
   
 
     
   private 
     
   static 
     
   int 
    SIZE  
   = 
     
   10 
   ; 
  

这里没有实现循环队列空间不够的时候扩展容量的方法，因为使用循环队列就是为了消除元素移动，扩展容量的话又要移动元素，就只考虑了在已知容量够用的情况下使用循环队列解决问题。

另外，为了简化问题，每次当队列清空以后，再次入队的时候，我们就把front和rear恢复到初试状态，从0开始入队，这一点在代码注释里交代过。

队列的循环数组实现：

package Queue;

public class CircularArrayQueue {

private Object[] contents;
private int front,rear; // front为队头下标，rear为队尾的下一个元素的下标
private int count; // 标记队列元素个数
private static int SIZE = 10 ;



public static void main(String[] args) {

CircularArrayQueue circlequeue = new CircularArrayQueue();

System.out.println( " 将0到7依次入队，然后连续4次出队 " );

for ( int i = 0 ;i < 8 ;i ++ )
circlequeue.enqueue(i);
for ( int i = 0 ;i < 4 ;i ++ )
circlequeue.dequeue();
System.out.println( " 队首元素为： " + circlequeue.first());
System.out.println( " 队首元素下标为： " + circlequeue.front);
System.out.println( " 队尾元素下标为： " + circlequeue.rear);
System.out.println( " 队列大小为： " + circlequeue.count + " n " );

System.out.println( " 再向队列中加入从8到11 " );
for ( int i = 8 ;i < 12 ;i ++ )
circlequeue.enqueue(i);
System.out.println( " 队首元素为： " + circlequeue.first());
System.out.println( " 队首元素下标为： " + circlequeue.front);
System.out.println( " 队尾元素下标为： " + circlequeue.rear);
System.out.println( " 队列大小为： " + circlequeue.count);
}


public CircularArrayQueue()
{
contents = new Object[SIZE];
front = - 1 ;
rear = 0 ;
count = 0 ;
}

public int size(){
return count;
}

public boolean isEmpty(){
return (size() == 0 );
}

public void enqueue(Object element){

if (size() == 0 ) // 默认如果数组中没有元素，则从0开始进队，这样简化问题的考虑
{
contents[ 0 ] = element;
front = 0 ;
rear = 1 ;
// rear++ 错误，经过一些进队出队操作后rear可能在别的位置了
count ++ ;
}
else
{
contents[rear] = element;
rear = (rear + 1 ) % contents.length;
// rear = (rear + 1) % size(); 错误
count ++ ;
}
}

public Object dequeue(){
if (isEmpty())
{
System.out.println( " 队列为空！！！ " );
System.exit( 1 );
}

Object result = contents[front];

contents[front] = null ; // 可要可不要，下次覆盖也可
front = (front + 1 ) % contents.length;
// front = (front + 1) % size(); 错误
count -- ;

return result;
}

public Object first(){
return contents[front];
}

}

结果：（注意下标的变化，因为不移动元素，实际上是用下标在移动指向）

将0到7依次入队，然后连续4次出队
队首元素为： 4
队首元素下标为： 4
队尾元素下标为： 8
队列大小为： 4

再向队列中加入从8到11
队首元素为： 4
队首元素下标为： 4
队尾元素下标为： 2
队列大小为： 8