数据结构和算法（Java版）快速学习（栈与队列）

栈是仅允许在表尾进行插入和删除操作的线性表。我们把允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom）。栈是一种后进先出（Last In First Out）的线性表，简称（LIFO)结构。

抽象数据类型：

栈同线性表一样，一般包括插入、删除等基本操作。其基于泛型的API接口代码如下：

public interface Stack<E> {

    //栈是否为空
    boolean isEmpty();
    //栈的大小
    int size();
    //入栈
    void push(E element);
    //出栈
    E pop();
    //返回栈顶元素
    E peek();
}

　　

栈的实现通常有两种方式：

• 基于数组的实现（顺序存储）
• 基于链表的实现（链式存储）

栈的顺序存储结构

栈的顺序存储结构其实是线性表顺序存储结构的简化，我们可以简称它为「顺序栈」。其存储结构如下图：

实现代码如下：

 

栈的链式存储结构

栈的链式存储结构，简称链栈。为了操作方便，一般将栈顶放在单链表的头部。通常对于链栈来说，不需要头结点。

其存储结构如下图：

代码实现如下：

 

 

队列是只允许在一端进行插入操作，在另一端进行删除操作的线性表。它是一种基于先进先出（First In First Out，简称FIFO）策略的集合类型。允许插入的一端称为队尾，允许删除的一端称为队头。

抽象数据类型：

队列作为一种特殊的线性表，它一样包括插入、删除等基本操作。其基于泛型的API接口代码如下：

public interface Queue<E> {

    //队列是否为空
    boolean isEmpty();

    //队列的大小
    int size();

    //入队
    void enQueue(E element);

    //出队
    E deQueue();
}

　　

同样的，队列具有两种存储方式：顺序存储和链式存储。

队列的顺序存储结构

其存储结构如下图：

队列的链式存储结构

队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们简称为「链队列」。

存储结构如下图：