🍁1. 栈的介绍
栈是一种后进先出的数据结构，栈中的元素只能从栈顶进行插入和删除操作，类似于叠盘子，最后放上去的盘子最先拿下来。
🍁2. 栈的基本操作
- 压栈（Push）：将一个元素压入栈顶。
- 出栈（Pop）：移除并返回栈顶元素。
- 栈顶元素（Peek）：返回栈顶元素但不移除。
- 判空（IsEmpty）：检查栈是否为空。
- 栈的大小（Size）：返回栈中的元素个数。
栈的定义方法也是和ArrayList一样的，然后就是使用对象去调用栈的方法
public class Text { public static void main(String[] args) { Stack<Integer> stack1 = new Stack<>(); stack1.push(1); stack1.push(2); stack1.push(3); System.out.println(stack1.pop()); System.out.println(stack1.peek()); System.out.println(stack1.isEmpty()); System.out.println(stack1.size()); } }
🍁3. 栈的实现
首先，栈是通过数组实现的，就像之前实现的顺序表一样
public class MyStack { public int[] elem; public int usedSize; public MyStack() { this.elem = new int[10]; } }
接下来实现一些栈的基本操作
🍁3.1 push()
当1 2 3 4依次入栈时，如下图
入栈其实很简单，只需要把元素放进去，接着usedSize++就可以了，但是学习数据结构我们的思维要严谨，如果栈满了怎么办，所以还需要处理栈满的情况，栈满之后就扩容，扩容也是和之前的顺序表一样的，判断是否栈满了也很简单，只需要判断数组的长度和usedSize是否相等就可以了
public void push(int val) { if(isFull()) { this.elem = Arrays.copyOf(elem,2*elem.length); } elem[usedSize++] = val; } public boolean isFull() { return usedSize == elem.length; }
🍁3.2 pop()
遵循后进先出的原则，第一次出栈取到的元素是4
那怎么去实现这个效果呢
只需要定义一个val，把栈顶的元素取出来，赋值给val，进行返回，同时出栈之后usedSize的值要减1
之后还需要考虑栈为空的情况，如果栈为空，肯定是不能再进行出栈的操作了，此时就需要抛出一个异常
public int pop() { if(isEmpty()){ throw new EmptyStackException(); } int val = elem[usedSize - 1]; usedSize--; return val; } public boolean isEmpty() { return usedSize == 0; }
判断栈为空只需要判断usedSize是否为空
🍁3.3 peek()
peek(）是获取栈顶元素，但是不删除，这个其实更简单，只需要把下标为usedSize的元素进行返回就可以了，也不需要usedSize--
同时，还是需要处理一下栈为空的情况
public int peek() { if(usedSize == 0){ throw new EmptyStackException(); } return elem[usedSize - 1]; }
接下来把之前写的方法测试一下：
public class Text { public static void main(String[] args) { MyStack stack = new MyStack(); stack.push(1); stack.push(2); stack.push(3); System.out.print(stack.pop() + " "); System.out.print(stack.pop() + " "); System.out.print(stack.peek() + " "); } }
🍁4. 栈的使用场景
🍁4.1 链表实现栈
问题：单链表是否可以实现栈？
单链表其实是可以实现栈的，用链表实现的栈叫做链式栈
入栈：如果采用尾插法入栈，入栈的时间复杂度为O(n)，如果给出last节点为O(1),出栈的时间复杂度为O(n),因为需要遍历到末尾才能入栈
如果采用头插法，入栈和出栈的时间复杂度都是O(1)
既然单链表可以实现栈了，那么双向链表肯定也可以实现栈，不论是头插还是尾插，双链表实现的栈出栈和入栈时间复杂度都是O(1)。
而且会发现，LinkedList也定义了栈的一些基本操作，可以当作栈来使用
🍁4.2 将递归转化为循环
一个典型的例子就是逆序打印链表，我们都知道，正常情况下，单链表是不能逆序打印的，递归的调用就类似于栈，最外面的一层先被打印，也就是最末尾元素最先打印，还可以通过栈来模拟递归
//递归方式 private void printList1(MySingleList.ListNode head){ if(head!=null){ printList1(head.next); System.out.print(head.value + " "); } } //循环方式 private void printList2(MySingleList.ListNode head){ if(head == null) return; Stack<MySingleList.ListNode> s = new Stack<>(); MySingleList.ListNode cur = head; //将节点保存在栈中 while(cur!=null){ s.push(cur); cur = cur.next; } //打印栈中节点 while(!s.empty()){ System.out.print(s.pop().value + " "); } }
🍁5. 队列的介绍
队列是一种先进先出的数据结构。队列中的元素只能从队尾插入，从队首移除，类似于排队买票，最先排队的人最先买到票。
Java中的Queue是一个接口，Deque叫做双端队列
🍁6. 队列的基本操作
- 入队（offer）：将一个元素插入队尾。
- 出队（poll）：移除并返回队首元素。
- 队首元素（Peek）：返回队首元素但不移除。
- 判空（IsEmpty）：检查队列是否为空。
- 队列的大小（Size）：返回队列中的元素个数。
由于Queue是一个接口，不能直接创建对象，所以这里通过LinkedList来创建对象
public class Text { public static void main(String[] args) { //使用接口的实现类LinkedList创建对象 Queue<Integer> q = new LinkedList<>(); q.offer(1); q.offer(2); q.offer(3); //出队 System.out.println(q.poll()); //获取对头元素 System.out.println(q.peek()); } }
🍁7. 队列的实现
🍁7.1 双向链表实现队列
双向链表的话，和栈一样，入队和出队的操作时间复杂度为O(n)，因为队列是先进先出的原则，入队就采用尾插的方法，出队也就是头删的方法
public class MyQueue { //双向链表 static class ListNode { public int val; ListNode pre; ListNode next; public ListNode(int val) { this.val = val; } } ListNode first = null; ListNode last = null; public int usedSize = 0; //尾插的方法进行入队 public void offer(int val) { ListNode node = new ListNode(val); if (isEmpty()) { first = last = node; } else { last.next = node; node.pre = last; last = last.next; } usedSize++; } //头删的方法进行出队 public int poll() { if (first == null) { throw new EmptyQueueException("队列为空"); } int value = first.val; first = first.next; if(first!=null){ first.pre = null; } usedSize--; return value; } //获取队头元素 public int peek() { if (first == null) { throw new EmptyQueueException("队列为空"); } return first.val; } public boolean isEmpty() { return usedSize == 0; } }
🍁7.2 数组实现的循环队列
如果采用正常的数组来实现队列的话就会有以下的弊端，
这样出队之后，数组前面的空间就会空出来，造成空间的浪费，那如何把这些空间也利用起来呢
使用这样的循环结构，就可以解决这个问题，也就是循环队列
front和rear在同一个位置时，表示队列为空，那么队列满了也是这样的情况，此时怎么区分呢？
1.定义一个size专门判断
2.添加标记，定义一个boolean类型的flag，表示走过没有
3.空出一个空间，此时rear.next == front就表示队列已满
此时还有一个问题：对于以上的例子，怎么解决下标的问题，例如从7下标是怎么到0下标的
也就是下标最后再往后怎么表示：
公式：(数组下标 - 偏移量) % 数组长度
7 ~ 0 可以通过 （7 + 1）% 8 来表示
还有一种情况：下标最前再往前
例如 2 下标往前走到 7 下标
公式：(数组下标 + 数组长度 - 偏移量) % 数组长度
（2 + 9 - 4）% 9，加上数组长度也就是为了避免负数的情况
我们通过力扣上的这道题来实现一下：
class MyCircularQueue { public int front; public int rear; public int[] elem; public MyCircularQueue(int k) { elem = new int[k + 1];//由于有一个位置空出来了，所以要额外再多一个位置 } public boolean enQueue(int value) { if (isFull()) { return false; } elem[rear] = value; rear = (rear + 1) % elem.length; return true; } public boolean deQueue() { if (isEmpty()) { return false; } front = (front + 1) % elem.length; return true; } public int Front() { if (isEmpty()) { return -1; } else { return elem[front]; } } public int Rear() { if (isEmpty()) return -1; int index = (rear == 0 )? elem.length - 1 : rear - 1; return elem[index]; } public boolean isEmpty() { return rear == front; } public boolean isFull() { return (rear + 1) % elem.length == front; } }
🍁8. 双端队列
在Java中，Deque（双端队列）是一个接口，它扩展了Queue接口。Deque支持在两端插入和删除元素，提供了比Queue更丰富的操作集合。可以使用Deque作为栈（后进先出）、队列（先进先出）、或者两者兼有。
Java提供了几种Deque的实现，其中最常见的是ArrayDeque和LinkedList。ArrayDeque是基于数组的双端队列，它在大多数操作中都提供了更好的性能。而LinkedList也实现了Deque接口，但由于其基于链表的结构，它在添加和删除元素时可能不如ArrayDeque高效。
public class DequeDemo { public static void main(String[] args) { //线性实现 Deque<Integer> deque = new ArrayDeque<>(); deque.add(1); deque.add(2); deque.add(3); for(int i : deque){ System.out.println(i); } //链式实现 Deque<Integer> ldeque = new LinkedList<>(); ldeque.add(1); ldeque.add(1); ldeque.add(1); for(int i : ldeque){ System.out.println(i); } } }
