1，队列

• “队列”（queue）这个单词是英国人说的"排"（line）（一种等待服务的方式）。在英国，"排队"的意思就是站到一排当中去。
• 计算机科学中，队列是一种数据结构，有点类似栈，只是在队列中第一个插入的数据项也会最先被移除（先进先出，FIFO），而在栈中，最后插入的数据项最先移除（LIFO）。
• 队列的作用就像电影院前的人们站成的排一样：第一个进入队尾的人将最先到达队头买票。最后排队的人最后才能买到票（或许，售票处挂出售空的牌子，就买不到票了）。

2，循环队列

• 为了避免随着不断地增删数据而出现的队列不满却不能插入新数据项的问题，可以让队头队尾指针绕回到数组开始的位置。这就是循环队列（也称为缓冲环）。
• 在队列中插入足够多的数据项，使队尾指针指向数组的高端，再删除几个数组前端的数据项。
• 插入更多的数据项。队尾指针向上移动。注意在队尾指针回绕之后，现在处于队头指针的下面，这就颠倒了起始的位置。这可以称为"折断的序列"：队列中的数据项存在数组两个不同的序列中。
• 删除足够多的数据项后，队头指针也回绕。这时队列的指针回到了初始运行时的位置状态，对头指针在队尾指针下面。数据项也恢复为单一的连续的序列。

3，队列的Java代码

/*
 * demonstrates queue
 * */
class Queue
{
    private int maxSize;
    private long[] queArray;
    private int front;
    private int rear;
    private int nItems;

    public Queue(int s)//constructor
    {
        maxSize = s;
        queArray = new long[maxSize];
        front = 0;
        rear = -1;
        nItems = 0;
    }

    public void insert(long j)//put item at rear of queue
    {
        if (rear == maxSize - 1)//deal with wraparound
        {
            rear = -1;
        }
        queArray[++rear] = j;//increment rear and insert
        nItems++;//one more item
    }

    public long remove()//take item from front of queue
    {
        long temp = queArray[front++];//get value and incr front
        if (front == maxSize)//deal with wraparound
        {
            front = 0;
        }
        nItems--;//one less item
        return temp;
    }

    public long peekFront()//peek at front of queue
    {
        return queArray[front];
    }

    public boolean isEmpty()//true if queue is empty
    {
        return (nItems == 0);
    }

    public boolean isFull()//true if queue is full
    {
        return (nItems == maxSize);
    }

    public int size()//number of items in queue
    {
        return nItems;
    }
}//end class Queue

public class QueueApp
{
    public static void main(String[] args)
    {
        Queue theQueue = new Queue(5);//queue holds 5 items

        theQueue.insert(10);//insert 4 items
        theQueue.insert(20);
        theQueue.insert(30);
        theQueue.insert(40);

        theQueue.remove();//remove 3 items(10,20,30)
        theQueue.remove();
        theQueue.remove();

        theQueue.insert(50);//insert 4 more items(wraps around)
        theQueue.insert(60);
        theQueue.insert(70);
        theQueue.insert(80);

        while (!theQueue.isEmpty())//remove and display all items
        {
            long n = theQueue.remove();//(40,50,60,70,80)
            System.out.print(n);
            System.out.print(" ");
        }
        System.out.println("");
    }//end main()
    /*
     * 输出结果
     * 40 50 60 70 80
     * */
}//end class QueueApp

4，队列的效率

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

5，双端队列

• 双端队列就是一个两端都是结尾的队列。队列的每一端都可以插入数据项和移除数据项。
• 这些方法可以叫做insertLeft()和insertRight()，以及removeLeft()和removeRight()。
• 如果严格禁止调用insertLeft()和removeLeft()方法（或禁用右端的操作），双端队列功能就和栈一样。禁止调用insertLeft()和removeRight()方法（或相反的另一对方法），它的功能就和队列一样了。
• 双端队列与栈或队列相比，是一种多用途的数据结构，在容器类库中有时会用双端队列来提供栈和队列的两种功能。但是，双端队列不像栈和队列那么常用。

6，优先级队列

• 优先级队列是比栈和队列更专用的数据结构。在很多情况下都很有用。像普通队列一样，优先级队列有一个队头和一个队尾，并且也是从对头移除数据项。不过在优先级队列中，数据项按关键字的值有序，这样关键字最小的数据项（或者关键字最大的数据项）总是在队头。数据项插入的时候会按照顺序插入到合适的位置以确保队列的顺序。

7，优先级队列的Java代码

import java.io.IOException;

/*
 * demonstrates priority queue
 * */
class PriorityQ
{
    //array in sorted order, from max at 0 to min at size-1
    private int maxSize;
    private long[] queArray;
    private int nItems;

    public PriorityQ(int s)//constructor
    {
        maxSize = s;
        queArray = new long[maxSize];
        nItems = 0;
    }

    public void insert(long item)//insert item
    {
        int j;
        if (nItems == 0)//if no items
        {
            queArray[nItems++] = item;//insert at 0
        }
        else
        {
            for (j = nItems - 1; j >= 0; j--)//start at end
            {
                if (item > queArray[j])//if new item larger
                {
                    queArray[j + 1] = queArray[j];//shift upward
                }
                else//if smaller
                {
                    break;//done shifting
                }
            }//end for
            queArray[j + 1] = item;//insert it
            nItems++;
        }//end else(nItems>0)
    }//end insert()

    public long remove()//remove minimum item
    {
        return queArray[--nItems];
    }

    public long peekMin()//peek at minimum item
    {
        return queArray[nItems - 1];
    }

    public boolean isEmpty()//true if queue is empty
    {
        return (nItems == 0);
    }

    public boolean isFull()//true if queue is full
    {
        return (nItems == maxSize);
    }
}//end class PriorityQ

public class PriorityQApp
{
    public static void main(String[] args) throws IOException
    {
        PriorityQ thePQ = new PriorityQ(5);
        thePQ.insert(30);
        thePQ.insert(50);
        thePQ.insert(10);
        thePQ.insert(40);
        thePQ.insert(20);
        while (!thePQ.isEmpty())
        {
            long item = thePQ.remove();
            System.out.print(item + " ");//10 20 30 40 50 
        }//end while
        System.out.println("");
    }//end main
}//end class PriorityQApp

8，栈和队列的比较

• 栈、队列和优先级队列是经常用于简化某些程序操作的数据结构。
• 在这些数据结构中，只有一个数据项可以被访问。
• 栈允许访问最后一个插入的数据项。
• 栈中重要的操作是在栈顶插入（压入）一个数据项，以及从栈顶移除（弹出）一个数据项。
• 队列只允许访问第一个插入的数据项。
• 队列的重要操作是在队尾插入数据项和在队头移除数据项。
• 队列可以实现为循环队列，它基于数组，数组下标可以从数组末端回绕到数组的开始位置。
• 优先级队列允许访问最小（或者有时是最大）的数据项。
• 优先级队列的重要操作是有序地插入新数据项和移除关键字最小的数据项。
• 这些数据结构可以用数组实现，也可以用其他机制（例如链表）来实现。
• 普通算术表达式是用中缀表达法表示的，这种命名的原因是操作符写在两个操作数的中间。
• 在后缀表达法中，操作符跟在两个操作数的后面。
• 算术表达式求值通常都是先转换成后缀表达式，然后再求后缀表达式的值。
• 在中缀表达式转换到后缀表达式以及求后缀表达式的值的过程里，栈都是很有用的工具。