「数据结构与算法入门」栈和队列
栈 (Stack)
栈(Stack)是一种线性的数据结构，栈中的元素遵循先入后出(FILO，First In Last Out)的原则。最早进入栈的元素位置称为栈底，最后进入站的元素位置成为栈顶。
操作栈
入栈 (push)
入栈(push)是将一个新的元素放入栈中，新元素的位置称为栈顶。
出栈 (pop)
出栈(pop)是将栈顶的元素从栈中弹出，原栈顶前一个元素位置成为新的栈顶。
代码实现
使用数组实现栈的代码如下：
import java.util.Arrays;public class MyArrayStack { private int<> arr; private int size; public MyArrayStack(int length) { arr = new int; } /** * 入栈 * * @param data 数据 */ public void push(int data) { if (size >= arr.length) arr = Arrays.copyOf(arr, 2 * arr.length); arr = data; size++; } /** * 出栈 */ public void pop() { arr = 0; size--; } /** * 输出 */ public void output() { System.out.println(Arrays.toString(arr)); } public static void main(String<> args) { final var stack = new MyArrayStack(6); stack.push(1); stack.push(2); stack.push(3); stack.push(4); stack.push(5); stack.push(6); stack.push(7); stack.push(8); stack.output(); stack.pop(); stack.output(); }} 使用链表实现栈的代码如下：
public class MyLinkedStack { private Node head; private Node last; private int size; /** * 入栈 * * @param data 数据 */ public void push(int data) { final var newNode = new Node(data); if (size == 0) { // 空链表 head = newNode; } else { newNode.prev = last; last.next = newNode; } last = newNode; size++; } /** * 出栈 */ public void pop() { final var prevNode = last.prev; prevNode.next = null; last = prevNode; size--; } /** * 输出 */ public void output() { var temp = this.head; for (int i = 0; i < size; i++) { System.out.print(temp.data + " "); temp = temp.next; } System.out.println(); } private static class Node { Node prev; int data; Node next; Node(int data) { this.data = data; } } public static void main(String<> args) { final var stack = new MyLinkedStack(); stack.push(1); stack.push(2); stack.push(3); stack.push(4); stack.push(5); stack.push(6); stack.push(7); stack.push(8); stack.output(); stack.pop(); stack.output(); }}进行入栈、出栈操作的时间复杂度均为O(1)。
队列 (Queue)
队列(Queue)也是一种线性数据结构，队列中的元素遵循先入先出(FIFO，First In First Out)的原则。队列的出口端称为队头，入口端称为队尾。
操作队列
入队 (enqueue)
入队(enqueue)是将新的元素放入队列中，新元素下一个位置成为新的队尾。
出队 (dequeue)
出队(dequeue)是将队头的元素移出队列，出队元素的后一个元素成为新的队头。
代码实现
使用数组与链表实现队列的方式有所不同。
数组实现
在不考虑扩容的情况下，队列的容量(capacity)是有限的，不断出队会使得队头前的空间逐渐失去作用。此时我们可以使用循环队列来保证队列容量的恒定，即使用已经出队的空间，来存放新的元素。
当(队尾下标 + 1) % 数组长度 = 队头下标时，表明该队列已满。（可结合单步调试进行理解）
public class MyArrayQueue { private int<> array; private int front; private int rear; public MyArrayQueue(int capacity) { this.array = new int; } /** * 入队 * * @param element 入队的元素 */ public void enQueue(int element) throws Exception { if ((rear + 1) % array.length == front) throw new Exception("队列已满"); array = element; rear = (rear + 1) % array.length; } /** * 出队 */ public void deQueue() throws Exception { if (rear == front) throw new Exception("队列已空"); front = (front + 1) % array.length; } public void output() { for (int i = front; i != rear; i = (i + 1) % array.length) { System.out.println(array); } } public static void main(String<> args) throws Exception { final var queue = new MyArrayQueue(5); queue.enQueue(1); queue.enQueue(2); queue.enQueue(3); queue.enQueue(4); queue.deQueue(); queue.deQueue(); queue.enQueue(5); queue.enQueue(6); queue.output(); }} 循环队列的意义在于，其不仅充分利用了数组的空间，还避免了数组元素移动带来的性能损失。其入队与出队的时间复杂度为O(1)
链表实现
public class MyLinkedQueue { private Node head; private Node last; private int size; /** * 入栈 * * @param data 数据 */ public void enQueue(int data) { final var newNode = new Node(data); if (size == 0) { // 空队列 head = newNode; } else { last.next = newNode; newNode.prev = last; } last = newNode; size++; } /** * 出栈 */ public void deQueue() { final var nextNode = head.next; nextNode.prev = null; head = nextNode; size--; } /** * 输出 */ public void output() { var temp = head; for (int i = 0; i < size; i++) { System.out.println(temp.data); temp = temp.next; } } private static class Node { Node prev; int data; Node next; public Node(int data) { this.data = data; } } public static void main(String<> args) { final var queue = new MyLinkedQueue(); queue.enQueue(1); queue.enQueue(2); queue.enQueue(3); queue.enQueue(4); queue.deQueue(); queue.deQueue(); queue.enQueue(5); queue.enQueue(6); queue.output(); }}