队列的定义

• 仅允许在一端插入而在另一端删除
• 允许插入的一端称为队尾 (rear)
• 允许删除的一端称为队头 (front)
• 队列的插入操作称为入队 (push)

• 删除操作称为出队 (pop)

队列的特点

• 先进先出 (FIFO, First In First Out)
• 删除只能在队头

• 插入只能在队尾

队列的抽象数据类型

ADT Queue {
数据对象

$D=\{a_i|0\le i\le n-1,n\ge 0,A_i\mathrm{为}E\mathrm{类}\mathrm{型}\}$

数据关系

$r=\{<a_i,a_{i+1}>|a_i,a_{i+1}\in D,i=0,\dots ,n-2\}$

基本运算
    boolean empty();
    void push(E e)
    E pop();
    E peek() }

队列的顺序存储结构

• 非循环队列

• 循环队列

非循环队列

• 队头指针 front 指向队头元素的前一个位置
• 队尾指针 rear 指向队尾元素

• 初始时 front == rear == -1

非循环队列的基本要素

• 队空的条件是 front == rear
• 队满的条件是 rear == MaxSize - 1
• 进队操作是 rear = rear + 1; data[rear] = e;

• 出队操作是 e = data[front]; front = front + 1;

SqQueueClass<E>

class SqQueueClass<E>
{
    final int MaxSize=100;
    private E [] data;
    private int front,rear;
    public SqQueueClass()
    {
        data = (E[])new Object[MaxSize];
        front = -1;
        rear = -1;
    }
}

empty()

public boolean empty()
{
    return front == rear;
}

push(E e)

public void push(E e)
{
    if (rear == MaxSize - 1)
        throw new IllegalArgumentException("队满");
    rear++;
    data[rear]=e;
}

pop()

public E pop()
{
    if (empty())
        throw new IllegalArgumentException("队空");
    front++;
    return (E)data[front];
}

peek()

public E peek()
{
    if (empty())
        throw new IllegalArgumentException("队空");
    return (E)data[front + 1];
}

toString()

public String toString()
{
    String ans="";
    if (!empty())
    {
        int p = front;
        while (true)
        {
            p++;
            ans += data[p] + " ";
            if (p == rear) break;
        }
    }
    return ans;
}

非循环队列的假溢出

• rear == MaxSize - 1 时
• 再进队就会发生假溢出
• 实际上队列中有空位置

• 解决方法是使用循环队列

循环队列

• 连接 data 的前端和后端
• 形成逻辑上的环状结构
• 基于求余运算 (%, mod)
• 队头指针循环进一 front = (front + 1) % MaxSize

• 队尾指针循环进一 rear = (rear + 1) % MaxSize

循环队列的问题

• 如何分辨队空和队满?
• 队空条件是 front == rear
• 队满条件是 (rear + 1) % MaxSize == front

• 即队中最大元素个数为 MaxSize - 1

循环队列的基本要素

• 队空条件是 front == rear
• 队满条件是 (rear + 1) % MaxSize == front
• 进队操作是 rear = (rear + 1) % MaxSize; data[rear] = e;

• 出队操作是 e = data[front]; front = (front + 1) % MaxSize;

CSqQueueClass<E>

class CSqQueueClass<E>
{
    final int MaxSize=100;
    private E [] data;
    private int front,rear;
    public CSqQueueClass()
    {
        data = (E[])new Object[MaxSize];
        front = 0;
        rear = 0;
    }
}

empty()

public boolean empty()
{
    return front == rear;
}

push(E e)

public void push(E e)
{
    if ((rear+1)%MaxSize==front)
        throw new IllegalArgumentException("队满");
    rear = ( rear + 1 ) % MaxSize;
    data[rear]=e;
}

pop()

public E pop()
{
    if (empty())
        throw new IllegalArgumentException("队空");
    front = ( front + 1 ) % MaxSize;
    return (E)data[front];
}

peek()

public E peek()
{
    if (empty())
        throw new IllegalArgumentException("队空");
    return (E)data[( front + 1 ) % MaxSize];
}

size()

public int size()
{
    return ((rear-front+MaxSize)%MaxSize);
}

toString()

public String toString()
{
    String ans = "";
    if (!empty())
    {
        int p = front;
        while (true)
        {
            p = ( p + 1 ) % MaxSize;
            ans += data[p] + " ";
            if (p == rear) break;
        }
    }
    return ans;
}

队列的链式存储结构

• 无需头结点
• 队头指针 front 指向队头元素
• 队尾指针 rear 指向队尾元素

• 称作链队

链队的基本要素

• 队空条件是 front = rear == null
• 通常不考虑队满
• 进队操作是 rear.next = new Node(e); rear = rear.next;

• 出队操作是 e = front.data; front = front.next;

LinkNode<E>

class LinkNode<E>
{
    E data;
    LinkNode<E> next;
    public LinkNode()
    {
        next=null;
    }
    public LinkNode(E d)
    {
        data=d;
        next=null;
    }
}

LinkQueueClass<E>

public class LinkQueueClass<E>
{
    LinkNode<E> front;
    LinkNode<E> rear;
    public LinkQueueClass()
    {
        front=null;
        rear=null;
    }
}

empty()

public boolean empty()
{
    return front==null;
}

push(E e)

public void push(E e)
{
    LinkNode<E> s=new LinkNode<E>(e);
    if (empty())
        front=rear=s;
    else
    {
        rear.next=s;
        rear=s;
    }
}

pop()

public E pop()
{
    E e;
    if (empty())
        throw new IllegalArgumentException("队空");
    if (front==rear)
    {
        e=(E)front.data;
        front=rear=null;
    }
    else
    {
        e=(E)front.data;
        front=front.next;
    }
    return e;
}

peek()

public E peek()
{
    if (empty())
        throw new IllegalArgumentException("队空");
    E e=(E)front.data;
    return e;
}

toString()

public String toString()
{
    String ans="";
    if (!empty())
    {
        LinkNode<E> p=front;
        while (p!=null)
        {
            ans+=p.data.toString()+" ";
            p=p.next;
        }
    }
    return ans;
}