java中堆栈的实现总结

Love The Way You Lie 2023-10-08 21:03 30阅读 0赞

#### java中队列和栈的类实现总结 ####

*  1. Java中的Stack
 *   *  1.1 Stack类的使用
     *  1.2 Stack类的分析
 *  2. java中的queue
 *   *  2.1 queue的方法定义
     *  2.2 Deque
     *  2.3 Queue的常见实现类
 *  3. 总结

## 1. Java中的Stack ##

### 1.1 Stack类的使用 ###

Stack的声明如下，可以看到Stack继承了Vector，因此Stack可以使用Vector中的方法，如size() 等。

public
    class Stack<E> extends Vector<E>

Stack类定义了**5个**方法，作用如下

<table> 
 <thead> 
  <tr> 
   <th>方法</th> 
   <th>描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>push</td> 
   <td>将对象压入栈</td> 
  </tr> 
  <tr> 
   <td>pop</td> 
   <td>将栈顶元素弹出</td> 
  </tr> 
  <tr> 
   <td>peek</td> 
   <td>返回栈顶对象，但并不从栈中移除</td> 
  </tr> 
  <tr> 
   <td>empty</td> 
   <td>判断栈是否为空</td> 
  </tr> 
  <tr> 
   <td>search(E o)</td> 
   <td>返回对象在堆栈中的位置，若不存在则返回-1</td> 
  </tr> 
 </tbody> 
</table>

### 1.2 Stack类的分析 ###

Stack是继承自Vector的，而Vector是线程安全的，所以Stack也是线程安全的。

然而正因为Stack继承自Vector，\*\*Stack类已经不被官方推荐使用！！\*\*基于 Vector 实现的栈 Stack。底层实际上还是数组，所以还是存在需要扩容。这使得 Stack 在基于数组实现上效率受影响，另外因为继承 Vector 类，Stack 可以复用 Vector 大量方法，这使得 Stack 在设计上不严谨。

官方推荐使用LinkedList来构建栈。

## 2. java中的queue ##

### 2.1 queue的方法定义 ###

与Stack不同，Java里的Queue不是一个类，而是一个接口。

Java集合类主要由两个根接口Collection和Map派生出来的，Collection派生出了三个子接口：List、Set、Queue，因此Java集合大致也可分成List、Set、Queue、Map四种接口体系.

接口中共定义了6个主要的方法

<table> 
 <thead> 
  <tr> 
   <th>方法</th> 
   <th>描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>add</td> 
   <td>在队列尾部插入一个元素（队列满时抛异常）</td> 
  </tr> 
  <tr> 
   <td>offer</td> 
   <td>在队列尾部插入一个元素（队列满时返回false）</td> 
  </tr> 
  <tr> 
   <td>remove</td> 
   <td>返回队列头部的对象，并从栈中移除它（队列为空时，抛异常）</td> 
  </tr> 
  <tr> 
   <td>poll</td> 
   <td>返回队列头部的对象，并从栈中移除它（队列为空时，返回null）</td> 
  </tr> 
  <tr> 
   <td>element</td> 
   <td>返回队列头部的对象，但不从栈中移除它（队列为空时，抛异常）</td> 
  </tr> 
  <tr> 
   <td>peek</td> 
   <td>返回队列头部的对象，但不从栈中移除它（队列为空时，返回null）</td> 
  </tr> 
 </tbody> 
</table>

**速记**：add、element、remove（are是：是不是抛异常？是）抛异常；offer、poll、peek（opp）返回特定的值。

### 2.2 Deque ###

queue是后入先出，但是java中还有一个叫deque的队列，叫双端队列，可以实现两端的入队和出队，在有些场景，用起来是相当方便的。

其方法总结如下：

<table> 
 <thead> 
  <tr> 
   <th></th> 
   <th></th> 
   <th></th> 
   <th></th> 
   <th></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td></td> 
   <td><em>抛出异常</em></td> 
   <td><em>特殊值</em></td> 
   <td><em>抛出异常</em></td> 
   <td><em>特殊值</em></td> 
  </tr> 
  <tr> 
   <td>插入</td> 
   <td>addFirst(e)</td> 
   <td>offerFirst(e)</td> 
   <td>addLast(e)</td> 
   <td>offerLast(e)</td> 
  </tr> 
  <tr> 
   <td>删除</td> 
   <td>removeFirst()</td> 
   <td>pollFirst()</td> 
   <td>removeLast()</td> 
   <td>pollLast()</td> 
  </tr> 
  <tr> 
   <td>检查</td> 
   <td>getFirst()</td> 
   <td>peekFirst()</td> 
   <td>getLast()</td> 
   <td>peekLast()</td> 
  </tr> 
 </tbody> 
</table>

### 2.3 Queue的常见实现类 ###

![image-20230320222620439][]

<table> 
 <thead> 
  <tr> 
   <th>实现类</th> 
   <th>描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td><strong>PriorityQueue</strong></td> 
   <td>非阻塞、非线程安全、无边界，支持优先级队列实现类</td> 
  </tr> 
  <tr> 
   <td><strong>ConcurrentLinkedQueue</strong></td> 
   <td>非阻塞、线程安全、无边界，基于链接节点的队列实现类</td> 
  </tr> 
  <tr> 
   <td><strong>ArrayBlockingQueue</strong></td> 
   <td>阻塞、线程安全、有边界，创建的时候指定大小，一旦创建容量不可改变实现类，默认是不保证线程的公平性，不允许向队列中插入null元素</td> 
  </tr> 
  <tr> 
   <td><strong>LinkedBlockingQueue</strong></td> 
   <td>阻塞、线程安全、可选有边界，一个由链表结构组成的可选有界阻塞队列实现类，如果未指定容量，那么容量将等于<code>Integer.MAX_VALUE</code></td> 
  </tr> 
  <tr> 
   <td><strong>PriorityBlockingQueue</strong></td> 
   <td>阻塞、线程安全、无边界，支持优先级排序的无边界阻塞队列实现类</td> 
  </tr> 
  <tr> 
   <td><strong>DelayQueue</strong></td> 
   <td>阻塞、线程安全、无边界，使用优先级队列实现的无界阻塞队列实现类，只有在延迟期满时才能从中提取元素</td> 
  </tr> 
  <tr> 
   <td><strong>SynchronousQueue</strong></td> 
   <td>阻塞、线程安全、无数据队列，不存储元素、没有内部容量的阻塞队列实现类</td> 
  </tr> 
  <tr> 
   <td><strong>LinkedBlockingDeque</strong></td> 
   <td>阻塞、线程安全、无边界，由链表结构组成的可选范围双向阻塞队列实现类，如果未指定容量，那么容量将等于 <code>Integer.MAX_VALUE</code></td> 
  </tr> 
  <tr> 
   <td><strong>Deque</strong></td> 
   <td>双端队列，允许两端都可以进行入队和出队操作的队列，其元素的逻辑结构仍是线性结构。将队列的两端分别称为前端和后端，两端都可以入队和出队。</td> 
  </tr> 
 </tbody> 
</table>

从类继承图中可以看到，LinkedList即实现了Queue，又实现了Deque，

## 3. 总结 ##

1.  Stack是后进先出，Queue是先进先出
2.  Stack是个类而Queue是个接口，但是他们都可以用LinkedList实现.

[image-20230320222620439]: https://img-blog.csdnimg.cn/img_convert/dcb37a4d1c42240a346d435f5ba60a3f.png