第四章涉及三种数据存储类型：栈，队列，优先级队列
1.概括：他们比数组和其他数据存储结构更为抽象，主要通过接口对栈，队列和优先级队列进行定义。这些
接口表明通过他们可以完成的操作，而他们的主要实现机制对用户来说是不可见的。（比如栈可以使用数组实现，也可以使用链表实现）
2.栈：
先进后出。
数据项进栈和入栈的时间复杂度都是O(1),也就是说栈操作所消耗的时间不依赖于数据项的个数，因此栈操作时间短。栈操作不需要比较和移动操作。
3.队列：
先进先出。例如：银行排队办业务，飞机等待起飞，网络数据包等待传送。。。
操作系统中各种队列：打印机作业在打印队列中等待打印；键盘敲击时，存储键入内容的队列；。。
*insert：把一个元素放入队尾
*remove：移除队头的元素。
栈中的push和pop命名很标准，队列的方法至今没有标准化的命名。insert(put,add,enque); remove(delete, get,deque)等
问题：
往队列中插入一个新元素，队头的rear箭头向上移动，移向数组下标大的位置。移除元素时，队尾Front指针也会向上移动。
这种情况和人们直觉相反，因为排队买票的时候，队伍总是向前移动的，当前面的人买完票离开队伍后，其他人都向前移动。
计算机中在队列里删除一个数据项后，也可以将其他数据项都向前移动，但是这样效率很差。
相反，通过队列中队头和队尾指针的移动保持所有的数据项的位置不变。
这样设计的问题是，队尾指针很快就会移动到数组的末端。，队尾指针不能再向后移动，无法移除也不能插入。
解决：循环队列，有时也称缓冲环。
在队列中插入足够多的数据项，队尾指针移动到高下标，再删除几个队头的数据项，再插入的时候，对为指针回绕到下标0；
在删除足够多数据项后，队头指针也回绕。
--->:没有数据项计数字段的队列：
在循环队列中nItems是计数字段，它的存在会使得insert和remove方法增加一点额外的操作，因为insert和remove方法必须分别递增
或者递减这个变量值。这可能算不上额外的开销，但是如果处理大量的插入和移除操作，就会影响性能。因此一些队列的实现不使用计数字段。
而是通过front和rear来计算出队列是否为空或者满以及数据项的个数。数据项的序列或者被折成两段，或者是连续的一段。
而且也出现一个问题：当队列满地时候，front和rear指针取一定的位置，但是当队列为空时，也可能呈现相同的位置关系。于是，在同一时间，
队列可能满也可能空。
--->:解决：让数组容量比队列数据项个数的最大值大一。
/**
* 不带计数字段的循环队列
*/
class QueueNoCount {
private int maxSize;
private long[] queue;
private int front, rear;
public QueueNoCount(int size) {
maxSize = size + 1;
queue = new long[maxSize];
front = 0;
rear = -1;
}
public void insert(long value) throws Exception {
if (isFull()) {
throw new Exception("queue is full, can not insert " + value);
}
if (rear == maxSize - 1)
rear = -1;
queue[++rear] = value;
}
public long remove() throws Exception {
if (isEmpty()) {
throw new Exception("queue is empty, can not remove");
}
long temp = queue[front++];
if (front == maxSize)
front = 0;
return temp;
}
public long peek() {
return queue[front];
}
public boolean isEmpty() {
return (rear + 1 == front) || (front + maxSize - 1 == rear);
}
public boolean isFull() {
return (rear + 2 == front) || (front + maxSize - 2 == rear);
}
public int size() {
if(isEmpty()) return 0;
if(isFull()) return maxSize-1;
if (rear >= front)
return rear - front + 1;
return (maxSize - front) + (rear + 1);
}
}
public class QueueNoCountDemo {
public static void main(String[] args) {
QueueNoCount q= new QueueNoCount(5);
try{
for(int i=1;i<7;i++){
q.insert(i);
System.out.println(i+"入队"+".对列中元素个数:"+q.size());
}
}catch(Exception e){
System.out.println(e);
}
try{
for(int i=1;i<7;i++){
System.out.println(q.remove()+"出队"+".对列中元素个数:"+q.size());
}
}catch(Exception e){
System.out.println(e);
}
System.out.println(q.size());
}
}