引言
常见的数据结构与算法题目，涵盖了数组、链表、栈、队列、二叉树、哈希表、字符串、图、排序和查找等方面的考察点。每个题目都附带有LeetCode的链接，可以点击链接了解更多题目详情
概述
| 类型 | 题目 | 考察点 | 难度 | LeetCode链接 |
| 数组 | 两数之和 | 哈希表、查找 | 简单 | LeetCode 1 |
| 链表 | 合并两个有序链表 | 链表操作、指针 | 简单 | LeetCode 21 |
| 栈 | 有效的括号 | 栈、字符串处理 | 简单 | LeetCode 20 |
| 队列 | 循环队列设计 | 队列、数组 | 中等 | LeetCode 622 |
| 二叉树 | 对称二叉树 | 二叉树递归、对称性判断 | 简单 | LeetCode 101 |
| 哈希表 | 两个数组的交集 II | 哈希表、数组 | 简单 | LeetCode 350 |
| 字符串 | 最长公共前缀 | 字符串处理、前缀判断 | 简单 | LeetCode 14 |
| 图 | 克隆图 | 图的遍历、深拷贝 | 中等 | LeetCode 133 |
| 排序 | 合并排序的数组 | 归并排序、数组操作 | 简单 | LeetCode 88 |
| 查找 | 第 K 个数 | 快速选择、二分查找 | 中等 | LeetCode 215 |
两数之和（LeetCode 1,Easy）
- 标签：哈希表|数组
题目
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答案。 示例 1： 输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。 示例 2： 输入：nums = [3,2,4], target = 6 输出：[1,2] 示例 3： 输入：nums = [3,3], target = 6 输出：[0,1] 提示： 2 <= nums.length <= 104 -109 <= nums[i] <= 109 -109 <= target <= 109 只会存在一个有效答案
原题：LeetCode 1
思路及实现
方式一：暴力解法（不推荐）
思路
最容易想到的方法是枚举数组中的每一个数 x，寻找数组中是否存在 target - x。
当我们使用遍历整个数组的方式寻找 target - x 时，需要注意到每一个位于 x 之前的元素都已经和 x 匹配过，因此不需要再进行匹配。而每一个元素不能被使用两次，所以我们只需要在 x 后面的元素中寻找 target - x。
代码实现
JAVA版本
import java.util.HashMap; public int[] twoSum(int[] nums, int target) { int n = nums.length; for (int i = 0; i < nums.length; i++) { // 遍历数组，从第一个元素开始 for (int j = i + 1; j < nums.length; j++) { // 在当前元素后面的元素中查找与目标值相加等于target的元素 if (nums[i] + nums[j] == target) { // 如果找到了符合条件的元素对 return new int[]{i, j}; // 返回这两个元素的下标 } } } return new int[0]; // 如果没有找到符合条件的元素对，则返回空数组 }
C语言版本
#include <stdio.h> #include <stdlib.h> int* twoSum(int* nums, int numsSize, int target, int* returnSize) { int* result = (int*)malloc(2 * sizeof(int)); // 分配保存结果的内存空间 *returnSize = 0; // 初始化返回结果数组的大小为0，表示没有找到满足条件的元素对 for (int i = 0; i < numsSize; i++) { // 外层循环遍历数组中的每个元素 for (int j = i + 1; j < numsSize; j++) { // 内层循环遍历当前元素后面的每个元素 if (nums[i] + nums[j] == target) { // 检查两个元素的和是否等于目标值 result[0] = i; // 将符合条件的第一个元素的下标存入结果数组的第一个位置 result[1] = j; // 将符合条件的第二个元素的下标存入结果数组的第二个位置 *returnSize = 2; // 更新返回结果数组的大小为2 return result; // 返回结果数组 } } } return result; // 返回结果数组，如果没有找到满足条件的元素对，数组中的元素值均为0 // 注意：需要在适当的时候释放result指向的动态分配内存，以避免内存泄漏 }
python3版本
from typing import List def twoSum(nums: List[int], target: int) -> List[int]: result = [] # 用于存储结果的列表 n = len(nums) for i in range(n): # 外层循环遍历列表中的每个元素 for j in range(i+1, n): # 内层循环遍历当前元素后面的每个元素 if nums[i] + nums[j] == target: # 检查两个元素的和是否等于目标值 result.append(i) # 将符合条件的第一个元素的下标添加到结果列表中 result.append(j) # 将符合条件的第二个元素的下标添加到结果列表中 return result # 返回结果列表 return result # 如果没有找到满足条件的元素对，返回空列表
复杂度分析：
- 时间复杂度分析：O(n^2)，其中n为数组nums的长度。这是由于代码使用了两层循环来遍历数组。外层循环将执行n次，而内层循环则将执行(n-1)次、(n-2)次、…、2次、1次，总的执行次数为n * (n-1) / 2，即O(n^2)。
- 空间复杂度分析：O(1)，即常数级别的空间复杂度。因为代码只使用了常数个额外变量来存储元素的下标和存储结果的数组。
方式二：哈希表（推荐）
思路
注意到方法一的时间复杂度较高的原因是寻找 target - x 的时间复杂度过高。因此，我们需要一种更优秀的方法，能够快速寻找数组中是否存在目标元素。如果存在，我们需要找出它的索引。
使用哈希表，可以将寻找 target - x 的时间复杂度降低到从 O(N) 降低到 O(1)。
这样我们创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。
下图以[2,7,11,15]为例
代码实现
JAVA版本
import java.util.HashMap; class Solution { public int[] twoSum(int[] nums, int target) { //key为当前值，value为当前值的位置 HashMap<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { int complement = target - nums[i]; // 计算差值，即目标值与当前元素的差值 if (map.containsKey(complement)) { return new int[]{map.get(complement), i}; // 返回HashMap中保存的差值元素的下标和当前元素的下标 } map.put(nums[i], i); // 将当前元素添加到HashMap中 } return new int[0]; // 如果没有找到满足条件的元素对，返回空数组 } }
C语言版本
#include <stdio.h> #include <stdlib.h> int* twoSum(int* nums, int numsSize, int target, int* returnSize) { int* result = (int*)malloc(2 * sizeof(int)); *returnSize = 0; // 创建哈希表 int hashtable[20001] = {0}; for (int i = 0; i < numsSize; ++i) { int complement = target - nums[i]; // 计算差值，即目标值与当前元素的差值 // 检查哈希表中是否存在差值 if (complement >= -10000 && complement <= 10000 && hashtable[complement + 10000] != 0) { result[0] = hashtable[complement + 10000] - 1; // 返回哈希表中保存的差值元素的下标 result[1] = i; // 返回当前元素的下标 *returnSize = 2; // 更新返回结果数组的大小为2 return result; } // 将当前元素添加到哈希表中 hashtable[nums[i] + 10000] = i + 1; } return result; }
python3版本
from typing import List from collections import defaultdict class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: hashtable = defaultdict(int) # 使用defaultdict来容纳哈希表 for i in range(len(nums)): complement = target - nums[i] # 计算差值，即目标值与当前元素的差值 if complement in hashtable: return [hashtable[complement], i] # 返回哈希表中保存的差值元素的下标和当前元素的下标 hashtable[nums[i]] = i # 将当前元素添加到哈希表中 return [] # 如果没有找到满足条件的元素对，返回空列表
复杂度分析：
- 时间复杂度：O(N)，其中 N 是数组中的元素数量。对于每一个元素 x，我们可以 O(1) 地寻找 target - x。
- 空间复杂度：O(N)，其中 N 是数组中的元素数量。主要为哈希表的开销。
合并两个有序链表（LeetCode 21,Easy）
- 标签：哈希表|数组
题目
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
> 输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = [] 输出：[]
示例 3：
输入：l1 = [], l2 = [0] 输出：[0] 提示：
两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100 l1 和 l2 均按 非递减顺序 排列
原题： LeetCode 21
思路及实现
方式一：迭代（推荐）
思路
我们可以用迭代的方法来实现上述算法。当 l1 和 l2 都不是空链表时，判断 l1 和 l2 哪一个链表的头节点的值更小，将较小值的节点添加到结果里，当一个节点被添加到结果里之后，将对应链表中的节点向后移一位
代码实现
Java版本
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int val) { * this.val = val; * } * } */ class Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { ListNode node = new ListNode(-1); // 创建一个临时节点作为结果链表的头节点 ListNode cur = node; while (list1 != null && list2 != null) { if (list1.val < list2.val) { cur.next = list1; // 将较小节点连接到结果链表 list1 = list1.next; // 移动指针到下一个节点 } else { cur.next = list2; list2 = list2.next; } cur = cur.next; // 移动当前节点指针到下一个节点 } if (list1 != null) { cur.next = list1; // 将剩下的节点连接到结果链表 } if (list2 != null) { cur.next = list2; } return node.next; // 返回结果链表的头节点 } }
说明：
创建了一个临时节点作为结果链表的头节点。然后使用cur引用指向当前节点，通过遍历两个链表，比较节点的值，将较小节点连接到结果链表中，并将指针移向下一个节点。最后，将剩下的节点连接到结果链表的末尾。
需要注意的是，最后返回的是结果链表的头节点
C语言版本
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode)); node->val = -1; // 创建一个临时节点作为结果链表的头节点 node->next = NULL; struct ListNode* cur = node; while (list1 != NULL && list2 != NULL) { if (list1->val < list2->val) { cur->next = list1; // 将较小节点连接到结果链表 list1 = list1->next; // 移动指针到下一个节点 } else { cur->next = list2; list2 = list2->next; } cur = cur->next; // 移动当前节点指针到下一个节点 } if (list1 != NULL) { cur->next = list1; // 将剩下的节点连接到结果链表 } if (list2 != NULL) { cur->next = list2; } struct ListNode* result = node->next; // 指向结果链表的头节点 free(node); // 释放临时节点的内存 return result; }
说明： 在C语言中使用了头节点，并使用了指针操作来完成。
在算法中，我们创建了一个临时节点作为结果链表的头节点。然后使用cur指针指向当前节点，通过遍历两个链表，比较节点的值，将较小节点连接到结果链表中，并将指针移向下一个节点。最后，将剩下的节点连接到结果链表的末尾。
需要注意的是，最后返回的是结果链表的头节点，使用一个临时节点来保存结果链表的头节点可以简化操作。
在末尾，我们释放了临时节点的内存，以防止内存泄漏。
Python3版本
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def mergeTwoLists(self, list1: ListNode, list2: ListNode) -> ListNode: node = ListNode(-1) # 创建临时节点作为结果链表的头节点 cur = node while list1 and list2: if list1.val < list2.val: cur.next = list1 # 将较小节点连接到结果链表 list1 = list1.next else: cur.next = list2 list2 = list2.next cur = cur.next cur.next = list1 or list2 # 将剩下的节点连接到结果链表 return node.next # 返回结果链表的头节点
说明： Python 三元表达式写法 A if x else B ，代表当 x=True 时执行 A ，否则执行 B 。
复杂度分析
- 时间复杂度：O(M+N)，M, N分别标识list1和list2的长度
- 空间复杂度: O(1), 节点引用cur，常量级的额外空间
方式二：递归（不推荐）
思路
我们可以如下递归地定义两个链表里的 merge 操作（忽略边界情况，比如空链表等）：
情况一 ：list1[0]<list2[0]，则 list1[0]+merge(list1[1:],list2) 其他情况 ：list2[0]+merge(list1,list2[1:])
也就是说，两个链表头部值较小的一个节点与剩下元素的 merge 操作结果合并。
我们直接将以上递归过程建模，同时需要考虑边界情况。
如果 l1 或者 l2 一开始就是空链表 ，那么没有任何操作需要合并，所以我们只需要返回非空链表。否则，我们要判断 l1 和 l2 哪一个链表的头节点的值更小，然后递归地决定下一个添加到结果里的节点。如果两个链表有一个为空，递归结束
代码实现
Java版本
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { // 如果l1为空，则直接返回l2作为合并后的链表 if (l1 == null) { return l2; } // 如果l2为空，则直接返回l1作为合并后的链表 else if (l2 == null) { return l1; } // 如果l1的值小于l2的值 else if (l1.val < l2.val) { // 将l1的下一个节点与l2递归地合并 l1.next = mergeTwoLists(l1.next, l2); return l1; // 返回合并后的链表头节点l1 } // 如果l2的值小于等于l1的值 else { // 将l2的下一个节点与l1递归地合并 l2.next = mergeTwoLists(l1, l2.next); return l2; // 返回合并后的链表头节点l2 } } }
说明：
解法提供了递归方式来合并两个有序链表的操作。在算法中，首先处理特殊情况：如果l1为空，则直接返回l2作为合并后的链表；如果l2为空，则直接返回l1作为合并后的链表。接下来，判断l1和l2的值大小关系：如果l1的值小于l2的值，将l1的下一个节点与l2递归地合并，将合并结果作为l1的下一个节点，并返回l1作为合并后的链表头节点；如果l2的值小于等于l1的值，将l2的下一个节点与l1递归地合并，将合并结果作为l2的下一个节点，并返回l2作为合并后的链表头节点。最终，返回合并后的链表头节点。
C语言版本
#include <stdio.h> #include <stdlib.h> struct ListNode { int val; struct ListNode *next; }; struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) { // 如果l1为空，则直接返回l2作为合并后的链表 if (l1 == NULL) { return l2; } // 如果l2为空，则直接返回l1作为合并后的链表 else if (l2 == NULL) { return l1; } // 如果l1的值小于l2的值 else if (l1->val < l2->val) { // 将l1的下一个节点与l2递归地合并 l1->next = mergeTwoLists(l1->next, l2); return l1; // 返回合并后的链表头节点l1 } // 如果l2的值小于等于l1的值 else { // 将l2的下一个节点与l1递归地合并 l2->next = mergeTwoLists(l1, l2->next); return l2; // 返回合并后的链表头节点l2 } }
说明：
在算法中，首先处理特殊情况：如果l1为空，则直接返回l2作为合并后的链表；如果l2为空，则直接返回l1作为合并后的链表。接下来，判断l1和l2的值的大小关系：如果l1的值小于l2的值，将l1的下一个节点与l2递归地合并，将合并结果作为l1的下一个节点，并返回l1作为合并后的链表头节点；如果l2的值小于等于l1的值，将l2的下一个节点与l1递归地合并，将合并结果作为l2的下一个节点，并返回l2作为合并后的链表头节点。最终，返回合并后的链表头节点。
Python3版本
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode: if not l1: # 如果l1为空，则直接返回l2 return l2 elif not l2: # 如果l2为空，则直接返回l1 return l1 elif l1.val < l2.val: # 如果l1的值小于l2的值 l1.next = self.mergeTwoLists(l1.next, l2) # 递归地将l1的下一个节点与l2合并 return l1 else: l2.next = self.mergeTwoLists(l1, l2.next) # 递归地将l2的下一个节点与l1合并 return l2
复杂度分析
- 时间复杂度：O(n+m)，其中 n 和 m 分别为两个链表的长度。因为每次调用递归都会去掉 l1 或者 l2 的头节点（直到至少有一个链表为空），函数 mergeTwoList 至多只会递归调用每个节点一次。因此，时间复杂度取决于合并后的链表长度，即 O(n+m)。
- 空间复杂度：O(n+m)，其中 n 和 m 分别为两个链表的长度。递归调用 mergeTwoLists 函数时需要消耗栈空间，栈空间的大小取决于递归调用的深度。结束递归调用时 mergeTwoLists 函数最多调用 n+m 次，因此空间复杂度为 O(n+m)。
小结
递归和迭代都可以用来解决将两个有序链表合并的问题。下面对比一下递归和迭代的解法特点：
| 递归解法 | 迭代解法 | |
| 优点 | 简洁，易于理解和实现 | 不涉及函数递归调用，避免递归开销和栈溢出问题 |
| 缺点 | 可能产生多个函数调用，涉及函数调用开销和栈溢出问题 | 需要使用额外变量保存当前节点，增加代码复杂性 |
| 时间复杂度 | O(m+n)，其中m和n分别是两个链表的长度 | O(m+n)，其中m和n分别是两个链表的长度 |
| 空间复杂度 | O(m+n)，其中m和n分别是两个链表的长度 | O(1) |
在实际应用中，如果链表较长，特别是超过系统栈的容量，采用迭代解法更为安全。而对于简短的链表，递归解法更为简洁和直观。
有效的括号（LeetCode 20,Easy）
- 标签：栈、字符串处理
题目
给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = “()” 输出：true
示例 2：
输入：s = “()[]{}” 输出：true
示例 3：
输入：s = “(]” 输出：false
提示：
1 <= s.length <= 104 s 仅由括号 ‘()[]{}’ 组成
思路及实现
方式一：栈（推荐）
思路
判断括号的有效性可以使用「栈」这一数据结构来解决。
代码实现
Java版本
import java.util.Stack; // leetcode submit region begin(Prohibit modification and deletion) class Solution { public boolean isValid(String s) { Stack<Character> stack = new Stack<>(); // 创建一个栈用于存储左括号字符 for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (c == '(' || c == '[' || c == '{') { stack.push(c); // 如果是左括号字符，将其压入栈中 } else { if (stack.isEmpty()) { return false; // 如果栈为空，说明缺少左括号，返回false } char top = stack.pop(); // 弹出栈顶元素 if (c == ')' && top != '(') { return false; // 如果当前字符是右括号且与栈顶元素不匹配，返回false } if (c == ']' && top != '[') { return false; } if (c == '}' && top != '{') { return false; } } } return stack.isEmpty(); // 最后判断栈是否为空，如果为空说明每个左括号都有匹配的右括号，则返回true，否则返回false } } // leetcode submit region end(Prohibit modification and deletion)
说明：
使用栈来判断给定的字符串中的括号是否匹配。先创建一个空栈，然后遍历字符串中的每个字符。如果是左括号字符，则压入栈中；如果是右括号字符，则与栈顶元素进行匹配。匹配成功则继续遍历，匹配失败则返回false。最后判断栈是否为空，如果为空则说明所有的括号都被匹配，返回true；否则，说明还有未匹配的括号，返回false
C++版本(由于C语言需要自己实现栈较为繁琐，此处使用C++)
#include <iostream> #include <stack> #include <string> using namespace std; bool isValid(string s) { stack<char> stk; // 创建一个栈用于存储左括号字符 for (char c : s) { if (c == '(' || c == '[' || c == '{') { stk.push(c); // 如果是左括号字符，将其压入栈中 } else { if (stk.empty()) { return false; // 如果栈为空，说明缺少左括号，返回false } char top = stk.top(); /* 获取栈顶元素 */ stk.pop(); // 弹出栈顶元素 if (c == ')' && top != '(') { return false; // 如果当前字符是右括号且与栈顶元素不匹配，返回false } if (c == ']' && top != '[') { return false; } if (c == '}' && top != '{') { return false; } } } return stk.empty(); // 最后判断栈是否为空，如果为空说明每个左括号都有匹配的右括号，则返回true，否则返回false }
说明：
使用C++的标准库来实现栈，判断给定的字符串中的括号是否匹配。首先创建一个stack用于存储左括号字符。然后遍历字符串中的每个字符，如果是左括号字符，则将其压入栈中；如果是右括号字符，则与栈顶元素进行匹配。匹配成功则继续遍历，匹配失败则返回false。最后判断栈是否为空，如果为空则说明所有的括号都被匹配，返回true；否则，说明还有未匹配的括号，返回false。
Python3版本
class Solution: def isValid(self, s: str) -> bool: stack = [] # 创建一个栈用于存储左括号字符 brackets = {'(': ')', '[': ']', '{': '}'} for char in s: if char in brackets.keys(): # 如果是左括号字符，将其压入栈中 stack.append(char) elif char in brackets.values(): # 如果是右括号字符 if not stack: # 如果栈为空，说明缺少左括号，返回False return False top = stack.pop() # 弹出栈顶元素 if char != brackets[top]: # 如果当前字符与栈顶元素不匹配，返回False return False return len(stack) == 0 # 判断栈是否为空，为空说明每个左括号都有匹配的右括号
说明：
创建一个列表作为栈来判断给定的字符串中的括号是否匹配。首先定义了一个字典brackets，用来存储左括号和右括号的对应关系。然后遍历字符串中的每个字符，如果是左括号字符，则将其压入栈中；如果是右括号字符，则和栈顶元素进行匹配。匹配成功则继续遍历，匹配失败则返回False。最后判断栈是否为空，如果为空则说明所有的括号都被匹配，返回True；否则，说明还有未匹配的括号，返回False
复杂度分析
- 时间复杂度：O(n)，其中 n 是字符串 s 的长度。
- 空间复杂度：O(n)，其中n为字符串的长度。在最坏情况下，所有的字符都是左括号，需要将其全部入栈，占用了O(n) 的空间。
这个算法具有线性时间复杂度和线性空间复杂度。
循环队列设计（LeetCode 622,Medium）
- 标签：队列、数组
题目
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。 循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。 你的实现应该支持如下操作： MyCircularQueue(k): 构造器，设置队列长度为 k 。 Front: 从队首获取元素。如果队列为空，返回 -1 。 Rear: 获取队尾元素。如果队列为空，返回 -1 。 enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。 deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。 isEmpty(): 检查循环队列是否为空。 isFull(): 检查循环队列是否已满。 示例： MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3 circularQueue.enQueue(1); // 返回 true circularQueue.enQueue(2); // 返回 true circularQueue.enQueue(3); // 返回 true circularQueue.enQueue(4); // 返回 false，队列已满 circularQueue.Rear(); // 返回 3 circularQueue.isFull(); // 返回 true circularQueue.deQueue(); // 返回 true circularQueue.enQueue(4); // 返回 true circularQueue.Rear(); // 返回 4 提示： 所有的值都在 0 至 1000 的范围内； 操作数将在 1 至 1000 的范围内； 请不要使用内置的队列库。 原题：[LeetCode 622](https://leetcode-cn.com/problems/design-circular-queue/)
思路及实现
方式一：数组（不推荐）
思路
我们可以通过一个数组进行模拟，通过操作数组的索引构建一个虚拟的首尾相连的环。在循环队列结构中，设置一个队尾 rear 与队首 front，且大小固定，结构如下图所示:
在循环队列中，当队列为空，可知 front=rear；
而当所有队列空间全占满时，也有 front=rear。
为了区别这两种情况，假设队列使用的数组有 capacity 个存储空间，则此时规定循环队列最多只能有capacity−1 个队列元素，当循环队列中只剩下一个空存储单元时，则表示队列已满。
根据以上可知，队列判空的条件是 front=rear，而队列判满的条件是 front=(rear+1)modcapacity。
对于一个固定大小的数组，只要知道队尾 rear 与队首 front，即可计算出队列当前的长度：(rear−front+capacity)modcapacity
循环队列的属性如下:
- elements：一个固定大小的数组，用于保存循环队列的元素。
- capacity：循环队列的容量，即队列中最多可以容纳的元素数量。
- front：队列首元素对应的数组的索引。
- rear：队列尾元素对应的索引的下一个索引。
循环队列的接口方法如下： MyCircularQueue(int k): 初始化队列，同时base 数组的空间初始化大小为 k+1。front,rear 全部初始化为 0。 enQueue(int value)：在队列的尾部插入一个元素，并同时将队尾的索引 rear 更新为 (rear+1)modcapacity。 deQueue()：从队首取出一个元素，并同时将队首的索引 front 更新为 (front+1)modcapacity。 Front()：返回队首的元素，需要检测队列是否为空。 Rear()：返回队尾的元素，需要检测队列是否为空。 isEmpty()：检测队列是否为空，根据之前的定义只需判断 rear 是否等于 front。 isFull()：检测队列是否已满，根据之前的定义只需判断 front 是否等于 (rear+1)modcapacity。
代码实现
Java版本
class MyCircularQueue { private int front; // 队头指针 private int rear; // 队尾指针 private int capacity; // 队列容量 private int[] elements; // 存储队列元素的数组 public MyCircularQueue(int k) { capacity = k + 1; // 设置队列容量，需要额外留一个空位用于判断队满的条件 elements = new int[capacity]; // 创建存储队列元素的数组 rear = front = 0; // 初始化队头和队尾指针 } public boolean enQueue(int value) { if (isFull()) { return false; // 如果队列已满，无法入队，返回false } elements[rear] = value; // 将元素放入队尾 rear = (rear + 1) % capacity; // 队尾指针后移一位，通过取模实现循环 return true; } public boolean deQueue() { if (isEmpty()) { return false; // 如果队列为空，无法出队，返回false } front = (front + 1) % capacity; // 队头指针后移一位，通过取模实现循环 return true; } public int Front() { if (isEmpty()) { return -1; // 如果队列为空，返回-1 } return elements[front]; // 返回队头元素 } public int Rear() { if (isEmpty()) { return -1; // 如果队列为空，返回-1 } return elements[(rear - 1 + capacity) % capacity]; // 返回队尾元素，通过(rear-1+capacity)%capacity实现循环 } public boolean isEmpty() { return rear == front; // 队头指针等于队尾指针时，队列为空 } public boolean isFull() { return (rear + 1) % capacity == front; // 队头指针的下一个位置等于队尾指针时，队列为满 } }
说明：
代码实现了一个循环队列类MyCircularQueue，使用数组来存储队列的元素，并使用front和rear两个指针来指示队头和队尾的位置。在构造方法MyCircularQueue中，初始化capacity为k+1，由于要留出一个空位来判断队满的条件，因此数组的长度为capacity。在入队方法enQueue中，首先判断队列是否已满，如果已满则无法入队，返回false；否则将元素放入队尾，并将rear指针循环到下一个位置。在出队方法deQueue中，首先判断队列是否为空，如果为空则无法出队，返回false；否则将front指针循环到下一个位置。在Front方法中，如果队列为空则返回-1，否则返回front指针所指位置的元素。在Rear方法中，如果队列为空则返回-1，否则返回rear指针的前一个位置（通过(rear-1+capacity)%capacity来实现循环）。isEmpty方法用于判断队列是否为空，即判断rear与front是否相等。isFull方法用于判断队列是否已满，即判断(rear+1)%capacity是否等于front。
这个代码中使用成员变量来存储队列的状态和数据，方法通过操作这些成员变量来实现对队列的操作。方法的返回值为布尔型，用于表示操作是否成功，而不是抛出异常来处理异常情况。
C语言版本
typedef struct { int front; // 队头指针 int rear; // 队尾指针 int capacity; // 队列容量 int* elements; // 存储队列元素的数组 } MyCircularQueue; MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); // 分配队列结构体的内存空间 obj->capacity = k + 1; // 设置队列容量，需要额外留一个空位用于判断队满的条件 obj->front = obj->rear = 0; // 初始化队头和队尾指针为0 obj->elements = (int*)malloc(sizeof(int) * obj->capacity); // 创建存储队列元素的数组 return obj; } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if ((obj->rear + 1) % obj->capacity == obj->front) { return false; // 如果队列已满，无法入队，返回false } obj->elements[obj->rear] = value; // 将元素放入队尾 obj->rear = (obj->rear + 1) % obj->capacity; // 队尾指针后移一位，通过取模实现循环 return true; } bool myCircularQueueDeQueue(MyCircularQueue* obj) { if (obj->rear == obj->front) { return false; // 如果队列为空，无法出队，返回false } obj->front = (obj->front + 1) % obj->capacity; // 队头指针后移一位，通过取模实现循环 return true; } int myCircularQueueFront(MyCircularQueue* obj) { if (obj->rear == obj->front) { return -1; // 如果队列为空，返回-1 } return obj->elements[obj->front]; // 返回队头元素 } int myCircularQueueRear(MyCircularQueue* obj) { if (obj->rear == obj->front) { return -1; // 如果队列为空，返回-1 } return obj->elements[(obj->rear - 1 + obj->capacity) % obj->capacity]; // 返回队尾元素，通过(rear-1+capacity)%capacity实现循环 } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->rear == obj->front; // 队头指针等于队尾指针时，队列为空 } bool myCircularQueueIsFull(MyCircularQueue* obj) { return (obj->rear + 1) % obj->capacity == obj->front; // 队头指针的下一个位置等于队尾指针时，队列为满 } void myCircularQueueFree(MyCircularQueue* obj) { free(obj->elements); // 释放存储队列元素的数组内存空间 free(obj); // 释放队列结构体内存空间 }
说明：使用结构体MyCircularQueue来存储队列的状态和数据。结构体中包括front和rear两个指针，capacity队列容量，以及存储队列元素的elements数组。
Python3版本
class MyCircularQueue: def __init__(self, k: int): self.front = self.rear = 0 # 初始化队头和队尾指针 self.elements = [0] * (k + 1) # 创建一个长度为k+1的数组来存储元素，留出一个空位作为判断队满的条件 def enQueue(self, value: int) -> bool: if self.isFull(): # 如果队满，无法入队，返回False return False self.elements[self.rear] = value # 将元素放入队尾 self.rear = (self.rear + 1) % len(self.elements) # 队尾指针后移一位 return True def deQueue(self) -> bool: if self.isEmpty(): # 如果队空，无法出队，返回False return False self.front = (self.front + 1) % len(self.elements) # 队头指针后移一位 return True def Front(self) -> int: return -1 if self.isEmpty() else self.elements[self.front] # 如果队空，返回-1；否则返回队头元素 def Rear(self) -> int: return -1 if self.isEmpty() else self.elements[(self.rear - 1) % len(self.elements)] # 如果队空，返回-1；否则返回队尾元素 def isEmpty(self) -> bool: return self.rear == self.front # 队头指针等于队尾指针时，队列为空 def isFull(self) -> bool: return (self.rear + 1) % len(self.elements) == self.front # 队头指针的下一位等于队尾指针时，队列为满
说明：
代码实现了一个循环队列类MyCircularQueue，使用一个数组来存储队列元素，并用队头和队尾指针来指示队列的位置。在__init__方法中，初始化队头和队尾指针，并创建一个长度为k+1的数组来存储元素，其中k为传入的参数。在isFull方法中，通过判断队头指针的下一位是否等于队尾指针来判断队列是否为满。在isEmpty方法中，通过判断队头指针是否等于队尾指针来判断队列是否为空。enQueue方法实现元素的入队操作，先判断队列是否为满，如果为满则无法入队，返回False；否则将元素放入队尾，并将队尾指针后移一位。deQueue方法实现元素的出队操作，先判断队列是否为空，如果为空则无法出队，返回False；否则将队头指针后移一位。Front方法返回队列的队头元素，如果队列为空则返回-1。Rear方法返回队列的队尾元素，如果队列为空则返回-1。
复杂度分析
- 时间复杂度：初始化和每项操作的时间复杂度均为 O(1)。
- 空间复杂度：O(k)，其中 k 为给定的队列元素数目。
方式二：链表（推荐）
思路
我们同样可以用链表实现队列，用链表实现队列则较为简单，因为链表可以在 O(1) 时间复杂度完成插入与删除。入队列时，将新的元素插入到链表的尾部；出队列时，将链表的头节点返回，并将头节点指向下一个节点。
循环队列的属性如下:
- head：链表的头节点，队列的头节点。
- tail：链表的尾节点，队列的尾节点。
- capacity：队列的容量，即队列可以存储的最大元素数量。
- size：队列当前的元素的数量。
代码实现
Java
class MyCircularQueue { private ListNode head; // 队头节点 private ListNode tail; // 队尾节点 private int capacity; // 队列容量 private int size; // 当前队列的元素个数 public MyCircularQueue(int k) { capacity = k; size = 0; } public boolean enQueue(int value) { if (isFull()) { return false; // 如果队列已满，无法入队，返回false } ListNode node = new ListNode(value); if (head == null) { head = tail = node; // 如果队列为空，设置头部和尾部节点为新节点 } else { tail.next = node; // 将新节点添加到尾部 tail = node; // 更新尾部节点 } size++; // 元素个数加1 return true; } public boolean deQueue() { if (isEmpty()) { return false; // 如果队列为空，无法出队，返回false } head = head.next; // 将头部节点后移一位，实现出队操作 size--; // 元素个数减1 return true; } public int Front() { if (isEmpty()) { return -1; // 如果队列为空，返回-1 } return head.val; // 返回头部节点的值 } public int Rear() { if (isEmpty()) { return -1; // 如果队列为空，返回-1 } return tail.val; // 返回尾部节点的值 } public boolean isEmpty() { return size == 0; // 如果元素个数为0，队列为空 } public boolean isFull() { return size == capacity; // 如果元素个数等于队列容量，队列已满 } } class ListNode { int val; ListNode next; public ListNode(int val) { this.val = val; } }
说明：
MyCircularQueue 类实现了一个循环队列，使用了链表来存储队列的元素。
在构造方法 MyCircularQueue 中，初始化了队头节点 head 和队尾节点 tail 为 null，队列的容量 capacity
为传入的参数 k，当前队列元素个数 size 初始化为 0。
enQueue 方法用于入队操作，首先判断队列是否已满，如果已满，则无法入队，返回 false。创建一个新的节点
node，如果队列为空，则将 head 和 tail 指针指向新节点；否则，将新节点添加到尾部，并更新 tail 指向新节点。元素个数
size 加 1，并返回 true 表示入队成功。
C语言
typedef struct { struct ListNode *head; // 队头指针 struct ListNode *tail; // 队尾指针 int capacity; // 队列容量 int size; // 当前队列的元素个数 } MyCircularQueue; MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue *obj = (MyCircularQueue *)malloc(sizeof(MyCircularQueue)); // 创建队列结构体并分配内存空间 obj->capacity = k; // 设置队列容量 obj->size = 0; // 当前队列元素个数为0 obj->head = obj->tail = NULL; // 初始化队头和队尾指针为 NULL return obj; } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if (obj->size >= obj->capacity) { return false; // 如果队列已满，无法入队，返回 false } struct ListNode *node = (struct ListNode *)malloc(sizeof(struct ListNode)); // 创建新节点并分配内存空间 node->val = value; // 设置节点的值 node->next = NULL; // 初始化节点的下一个指针为 NULL if (!obj->head) { obj->head = obj->tail = node; // 如果队列为空，设置头部和尾部指针为新节点 } else { obj->tail->next = node; // 将新节点添加到尾部 obj->tail = node; // 更新尾部指针 } obj->size++; // 当前队列元素个数加1 return true; } bool myCircularQueueDeQueue(MyCircularQueue* obj) { if (obj->size == 0) { return false; // 如果队列为空，无法出队，返回 false } struct ListNode *node = obj->head; // 保存当前头部节点 obj->head = obj->head->next; // 头部指针后移一位，实现出队操作 obj->size--; // 当前队列元素个数减1 free(node); // 释放出队节点的内存 return true; } int myCircularQueueFront(MyCircularQueue* obj) { if (obj->size == 0) { return -1; // 如果队列为空，返回 -1 } return obj->head->val; // 返回头部节点的值 } int myCircularQueueRear(MyCircularQueue* obj) { if (obj->size == 0) { return -1; // 如果队列为空，返回 -1 } return obj->tail->val; // 返回尾部节点的值 } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->size == 0; // 如果当前队列元素个数为0，队列为空 } bool myCircularQueueIsFull(MyCircularQueue* obj) { return obj->size == obj->capacity; // 如果当前队列元素个数等于队列容量，队列已满 } void myCircularQueueFree(MyCircularQueue* obj) { for (struct ListNode *curr = obj->head; curr;) { // 遍历整个队列，从头部开始 struct ListNode *node = curr; // 保存当前节点 curr = curr->next; // 移动到下一个节点 free(node); // 释放当前节点的内存 } free(obj); // 释放队列结构体的内存 }
说明：
使用了结构体来存储队列的状态和数据。在 myCircularQueueCreate 函数中，初始化了队列的容量 capacity 为传入的参数 k，当前队列元素个数 size为 0，并将队头 head 和队尾 tail 指针初始化为 NULL。
Python3
class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next class MyCircularQueue: def __init__(self, k: int): self.head = self.tail = None # 队头和队尾指针，用于指向队列的头部和尾部 self.capacity = k # 队列容量 self.size = 0 # 当前队列中的元素个数 def enQueue(self, value: int) -> bool: if self.isFull(): # 如果队列已满，无法入队，返回False return False node = ListNode(value) # 创建一个新节点 if self.head is None: # 如果队列为空，设置头部和尾部指针为新节点 self.head = node self.tail = node else: self.tail.next = node # 将新节点添加到尾部 self.tail = node # 更新尾部指针 self.size += 1 # 元素个数加1 return True def deQueue(self) -> bool: if self.isEmpty(): # 如果队列为空，无法出队，返回False return False self.head = self.head.next # 将头部指针后移一位，实现出队操作 self.size -= 1 # 元素个数减1 return True def Front(self) -> int: return -1 if self.isEmpty() else self.head.val # 如果队列为空，返回-1；否则返回头部节点的值 def Rear(self) -> int: return -1 if self.isEmpty() else self.tail.val # 如果队列为空，返回-1；否则返回尾部节点的值 def isEmpty(self) -> bool: return self.size == 0 # 如果元素个数为0，队列为空 def isFull(self) -> bool: return self.size == self.capacity # 如果元素个数等于队列容量，队列已满
说明： 使用链表来存储队列的元素。ListNode是节点结构体，用于表示队列中的每个节点。
MyCircularQueue类的初始化方法__init__中，初始化队头和队尾指针为None，队列容量为k，当前队列的元素个数为0。
enQueue
方法用于入队操作，首先判断队列是否已满，如果已满则无法入队，返回False。创建一个新节点，如果队列为空，设置头部和尾部指针为新节点；否则，将新节点添加到队尾，并更新尾部指针。元素个数加1，并返回True
表示入队成功。
复杂度分析
- 时间复杂度：初始化和每项操作的时间复杂度均为 O(1)。
- 空间复杂度：O(k)，其中 k 为给定的队列元素数目。
数组VS链表
| 方面 | 数组 | 链表 |
| 存储方式 | 连续的内存空间 | 非连续的内存空间 |
| 插入和删除操作 | O(n) | O(1) |
| 随机访问 | O(1) | O(n) |
| 内存效率 | 较高（不需要额外指针空间） | 较低（需要额外指针空间） |
| 大小变化 | 需要重新分配内存空间 | 可以动态变化 |
| 实现复杂性 | 相对简单 | 相对复杂 |
