基础概念与简单数据结构的笔记02

• 学习内容:

  • 栈（Stack）：
    • 栈的定义、基本操作（Push、Pop、Peek）、应用场景。
  • 队列（Queue）：
    • 队列的定义、基本操作（Enqueue、Dequeue）、应用场景。
    • 双端队列（Deque）的理解和使用。
  • 字符串（String）的基本操作和常见问题，如反转、回文检查、子串查找等。

• 实践:

  • 实现栈和队列的基本操作。
  • 解决经典的字符串问题，如括号匹配、最小编辑距离等。

学习笔记

1. 栈（Stack）

栈的定义:

• 栈是一种后进先出（LIFO, Last In First Out）的数据结构。它的特点是只能在一端（称为栈顶）进行插入和删除操作。

基本操作:

• Push: 将元素压入栈顶。
• Pop: 从栈顶移除并返回元素。
• Peek/Top: 查看栈顶的元素但不移除它。
• isEmpty: 判断栈是否为空。

应用场景:

• 函数调用栈: 计算机通过栈来跟踪函数调用的顺序。
• 表达式求值: 中缀表达式转换为后缀表达式（逆波兰表达式）。
• 括号匹配: 用栈检查括号是否成对匹配。

实践:

• 实现栈的基本操作，使用数组或链表结构。

2. 队列（Queue）

队列的定义:

• 队列是一种先进先出（FIFO, First In First Out）的数据结构。元素从队列尾部进入，从队列头部移出。

基本操作:

• Enqueue: 将元素添加到队列尾部。
• Dequeue: 从队列头部移除并返回元素。
• Front/Peek: 查看队列头部的元素但不移除它。
• isEmpty: 判断队列是否为空。

应用场景:

• 任务调度: 任务按顺序执行。
• 广度优先搜索（BFS）: 在图或树的遍历中使用队列。

双端队列（Deque）:

• Deque（Double-Ended Queue）是一种允许在两端进行插入和删除操作的队列。它可以作为栈或队列使用。

Deque的基本操作:

• addFirst: 在队列头部添加元素。
• addLast: 在队列尾部添加元素。
• removeFirst: 移除并返回队列头部的元素。
• removeLast: 移除并返回队列尾部的元素。

实践:

• 实现队列和双端队列的基本操作，探讨它们在不同场景下的应用。

3. 字符串（String）

基本操作:

• 获取长度: length() 返回字符串的长度。
• 连接字符串: concat() 或 + 操作符。
• 子串查找: indexOf() 或 contains() 查找子串。
• 字符串比较: equals() 比较字符串是否相等。
• 字符串反转: 通过循环或内置函数 reverse() 实现字符串反转。

常见问题:

• 字符串反转: 使用双指针或栈。
• 回文检查: 判断一个字符串是否是回文。
• 括号匹配: 使用栈来匹配字符串中的括号是否对称。
• 子串查找: 实现 KMP 算法，优化子串查找。
• 最小编辑距离: 使用动态规划计算两个字符串之间的最小编辑操作。

实践部分

1. 实现栈的基本操作

使用数组或链表来实现栈。以下是用数组实现栈的示例代码：

class Stack {private int maxSize;private int[] stackArray;private int top;public Stack(int size) {maxSize = size;stackArray = new int[maxSize];top = -1;  // 栈顶初始化为-1，表示栈为空}public void push(int value) {if (isFull()) {System.out.println("栈已满，无法添加元素");return;}stackArray[++top] = value;}public int pop() {if (isEmpty()) {throw new RuntimeException("栈为空，无法移除元素");}return stackArray[top--];}public int peek() {if (isEmpty()) {throw new RuntimeException("栈为空，无法查看元素");}return stackArray[top];}public boolean isEmpty() {return (top == -1);}public boolean isFull() {return (top == maxSize - 1);}
}

应用:

1. 创建一个栈并进行 Push、Pop 和 Peek 操作，验证栈的行为是否正确。
2. 使用栈实现中缀表达式到后缀表达式的转换。

2. 实现队列的基本操作

用数组实现队列，并完成基本操作。

class Queue {private int maxSize;private int[] queueArray;private int front;private int rear;private int nItems;public Queue(int size) {maxSize = size;queueArray = new int[maxSize];front = 0;rear = -1;nItems = 0;}public void enqueue(int value) {if (isFull()) {System.out.println("队列已满，无法添加元素");return;}if (rear == maxSize - 1) {rear = -1;  // 处理循环}queueArray[++rear] = value;nItems++;}public int dequeue() {if (isEmpty()) {throw new RuntimeException("队列为空，无法移除元素");}int temp = queueArray[front++];if (front == maxSize) {front = 0;  // 处理循环}nItems--;return temp;}public int peek() {if (isEmpty()) {throw new RuntimeException("队列为空，无法查看元素");}return queueArray[front];}public boolean isEmpty() {return (nItems == 0);}public boolean isFull() {return (nItems == maxSize);}
}

应用:

1. 创建一个队列，执行 Enqueue 和 Dequeue 操作，检查队列的行为。
2. 使用队列实现广度优先搜索（BFS）算法遍历图或树结构。

3. 实现双端队列（Deque）的基本操作

Deque 的实现可以通过双向链表来完成。以下是使用双向链表实现双端队列的示例代码：

class Deque {private LinkedList<Integer> deque;public Deque() {deque = new LinkedList<>();}public void addFirst(int value) {deque.addFirst(value);}public void addLast(int value) {deque.addLast(value);}public int removeFirst() {if (deque.isEmpty()) {throw new RuntimeException("Deque为空，无法移除元素");}return deque.removeFirst();}public int removeLast() {if (deque.isEmpty()) {throw new RuntimeException("Deque为空，无法移除元素");}return deque.removeLast();}public int peekFirst() {if (deque.isEmpty()) {throw new RuntimeException("Deque为空，无法查看元素");}return deque.peekFirst();}public int peekLast() {if (deque.isEmpty()) {throw new RuntimeException("Deque为空，无法查看元素");}return deque.peekLast();}public boolean isEmpty() {return deque.isEmpty();}
}

应用:

1. 通过 Deque 实现一个具有先进先出（FIFO）和后进先出（LIFO）特性的队列。
2. 实现一个滑动窗口最大值问题的解决方案。

4. 解决经典的字符串问题

以下是解决括号匹配和最小编辑距离问题的示例代码：

括号匹配问题:

public boolean isValid(String s) {Stack<Character> stack = new Stack<>();for (char c : s.toCharArray()) {if (c == '(' || c == '{' || c == '[') {stack.push(c);} else {if (stack.isEmpty()) return false;char top = stack.pop();if ((c == ')' && top != '(') ||(c == '}' && top != '{') ||(c == ']' && top != '[')) {return false;}}}return stack.isEmpty();
}

最小编辑距离:

public int minDistance(String word1, String word2) {int[][] dp = new int[word1.length() + 1][word2.length() + 1];for (int i = 0; i <= word1.length(); i++) {for (int j = 0; j <= word2.length(); j++) {if (i == 0) {dp[i][j] = j;} else if (j == 0) {dp[i][j] = i;} else if (word1.charAt(i - 1) == word2.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1];} else {dp[i][j] = 1 + Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1]));}}}return dp[word1.length()][word2.length()];
}