本文共 13871 字，大约阅读时间需要 46 分钟。

1 栈 Stack

栈的英文单词是Stack，它代表一种特殊的线性表，这种线性表只能在固定一端（通常认为是线性表的尾端）进行插入、删除操作。

栈是一种数据结构，它代表只能在某一端进行插入、删除操作的特殊线性表，通常就是在线性表的尾端进行插入、删除操作。 对于栈而言，允许进行插入、删除操作的一端被称为栈顶（top），另一端则被称为栈底（bottom）。 如果一个栈不包含任何元素，那这个栈就被称为空栈。 从栈顶插入一个元素被称为进栈，将一个元素插入栈顶被称为“压入栈”——对应的英文说法为push。 从栈顶删除一个元素被称为出栈，将一个元素从栈顶删除被称为“弹出栈”——对应的英文说法为pop。 栈是一种被限制过的线性表，通常不应该提供线性表中的如下方法。

• 获取指定索引处的元素；
• 按值查找数据元素的位置；
• 向指定索引处插入数据元素；
• 删除指定索引处的数据元素。

栈的常用操作如下:

• 初始化：通常是一个构造器，用于创建一个空栈。
• 返回栈的长度：该方法用于返回栈中数据元素的个数。
• 入栈：向栈的栈顶插入一个数据元素，栈的长度+1。
• 出栈：从栈的栈顶删除一个数据元素，栈的长度-1，该方法通常返回被删除的元素。
• 访问栈顶元素：返回栈顶的数据元素，但不删除栈顶元素。
• 判断栈是否为空：该方法判断栈是否为空，如果栈为空返回true，否则返回false。
• 清空栈：将栈清空。

public class SequenceStack
   
         {
              private int DEFAULT_SIZE = 10;           //保存数组的长度           private int capacity;           //定义当底层数组容量不够时，程序每次增加的数组长度           private int capacityIncrement = 0;           //定义一个数组用于保存顺序栈的元素           private Object[] elementData;           //保存顺序栈中元素的当前个数           private int size = 0;           //以默认数组长度创建空顺序栈           public SequenceStack()           {
                    capacity = DEFAULT_SIZE;                 elementData = new Object[capacity];           }           //以一个初始化元素来创建顺序栈           public SequenceStack(T element)           {
                    this();                 elementData[0] = element;                 size++;           }           /**            * 以指定长度的数组来创建顺序栈            * @param element 指定顺序栈中第一个元素            * @param initSize 指定顺序栈底层数组的长度            */           public SequenceStack(T element , int initSize)           {
                    this.capacity = initSize;                 elementData = new Object[capacity];                 elementData[0] = element;                 size++;           }           /**            * 以指定长度的数组来创建顺序栈            * @param element 指定顺序栈中第一个元素            * @param initSize 指定顺序栈底层数组的长度            * @param capacityIncrement 指定当顺序栈底层数组的长度不够时，底层数组每次增加的长度            */           public SequenceStack(T element , int initSize                 , int capacityIncrement)           {
                    this.capacity = initSize;                 this.capacityIncrement = capacityIncrement;                 elementData = new Object[capacity];                 elementData[0] = element;                 size++;           }           //获取顺序栈的大小           public int length()           {
                    return size;           }           //入栈           public void push(T element)           {
                    ensureCapacity(size + 1);                 elementData[size++] = element;           }           //很麻烦，而且性能很差           private void ensureCapacity(int minCapacity)           {
                    //如果数组的原有长度小于目前所需的长度                 if (minCapacity > capacity)                 {
                          if (capacityIncrement > 0)                       {
                                while (capacity < minCapacity)                             {
                                                                  //不断地将capacity长度加capacityIncrement                                   //直到capacity大于minCapacity为止                                   capacity += capacityIncrement;                             }                       }                       else                       {
                                //不断地将capacity * 2,直到capacity大于minCapacity为止                             while (capacity < minCapacity)                             {
                                       capacity <<= 1;                             }                       }                       elementData = Arrays.copyOf(elementData , capacity);                 }           }           //出栈         public T pop()           {
                    T oldValue = (T)elementData[size - 1];                 //释放栈顶元素                 elementData[--size] = null;                  return oldValue;           }           //返回栈顶元素,但不删除栈顶元素         public T peek()           {
                    return (T)elementData[size - 1];           }           //判断顺序栈是否为空栈           public boolean empty()           {
                    return size == 0;           }           //清空顺序栈           public void clear()           {
                    //将底层数组所有元素赋为null                 Arrays.fill(elementData , null);                 size = 0;           }           public String toString()           {
                    if (size == 0)                 {
                          return "[]";                 }                 else                 {
                          StringBuilder sb = new StringBuilder("[");                       for (int i = size - 1  ; i > -1 ; i-- )                       {
                                 sb.append(elementData[i].toString() + ", ");                       }                       int len = sb.length();                       return sb.delete(len - 2 , len).append("]").toString();                 }           }     }
   

2.队列

队列（Queue）是另一种被限制过的线性表，它使用固定的一端来插入数据元素，另一端只用于能删除元素。也就是说，队列中元素的移动方向总是固定的，就像排队购物一样：先进入队伍的顾客先获得服务，队伍中的顾客总是按固定方向移动，只有当排在自己前面的所有顾客获得服务之后，当前顾客才会获得服务。

队列是一种特殊的线性表，它只允许在表的前端（front）进行删除操作，只允许在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。

如果队列中不包含任何元素，该队列就被称为空队列。

对于一个队列来说，每个元素总是从队列的rear端进入队列，然后等待该元素之前的所有元素出队之后，当前元素才能出队。因此，把队列简称为先进先出（FIFO）的线性表。

队列的常用操作如下：

• 初始化：通常是一个构造器，用于创建一个空队列。
• 返回队列的长度：该方法用于返回队列中数据元素的个数。
• 加入元素：向队列的rear端插入一个数据元素，队列的长度+1。
• 删除元素：从队列的front端删除一个数据元素，队列长度-1，该方法通常返回被删除的元素。
• 访问队列的前端元素：返回队列的front端的数据元素，但不删除该元素。
• 判断队列是否为空：该方法判断队列是否为空，如果队列为空返回true，否则返回false。
• 清空队列：将队列清空。

public class SequenceQueue
   
         {
              private int DEFAULT_SIZE = 10;           //保存数组的长度           private int capacity;           //定义一个数组用于保存顺序队列的元素           private Object[] elementData;           //保存顺序队列中元素的当前个数           private int front = 0;           private int rear = 0;           //以默认数组长度创建空顺序队列           public SequenceQueue()           {
                    capacity = DEFAULT_SIZE;                 elementData = new Object[capacity];           }           //以一个初始化元素创建顺序队列           public SequenceQueue(T element)           {
                    this();                 elementData[0] = element;                 rear++;           }           /**            * 以指定长度的数组来创建顺序队列            * @param element 指定顺序队列中第一个元素            * @param initSize 指定顺序队列底层数组的长度            */           public SequenceQueue(T element , int initSize)           {
                    this.capacity = initSize;                 elementData = new Object[capacity];                 elementData[0] = element;                 rear++;           }           //获取顺序队列的大小           public int length()           {
                    return rear - front;           }           //插入队列           public void add(T element)           {
                    if (rear > capacity - 1)                 {
                           throw new IndexOutOfBoundsException("队列已满的异常");                 }                 elementData[rear++] = element;           }           //移除队列         public T remove()           {
                    if (empty())                 {
                           throw new IndexOutOfBoundsException("空队列异常");                 }                 //保留队列的rear端的元素的值                 T oldValue = (T)elementData[front];                 //释放队列的rear端的元素                 elementData[front++] = null;                  return oldValue;           }           //返回队列顶元素，但不删除队列顶元素           public T element()           {
                    if (empty())                 {
                          throw new IndexOutOfBoundsException("空队列异常");                 }                 return (T)elementData[front];           }           //判断顺序队列是否为空队列           public boolean empty()           {
                    return rear == front;           }           //清空顺序队列           public void clear()           {
                    //将底层数组所有元素赋为null                 Arrays.fill(elementData , null);                 front = 0;                 rear = 0;           }           public String toString()           {
                    if (empty())                 {
                           return "[]";                 }                 else                 {
                           StringBuilder sb = new StringBuilder("[");                        for (int i = front  ; i < rear ; i++ )                        {
                                  sb.append(elementData[i].toString() + ", ");                        }                        int len = sb.length();                        return sb.delete(len - 2 , len).append("]").toString();                 }      }     }
   

对于“假满”问题，程序有如下解决方法。

• 每次将元素移出队列时都将队列中的所有元素向front端移动一位，这种方式下front值永远为0，元素插入队列时rear值+1，元素移出队列时rear -1。但这种方式非常浪费时间，因为每次将元素从队列移除都需进行“整体搬家”。
• 数组存储区看成一个首尾相接的环形区域，当存放到数组的最大地址之后，rear的值再次变为0。采用这种技巧存储的队列称为循环队列。

3 循环队列

public class LoopQueue
   
         {
              private int DEFAULT_SIZE = 10;           //保存数组的长度           private int capacity;           //定义一个数组用于保存循环队列的元素           private Object[] elementData;           //保存循环队列中元素的当前个数           private int front = 0;           private int rear = 0;           //以默认数组长度创建空循环队列           public LoopQueue()           {
                    capacity = DEFAULT_SIZE;                 elementData = new Object[capacity];           }           //以一个初始化元素创建循环队列           public LoopQueue(T element)           {
                    this();                 elementData[0] = element;                 rear++;           }           /**            * 以指定长度的数组来创建循环队列            * @param element 指定循环队列中第一个元素            * @param initSize 指定循环队列底层数组的长度            */           public LoopQueue(T element , int initSize)           {
                    this.capacity = initSize;                 elementData = new Object[capacity];                 elementData[0] = element;                 rear++;           }           //获取循环队列的大小           public int length()           {
                    if (empty())                 {
                          return 0;                 }                 return rear > front ? rear - front                        : capacity - (front - rear);           }           //插入队列           public void add(T element)           {
                    if (rear == front                        && elementData[front] != null)                 {
                          throw new IndexOutOfBoundsException("队列已满的异常");                 }                 elementData[rear++] = element;                 //如果rear已经到头，那就转头                 rear = rear == capacity ? 0 : rear;           }           //移除队列         public T remove()           {
                    if (empty())                 {
                          throw new IndexOutOfBoundsException("空队列异常");                 }                 //保留队列rear端的元素的值                 T oldValue = (T)elementData[front];                 //释放队列rear端的元素                 elementData[front++] = null;                                  //如果front已经到头，那就转头                 front = front == capacity ? 0 : front;                 return oldValue;           }           //返回队列顶元素，但不删除队列顶元素         public T element()           {
                    if (empty())                 {
                          throw new IndexOutOfBoundsException("空队列异常");                 }                 return (T)elementData[front];           }           //判断循环队列是否为空队列           public boolean empty()           {
                    //rear==front且rear处的元素为null                 return rear == front                        && elementData[rear] == null;           }           //清空循环队列           public void clear()           {
                    //将底层数组所有元素赋为null                 Arrays.fill(elementData , null);                 front = 0;                 rear = 0;           }           public String toString()           {
                    if (empty())                 {
                          return "[]";                 }                 else                 {
                          //如果front < rear，有效元素就是front到rear之间的元素                       if (front < rear)                       {
                                  StringBuilder sb = new StringBuilder("[");                               for (int i = front  ; i < rear ; i++ )                               {
                                         sb.append(elementData[i].toString() + ", ");                               }                               int len = sb.length();                               return sb.delete(len - 2 , len).append("]").toString();                       }                       //如果front >= rear，有效元素为front到capacity之间、0到front之间的元素                       else                       {
                                  StringBuilder sb = new StringBuilder("[");                               for (int i = front  ; i < capacity ; i++ )                               {
                                         sb.append(elementData[i].toString() + ", ");                               }                               for (int i = 0 ; i < rear ; i++)                               {
                                         sb.append(elementData[i].toString() + ", ");                               }                               int len = sb.length();                               return sb.delete(len - 2 , len).append("]").toString();                       }                 }           }     }
   

4. 双向队列

双向队列（由英文单词Deque代表）代表一种特殊的队列，它可以在两端同时进行插入、删除操作

双向队列（Deque）既可说是Queue的子接口，也可说是Stack（JDK并未提供这个接口）的子接口。因此，Deque既可当成队列使用，也可当成栈使用。

由此可见，Deque其实就是Queue和Stack混合而成的一种特殊线性表，完全可以参考前面的Queue、Stack的实现类来实现此处的Deque，此处不再赘述。

JDK虽然提供了一个古老的Stack类，但现在已经不再推荐开发者使用这个古老的“栈”实现，而是推荐使用Deque实现类作为“栈”使用。

JDK为Deque提供了ArrayDeque、LinkedBlockingDeque、LinkedList这3个实现类。其中，ArrayDeque代表顺序存储结构的双向队列，LinkedList则代表链式存储结构的双向队列，LinkedBlockingDeque其实是一个线程安全的、链式结构的双向队列。

JDK提供的工具类确实非常强大，它分别为线性表、队列、栈3种数据结构提供了两种实现：顺序结构和链式结构。虽然LinkedList工具类的功能非常强大，它既可当成线性表使用，也可当成栈使用，还可当成队列使用，但对大部分程序而言，使用ArrayList、ArrayDeque的性能比LinkedList更好。

转载地址：https://blog.csdn.net/ynchyong/article/details/112318461 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！