读JSE源码（四）栈和队列
1 总述1.1栈 stack

定义：栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行。

特点：先进后出

基本操作：

入栈push,

出栈pop,

获取栈定元素peek，

判断栈是否为空isEmpty.

实现：栈可以用数组实现，也可以用链表实现。

栈的链表实现 栈的数组实现

队列：先进先出

基本操作：

add添加元素到队尾

remove移除队头元素

peek获取队头元素

isEmpty方法判断队列是否为空

Dequeue是JSE定义的双端队列接口（double ended queue），定义了元素可以从两端插入和删除元素。可以利用Dequeue定义的方法实现栈和队列。在使用该接口时可以用对应的方法作为栈或者队列这2种数据结构的操作（下图中左边的方法其实调用了右边方法）：

栈和队列的数组实现是ArrayDeque，链表实现是LinkedList。其类关系图如下

使用

JSE的栈实现
1）ArrayDeque
当数组放满元素时，会将其元素复制到另一个更大容量的数组中。

1)ArrayDeque
其内部实现类似于下述代码，用front和rear记录当前队列的队头和队尾。用数组实现队列是需要，需要考虑当rear到达数组最大位置处，如何添加元素？

当rear指向数组最大位置处时，需要重新回来数组开始处，如此形成循环，如下图

// Queue.java// demonstrates queue// to run this program: C>java QueueApp////////////////////////////////////////////////////////////////class Queue   {   private int maxSize;   private E[] queArray;   private int front;   private int rear;   private int nItems;//--------------------------   public Queue(int s)          // constructor      {      maxSize = s;      queArray = (E())new Object[maxSize];      front = 0;      rear = -1;      nItems = 0;      }//--------------------------   public void insert(E 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 E remove()         // take item from front of queue      {      E temp = queArray[front++]; // get value and incr front      if(front == maxSize)           // deal with wraparound         front = 0;      nItems--;                      // one less item      return temp;      }//--------------------------   public E 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////////////////////////////////////////////////////////////////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      theQueue.remove();              //    (10, 20, 30)      theQueue.remove();      theQueue.insert(50);            // insert 4 more items      theQueue.insert(60);            //    (wraps around)      theQueue.insert(70);      theQueue.insert(80);      while( !theQueue.isEmpty() )    // remove and display         {                            //    all items         E n = theQueue.remove();  // (40, 50, 60, 70, 80)         System.out.print(n);         System.out.print(" ");         }      System.out.println("");      }  // end main()   }  // end class QueueApp////////////////////////////////////////////////////////////////
2）LinkdedList
add方法将元素加入链表末端
remove方法移除链表头元素
peek方法获取链表头元素
isEmpty方法判断队列是否为空