特点——先进先出:
只允许一端进行插入操作,另一端进行删除操作的 线性表
插入一段是队尾,删除的一端是队头
存储方式——顺序存储和链式存储
顺序存储
顺序存储用数组实现
假设有N个元素的一个队列,数组下标为0的一端是对头,入队操作就是通过数组下标一个个顺序追加,不需要移动元素,如果删除对头元素,后面的元素就要往前移动,这种方式性能不高
顺序队列的实现代码如下:
public class ArrayQueue {
private Array<E> data;
public ArrayQueue(){
this.data = new DynamicArray();
}
public boolean isEmpty() {
return data.isEmpty();
}
public int size() {
return data.size();
}
public void enqueue(E e) {
data.add(e);
}
public E dequeue() {
return data.remove(0);
}
public E head() {
return data.get(0);
}
@Override
public String toString() {
return "Head " + data.toString() + " Tail";
}
}
为了提高队的性能,于是出现了循环队列
循环队列
就是有两个指针,front指向队头,rear指向对尾元素的下一个位置
元素出队时front往后移动,如果到了对尾则转到头部,同理入队时rear后移,如果到了对尾则转到头部,这样通过下标front出队时,就不需要移动元素了
循环操作rear依次后移,然后再从头开始,出现rear和front相等时,队列满
注意(当队列为空时,front和rear相等 当队列为满时,front和rear也相等)
为了区分这种情况,规定数组还有一个空闲单元时,就表示队列已满
因为rear 可能在front后面,也可能循环到front前面,所以队列满的条件就变成了(rear+1)%maxsize = front ,同时队列元素个数的计算就是(rear -front+maxsize)%maxsize
循环队列的实现代码如下:
public class LoopQueue<E> {
private E[] data;
private int size;
private int tail;
private int head;
public LoopQueue(){
this(8);
}
public LoopQueue(int capcaity) {
this.data = (E[]) new Object[capcaity + 1];
this.head = 0;
this.tail = 0;
this.size = 0;
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public void enqueue(E e) {
if((tail + 1) % data.length == head % data.length){
resize(data.length * 2);
}
data[tail] = e;
tail = (tail + 1)% data.length;
size++;
}
public E dequeue() {
if(tail == head){
return null;
}
E e = data[head];
head = (head + 1)% data.length;
size--;
if(size == data.length / 4 && data.length / 2 != 0){
resize(data.length / 2);
}
return e;
}
public E head() {
return data[head];
}
private void resize(int newCapcaity){
E[] newData = (E[])new Object[newCapcaity + 1];
for(int i = 0 ; i < size ; i ++) {
newData[i] = data[(i + head) % data.length];
}
head = 0;
tail = size;
data = newData;
}
@Override
public String toString() {
StringBuilder sBuilder = new StringBuilder();
sBuilder.append("Head ");
for(int i = 0 ; i < size ; i ++) {
sBuilder.append(data[(i + head) % data.length]).append(",");
}
int lastIndex = sBuilder.lastIndexOf(",");
if(lastIndex != -1){
sBuilder.deleteCharAt(lastIndex);
}
sBuilder.append(" Tail");
return sBuilder.toString();
}
温馨提示:
循环队列要事先申请好空间,整个过程都不能释放,而且要有固定的长度
链式列表:
由于循环队列不够灵活,于是引入了链式存储队列,即线性表的单链表
它只能对尾进,队头出,并且规定队头指针指向链队列的头结点,对尾指针指向终端节点
当队列为空时,front和rear都指向头结点
具体实现代码如下:
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20
typedef int Status;
typedef int QElemType;
//结点结构
typedef struct QNode{
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
//队列的链表结构