数据结构（四）链表实现队列和栈_栈和队列用链表储存

之前的队列和栈使用数组来实现，由于数组在创建时需要指定固定的容量，即数组的大小是固定的。这意味着在使用数组实现队列和栈时，需要在初始化时确定数组的大小，即使动态地扩展容量也会造成性能和内存空间的浪费。

为什么用链表实现队列和栈

链表实现队列和栈有许多好处，其中一些主要优点包括：

1. 动态大小： 链表实现的队列和栈可以动态调整大小，不需要事先指定固定的容量。这意味着它们可以根据需要动态增长或缩小，更加灵活和适应性强。

2. 内存管理： 链表中的节点是动态分配的，只有在需要时才会分配内存，而且节点可以在不连续的内存位置上存储。相比之下，使用数组实现的队列和栈需要在创建时分配连续的内存空间，这可能会导致内存碎片问题。

3. 插入和删除效率高： 链表在插入和删除操作上具有良好的性能，特别是在队列的头部插入和删除、栈的顶部插入和删除。这是因为在链表中，只需要调整指针的指向，不需要像数组那样移动大量元素。

4. 灵活性： 链表实现的队列和栈可以轻松地支持双端操作。例如，我们可以在链表的头部和尾部进行插入和删除操作，这使得实现双端队列（deque）和其他特殊数据结构变得更加容易。

5. 易于实现： 链表是一种简单的数据结构，易于实现和理解。相比之下，数组实现的队列和栈需要处理固定大小的数组和边界情况，实现起来可能会更复杂一些。

总的来说，链表实现的队列和栈具有动态大小、内存管理优势、高效的插入和删除操作、灵活性和易于实现等优点，因此在许多情况下都是一种较为理想的选择。

队列

使用链表实现了一个队列（Queue）的基本操作，包括 enqueue() 入队、dequeue() 出队、isEmpty() 判空、size() 获取大小、peek() 查看队头元素。

链表中的节点类 Node 包含数据和指向下一个节点的引用。队列的前端（front）和后端（rear）都由指针进行跟踪，以便在常数时间内进行插入和删除操作。

class Node<E> {
    E data;
    Node<E> next;

    public Node(E data) {
        this.data = data;
        this.next = null;
    }
}

public class Queue<E> {
    private Node<E> front;
    private Node<E> rear;
    private int size;

    public Queue() {
        front = null;
        rear = null;
        size = 0;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }

    public void enqueue(E data) {
        Node<E> newNode = new Node<>(data);
        if (isEmpty()) {
            front = newNode;
        } else {
            rear.next = newNode;
        }
        rear = newNode;
        size++;
    }

    public E dequeue() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        E data = front.data;
        front = front.next;
        if (front == null) {
            rear = null;
        }
        size--;
        return data;
    }

    public E peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        return front.data;
    }

    public static void main(String[] args) {
        Queue<Integer> queue = new Queue<>();
        queue.enqueue(1);
        queue.enqueue(2);
        queue.enqueue(3);

        System.out.println("Dequeued element: " + queue.dequeue());
        System.out.println("Front element: " + queue.peek());
        System.out.println("Queue size: " + queue.size());
    }
}
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

栈

使用链表实现了一个栈（Stack）的基本操作，包括 push() 入栈、pop() 出栈、isEmpty() 判空、size() 获取大小、peek() 查看栈顶元素。链表中的节点类 Node 包含数据和指向下一个节点的引用。栈的顶部由指针进行跟踪，以便在常数时间内进行插入和删除操作。

class Node<E> {
    E data;
    Node<E> next;

    public Node(E data) {
        this.data = data;
        this.next = null;
    }
}

public class Stack<E> {
    private Node<E> top;
    private int size;

    public Stack() {
        top = null;
        size = 0;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }

    public void push(E data) {
        Node<E> newNode = new Node<>(data);
        newNode.next = top;
        top = newNode;
        size++;
    }

    public E pop() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        E data = top.data;
        top = top.next;
        size--;
        return data;
    }

    public E peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        return top.data;
    }

    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);

        System.out.println("Popped element: " + stack.pop());
        System.out.println("Top element: " + stack.peek());
        System.out.println("Stack size: " + stack.size());
    }
}
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

总结

通过链表手动实现队列和栈可以帮助理解链表，队列和栈的基本原理和操作。尽管相比于标准库中的Deque实现可能存在一些局限性，作为学习数据结构的起点。通过自己动手实现，可以加深对数据结构的理解，并提升编程能力。