数据结构:栈和队列学习。

数据结构2-栈和队列

1. 栈

  1. 概述

    ​ 栈也是一种线性结构,和数组相比,是数组操作的子集,规定了只能从一端添加元素,也只能从这一端取出元素,这一端称为栈顶。栈是一种后进先出(LIFO)的数据结构。

  2. 应用

    undo操作-编辑器

    系统调用栈-os

    括号匹配-编译器

  3. 实现

    1)定义栈的接口

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    package top.tobing.ds.stack;

    public interface Stack<E> {
    // 获取栈的大小
    int getSize();
    // 判断栈是否为空
    boolean isEmpty();
    // 讲一个元素压栈
    void push(E e);
    // 将栈顶元素弹出
    E pop();
    // 查看栈顶元素
    E peek();

    }

    2)利用之前编写的动态数组

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    package top.tobing.ds.stack;

    /**
    * @author Tobing
    */
    public class ArrayStack<E> implements Stack<E> {

    private Array<E> array;

    public ArrayStack() {
    this.array = new Array<>();
    }

    public ArrayStack(int capacity) {
    this.array = new Array<>(capacity);
    }

    @Override
    public int getSize() {
    return array.getSize();
    }

    @Override
    public boolean isEmpty() {
    return array.isEmpty();
    }

    // 返回栈的容量
    public int getCapacity() {
    return array.getCapacity();
    }

    @Override
    public void push(E e) {
    array.addLast(e);
    }

    @Override
    public E pop() {
    return array.removeLast();
    }

    @Override
    public E peek() {
    return array.getLast();
    }

    @Override
    public String toString() {
    StringBuilder sb = new StringBuilder();
    sb.append("Stack: ");
    sb.append("[");
    for (int i = 0; i < array.getSize(); i++) {
    sb.append(array.get(i));
    if (i != array.getSize() - 1) {
    sb.append(", ");
    }
    }
    sb.append("] top");
    return sb.toString();
    }
    }

    Array的代码查看数据结构1-数组

  4. 复杂度分析

    函数名 复杂度 其他说明
    push O(1)均摊 压栈的时候可能触发resize
    pop O(1)均摊 弹栈的时候可能触发resize
    peek O(1)
  5. Java中的栈

    Stack 类表示后进先出(LIFO)的对象堆栈。它通过五个操作对类 Vector 进行了扩展 ,允许将向量视为堆栈。它提供了通常的 pushpop 操作,以及取堆栈顶点的 peek 方法、测试堆栈是否为空的 empty 方法、在堆栈中查找项并确定到堆栈顶距离的 search 方法。

    首次创建堆栈时,它不包含项。

    Deque 接口及其实现提供了 LIFO 堆栈操作的更完整和更一致的 set,应该优先使用此 set,而非此类。例如:

    1
    Deque<Integer> stack = new ArrayDeque<Integer>();

2. 队列

  1. 概述

    ​ 队列也是一种线性结构,和数组相比,是数组操作的子集,规定了只能从一端(队尾)添加元素,也只能从另外一端(队首)取出元素,这一端称为栈顶。栈是一种先进先出(FIFO)的数据结构。

  2. 实现

    1)定义队列接口

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    package top.tobing.ds.queue;

    public interface Queue<E> {
    // 获取队列大小
    int getSize();
    // 判断是否为空队列
    boolean isEmpty();
    // 入队
    void enqueue(E e);
    // 出队
    E dequeue();
    // 查看队首元素
    E getFront();

    }

    2)队列实现1-数组队列

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    package top.tobing.ds.queue;

    /**
    * @author Tobing
    */
    public class ArrayQueue<E> implements Queue<E> {

    private Array<E> array;

    public ArrayQueue(int capacity) {
    array = new Array<>(capacity);
    }

    public ArrayQueue() {
    array = new Array<>();
    }

    @Override
    public int getSize() {
    return array.getSize();
    }

    @Override
    public boolean isEmpty() {
    return array.isEmpty();
    }

    @Override
    public void enqueue(E e) {
    array.addLast(e);
    }

    @Override
    public E dequeue() {
    return array.removeFirst();
    }

    @Override
    public E getFront() {
    return array.getFirst();
    }

    public int getCapacity() {
    return array.getCapacity();
    }

    @Override
    public String toString() {
    StringBuilder sb = new StringBuilder();
    sb.append("Queue: front [");
    for (int i = 0; i < array.getSize(); i++) {
    sb.append(array.get(i));
    if (i != array.getSize() - 1) {
    sb.append(", ");
    }
    }
    sb.append("] tail");
    return sb.toString();
    }
    }

    2)队列实现2-循环队列

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    package top.tobing.ds.queue;

    import top.tobing.ds.queue.Queue;

    import java.util.Arrays;

    /**
    * @author Tobing
    */
    public class LoopQueue<E> implements Queue<E> {

    private E[] data;
    private int front, tail;
    private int size;

    public LoopQueue(int capacity) {
    front = 0;
    tail = 0;
    size = 0;
    data = (E[]) new Object[capacity + 1];
    }

    public LoopQueue() {
    this(10);
    }

    @Override
    public int getSize() {
    return this.size;
    }

    @Override
    public boolean isEmpty() {
    return front == tail;
    }

    @Override
    public void enqueue(E e) {
    if ((tail + 1) % data.length == front) {
    resize(getCapacity() * 2);
    }
    data[tail] = e;
    size++;
    tail = (tail + 1) % data.length;
    }

    @Override
    public E dequeue() {
    if (isEmpty()) {
    throw new IllegalArgumentException("Queue is empty.");
    }
    E res = data[front];
    data[front] = null;
    front++;
    size--;
    // 懒汉式:防止复杂度闪烁
    if (size == getCapacity() / 4 && getCapacity() / 2 != 0) {
    resize(getCapacity() / 2);
    }
    return res;
    }

    // 扩容
    private void resize(int capacity) {
    E[] newData = (E[]) new Object[capacity];
    for (int i = 0; i < size; i++) {
    newData[i] = data[(i + front) % data.length];
    }
    data = newData;
    front = 0;
    tail = size;
    }

    @Override
    public E getFront() {
    return data[front];
    }

    public int getCapacity() {
    return data.length - 1;
    }

    @Override
    public String toString() {
    StringBuilder sb = new StringBuilder();
    sb.append("Queue: front [");
    for (int i = front; i != tail; i = (i + 1) % data.length) {
    sb.append(data[i]);
    if ((i + 1) % data.length != tail) {
    sb.append(", ");
    }
    }
    sb.append("] tail");
    return sb.toString();
    }
    }
  3. 复杂度分析

    1)数组复杂度

    函数 复杂度 其他说明
    enqueue O(1)均摊 可能触发resize
    dequeue O(n) 可能触发resize
    getFront O(1)
    getCapacity O(1)

    ​ 从上面的复杂度分析可知,数组方式实现的队列在每次出队之后,要将剩下的所有元素挪动一遍,导致复杂度O(n),因此我们考虑在不挪动的情况下实现队列。于是便有了循环队列。

    2)循环队列复杂度

    函数 复杂度 其他说明
    enqueue O(1)均摊 可能触发resize
    dequeue O(1)均摊 可能触发resize
    resize O(n)
    getFront O(1)
    getCapacity O(1)
    getSize O(1)
  4. 代码注意点

    ​ 数组方式实现的队列基本都是在Array上进行封装,Array之前已经分析过,因此我们不在进行赘述,我们主要讨论循环队列的实现。

    循环队列使用front和tail记录了队列的队首和队尾。

    循环队列如果全部利用所有元素,判断front==tail会有歧义,因此浪费一个元素消除歧义。

    循环队列通过判断**(tail+1)%data.length==front**来巧妙地判断队列是否满。

    循环队列入队、出队、扩容的时候都要维护front、tail、size

    循环队列遍历可以有多种方式,通过判断下标是否为tail或者循环次数是否为size可以判定循环是否可以结束。

    入队时注意判断队列是否已满(resize),维护size和tail。

    出队时注意判断队列是否已经为空,同时也要判断是否要进行resize,维护front和size。

    resize的时候注意维护front、tail和size。

  5. Java中的队列

    ​ 队列通常(但并非一定)以 FIFO(先进先出)的方式排序各个元素。不过优先级队列和 LIFO 队列(或堆栈)例外,前者根据提供的比较器或元素的自然顺序对元素进行排序,后者按 LIFO(后进先出)的方式对元素进行排序。无论使用哪种排序方式,队列的 都是调用 remove()poll() 所移除的元素。在 FIFO 队列中,所有的新元素都插入队列的末尾。其他种类的队列可能使用不同的元素放置规则。每个 Queue 实现必须指定其顺序属性。

评论