第四章栈与队列2 （对列）

4.2 队列

4.2.1 队列的定义

队列简称队，它通栈一样，也是一种运算受限的线性表，其限制是仅允许在表的一端进行插入，而在表的另一端进行删除。在队列中把插入数据元素的一端称为队尾(rear)，删除元素的一端称为队首(front)。向队尾插入元素称为进队或入队。从队列中删除元素称为离队或出队。

队列是先进先出表（First In First Out,FIFO）。

队列的接口Queue：

 1 package com.datastructure.chapter04.interfaces;
 2 
 3 import com.datastructure.chapter04.Exception.QueueEmptyException;
 4 
 5 /** 
 6  * @ClassName: Queue 
 7  * @Description: 队列的接口
 8  * @author 
 9  * @date 2018年3月16日 下午10:09:17 
10  *  
11  */
12 public interface Queue {
13     
14      //返回队列打大小
15     public int getSize();
16     
17     //判断队列是否为空
18     public boolean isEmpty();
19     
20     //数据元素e入列
21     public void enqueue(Object e);
22     
23     //队首元素出队
24     public Object dequeue() throws QueueEmptyException;
25     
26     //取队首元素
27     public Object peek() throws QueueEmptyException;
28 }

View Code

队列为空的异常类：

1 package com.datastructure.chapter04.Exception;
2 
3 @SuppressWarnings("serial")
4 public class QueueEmptyException extends RuntimeException {
5     
6     public QueueEmptyException(String err) {
7         super(err);
8     }
9 }

View Code

4.2.2 队栈的顺序存储实现

  1 package com.datastructure.chapter04.interfaces;
  2 
  3 import javax.swing.tree.ExpandVetoException;
  4 
  5 import com.datastructure.chapter04.Exception.QueueEmptyException;
  6 
  7 public class QueueArray implements Queue {
  8 
  9     private static final int CAP = 7;//队列默认大小
 10     
 11     private Object[] elements;//数据元素数组
 12     
 13     private int capacity;//数组的大小elements.length
 14     
 15     private int front;//队首指针，指向队首
 16     
 17     private int rear;//队尾指针，指向队尾后一个位置
 18     
 19     public QueueArray() {
 20         this(CAP);
 21     }
 22     
 23     public QueueArray(int cap) {
 24         capacity = cap+1;
 25         elements = new Object[capacity];
 26         front = rear = 0;
 27     }
 28 
 29     /* (非 Javadoc) 
 30      * <p>Title: getSize</p> 
 31      * <p>Description: 获得队列的长度</p> 
 32      * @return 
 33      * @see com.datastructure.chapter04.interfaces.Queue#getSize() 
 34      */
 35     @Override
 36     public int getSize() {
 37         return (rear-front+capacity)%capacity;
 38     }
 39 
 40     /* (非 Javadoc) 
 41      * <p>Title: isEmpty</p> 
 42      * <p>Description: 判断队列是否为空</p> 
 43      * @return 
 44      * @see com.datastructure.chapter04.interfaces.Queue#isEmpty() 
 45      */
 46     @Override
 47     public boolean isEmpty() {
 48         return front == rear;
 49     }
 50 
 51     /* (非 Javadoc) 
 52      * <p>Title: enqueue</p> 
 53      * <p>Description: 队列的入队</p> 
 54      * @param e 
 55      * @see com.datastructure.chapter04.interfaces.Queue#enqueue(java.lang.Object) 
 56      */
 57     @Override
 58     public void enqueue(Object e) {
 59         if(getSize()==capacity-1) expandSpace();
 60         elements[rear] = e;
 61         rear = (rear+1)%capacity;
 62         
 63     }
 64 
 65     /** 
 66      * @Title: expandSpace 
 67      * @Description:  队列扩容
 68      * @param   
 69      * @return void   
 70      * @throws 
 71      */
 72     private void expandSpace() {
 73         Object[] a =new Object[elements.length*2];
 74         int i = front; int j=0;
 75         
 76         while(i!=rear){
 77             a[j++] = elements[i];
 78             i = (i+1)%capacity;
 79         }
 80         elements = a;
 81         
 82         capacity = elements.length;
 83         front = 0;
 84         rear = j;//设置新的队首，队尾指针
 85     }
 86 
 87     /* (非 Javadoc) 
 88      * <p>Title: dequeue</p> 
 89      * <p>Description: 队列的出队</p> 
 90      * @return
 91      * @throws QueueEmptyException 
 92      * @see com.datastructure.chapter04.interfaces.Queue#dequeue() 
 93      */
 94     @Override
 95     public Object dequeue() throws QueueEmptyException {
 96         if(isEmpty())
 97             throw new QueueEmptyException("错误，队列为空");
 98         Object obj = elements[front];
 99         front = (front+1)%capacity;
100         return obj;
101     }
102 
103     /* (非 Javadoc) 
104      * <p>Title: peek</p> 
105      * <p>Description: 获得队首元素</p> 
106      * @return
107      * @throws QueueEmptyException 
108      * @see com.datastructure.chapter04.interfaces.Queue#peek() 
109      */
110     @Override
111     public Object peek() throws QueueEmptyException {
112         if(isEmpty())
113             throw new QueueEmptyException("错误，队列为空");
114         return elements[front];
115     }
116 
117 }

View Code

以上有个循环数组的概念：就是将数组头和尾通过两个指针（front队首和rear队尾）来指向这两个位置，然后空队列，front=rear，满队列也是队尾和对首指向同一个位置。

顺序存储的队列时间复杂度T(n)=O(1);

4.2.3 队栈的链式存储实现

 1 package com.datastructure.chapter04.impl;
 2 
 3 import com.datastructure.chapter04.Exception.QueueEmptyException;
 4 import com.datastructure.chapter04.interfaces.Queue;
 5 
 6 public class QueueSLinked implements Queue {
 7 
 8     private SLNode front;
 9     
10     private SLNode rear;
11     
12     private int size;
13 
14     public QueueSLinked() {
15         front = new SLNode();
16         rear = front;
17         size = 0;
18     }
19     
20     
21     /* (非 Javadoc) 
22      * <p>Title: getSize</p> 
23      * <p>Description: 队列的长度</p> 
24      * @return 
25      * @see com.datastructure.chapter04.interfaces.Queue#getSize() 
26      */
27     @Override
28     public int getSize() {
29         return size;
30     }
31 
32     /* (非 Javadoc) 
33      * <p>Title: isEmpty</p> 
34      * <p>Description: 队列是否为空</p> 
35      * @return 
36      * @see com.datastructure.chapter04.interfaces.Queue#isEmpty() 
37      */
38     @Override
39     public boolean isEmpty() {
40         return size == 0;
41     }
42 
43     /* (非 Javadoc) 
44      * <p>Title: enqueue</p> 
45      * <p>Description: 入队</p> 
46      * @param e 
47      * @see com.datastructure.chapter04.interfaces.Queue#enqueue(java.lang.Object) 
48      */
49     @Override
50     public void enqueue(Object e) {
51         SLNode p = new SLNode(e, null);//创建新结点
52         rear.setNext(p);//队尾的下一个是新入队的结点
53         rear = p;//移动队尾指针至新入队的结点
54         size++;//长度加1
55     }
56 
57     /* (非 Javadoc) 
58      * <p>Title: dequeue</p> 
59      * <p>Description: 出队</p> 
60      * @return
61      * @throws QueueEmptyException 
62      * @see com.datastructure.chapter04.interfaces.Queue#dequeue() 
63      */
64     @Override
65     public Object dequeue() throws QueueEmptyException {
66         if(size<=0)
67             throw new QueueEmptyException("错误：队列为空");
68         SLNode p = front.getNext();//j
69         front.setNext(p.getNext());//直接将队首指向下下一个结点，就将队首结点移除掉了
70         size--;
71         if(size<1) rear = front;//若队列为空，rear指向头结点
72         return p.getData();
73     }
74 
75     /* (非 Javadoc) 
76      * <p>Title: peek</p> 
77      * <p>Description:取队首元素 </p> 
78      * @return
79      * @throws QueueEmptyException 
80      * @see com.datastructure.chapter04.interfaces.Queue#peek() 
81      */
82     @Override
83     public Object peek() throws QueueEmptyException {
84         if(size<=0)
85             throw new QueueEmptyException("错误：队列为空");
86         return front.getNext().getData();
87     }
88 
89 }

View Code

链式存储队列时间复杂度T(n)=O(1);

第四章 栈与队列2 （对列）

第四章栈与队列2 （对列）