数据结构——栈和队列

发表于 更新于 本文字数： 584 阅读时长 ≈ 2 分钟

栈和队列是线性表的一种，只是它们是操作受限的线性表。

栈

栈是只能在表尾进行插入或删除操作的线性表，通常我们称表尾端为栈顶，表头端为栈底，它是一种先进后出的线性表，既只能在表尾端插入元素，称为入栈，也只能在表尾端删除元素，称为出栈。

1
2
3
4
5
6
7
java.lang.Object
↳     java.util.AbstractCollection<E>
   ↳     java.util.AbstractList<E>
       ↳     java.util.Vector<E>
           ↳     java.util.Stack<E>

public class Stack<E> extends Vector<E> {}

Stack的API

1
2
3
4
5
             boolean       empty()              // 栈是否为空
synchronized E             peek()               // 返回栈顶元素，不执行删除操作
synchronized E             pop()                // 返回栈顶元素，并将其从栈中删除
             E             push(E object)       // 将元素存入栈顶
synchronized int           search(Object o)     // 查找“元素o”在栈中的位置：由栈底向栈顶方向数

队列

队列刚好和栈相反，它是一种先进先出（FIFO）的线性表，只能在一端插入元素，在另一端删除元素，如下图所示，允许插入元素的一端称为队尾，允许删除元素的一端称为队头。

1
2
3
4
5
java.lang.Iterable<E>
↳     java.util.Collection<E>
   ↳     java.util.Stack<E>

public interface Queue<E> extends Collection<E>  {}

队列的实现

  • 没有实现的阻塞接口 LinkedList
  • 实现阻塞接口的
    • ArrayBlockingQueue ：一个由数组支持的有界队列。
    • LinkedBlockingQueue ：一个由链接节点支持的可选有界队列。
    • PriorityBlockingQueue ：一个由优先级堆支持的无界优先级队列。
    • DelayQueue ：一个由优先级堆支持的、基于时间的调度队列。
    • SynchronousQueue ：一个利用 BlockingQueue 接口的简单聚集（rendezvous）机制。

Queue 的 API

func return explain
add(E e) boolean 增加一个元索 如果队列已满，则抛出一个 IIIegaISlabEepeplian 异常
remove() E 移除并返回队列头部的元素 如果队列为空，则抛出一个 NoSuchElementException 异常
element() E 返回队列头部的元素 如果队列为空，则抛出一个 NoSuchElementException 异常
offer(E e) boolean 添加一个元素并返回true 如果队列已满，则返回false
poll() E 移除并返问队列头部的元素 如果队列为空，则返回null
peek() E 返回队列头部的元素 如果队列为空，则返回null
put(E e) void 添加一个元素 如果队列满，则阻塞
take() E e 移除并返回队列头部的元素 如果队列为空，则阻塞