常见的七种查找算法¶
数据结构是数据存储的方式，算法是数据计算的方式。算法和数据结构息息相关，本文涉及部分数据结构的专业名词。
1. 基本查找（顺序查找）¶
说明：顺序查找适合于存储结构为数组或者链表。
基本思想：顺序查找也称为线性查找，属于无序查找算法。从数据结构线的一端开始，顺序扫描，依次将遍历到的结点与要查找的值相比较，若相等则表示查找成功；若遍历结束仍没有找到相同的，表示查找失败。
示例代码：
public class A01_BasicSearchDemo1 {
public static void main(String[] args) {
// 基本查找/顺序查找
// 核心：从0索引开始挨个往后查找
// 需求：定义一个方法利用基本查找，查询某个元素是否存在
// 数据如下：{131, 127, 147, 81, 103, 23, 7, 79}
int[] arr = {131, 127, 147, 81, 103, 23, 7, 79};
int number = 82;
System.out.println(basicSearch(arr, number));
}
// 参数：一：数组 二：要查找的元素
// 返回值：元素是否存在
public static boolean basicSearch(int[] arr, int number) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == number) {
return true;
}
}
return false;
}
}
2. 二分查找（折半查找）¶
说明：元素必须是有序的，从小到大或从大到小均可。
如果是无序的，可以先排序，但排序之后会改变原有数据的顺序，查找出来的元素位置跟原来可能不一样，所以排序之后再查找只能判断当前数据是否在容器当中，返回的索引无实际意义。
基本思想：也称为折半查找，属于有序查找算法。用给定值先与中间结点比较，比较之后有三种情况：
- 相等：说明找到了
- 要查找的数据比中间节点小：说明要查找的数字在中间节点左边
- 要查找的数据比中间节点大：说明要查找的数字在中间节点右边
代码示例：
public class A02_BinarySearchDemo1 {
public static void main(String[] args) {
// 二分查找/折半查找
// 核心：每次排除一半的查找范围
// 需求：定义一个方法利用二分查找，查询某个元素在数组中的索引
// 数据如下：{7, 23, 79, 81, 103, 127, 131, 147}
int[] arr = {7, 23, 79, 81, 103, 127, 131, 147};
System.out.println(binarySearch(arr, 150));
}
public static int binarySearch(int[] arr, int number) {
// 1.定义两个变量记录要查找的范围
int min = 0;
int max = arr.length - 1;
// 2.利用循环不断查找
while (true) {
if (min > max) {
return -1;
}
// 3.找到min和max的中间位置
int mid = (min + max) / 2;
// 4.拿着mid指向的元素跟要查找的元素进行比较
if (arr[mid] > number) {
// number在mid的左边
max = mid - 1;
} else if (arr[mid] < number) {
// number在mid的右边
min = mid + 1;
} else {
// 找到了
return mid;
}
}
}
}
3. 插值查找¶
在介绍插值查找之前，先考虑一个问题：为什么二分查找算法一定要折半，而不是折四分之一或者折更多呢？
二分查找中查找点计算如下：
mid = (low + high) / 2，即 mid = low + ½ * (high - low)
我们可以将查找点改进为：
mid = low + (key - a[low]) / (a[high] - a[low]) * (high - low)
这样，让 mid 值的变化更靠近关键字 key，间接减少了比较次数。
基本思想：基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。插值查找也属于有序查找。
细节：对于表长较大且关键字分布比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好得多。反之，数组中如果分布非常不均匀，插值查找未必是合适的选择。
代码跟二分查找类似，只需修改 mid 的计算方式即可。
4. 斐波那契查找¶
在介绍斐波那契查找算法之前，先介绍一下与之紧密相连的黄金分割概念。
黄金比例又称黄金分割，是指事物各部分间一定的数学比例关系，即将整体一分为二，较大部分与较小部分之比等于整体与较大部分之比，其比值约为 1:0.618 或 1.618:1。
0.618 被公认为最具有审美意义的比例数字，这个数值不仅体现在绘画、雕塑、音乐、建筑等艺术领域，在管理、工程设计等方面也有着不可忽视的作用。
斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89……（从第三个数开始，后边每一个数都是前两个数的和）。随着斐波那契数列的递增，前后两个数的比值会越来越接近 0.618，利用这个特性，就可以将黄金比例运用到查找技术中。
基本思想：二分查找的一种提升算法，通过运用黄金比例的概念在数列中选择查找点进行查找，提高查找效率。斐波那契查找也属于有序查找算法。
代码示例：
public class FeiBoSearchDemo {
public static int maxSize = 20;
public static void main(String[] args) {
int[] arr = {1, 8, 10, 89, 1000, 1234};
System.out.println(search(arr, 1234));
}
public static int[] getFeiBo() {
int[] arr = new int[maxSize];
arr[0] = 1;
arr[1] = 1;
for (int i = 2; i < maxSize; i++) {
arr[i] = arr[i - 1] + arr[i - 2];
}
return arr;
}
public static int search(int[] arr, int key) {
int low = 0;
int high = arr.length - 1;
int index = 0; // 斐波那契分割数的下标值
int mid = 0;
int[] f = getFeiBo(); // 斐波那契数列
// 获取斐波那契分割数值的下标
while (high > (f[index] - 1)) {
index++;
}
// 因为f[k]值可能大于a的长度，需要使用Arrays构造新数组，不足部分用0补齐
int[] temp = Arrays.copyOf(arr, f[index]);
// 实际使用arr数组最后一个数填充不足部分
for (int i = high + 1; i < temp.length; i++) {
temp[i] = arr[high];
}
// 循环处理，找到key值
while (low <= high) {
mid = low + f[index - 1] - 1;
if (key < temp[mid]) {
// 向数组前面部分查找
high = mid - 1;
/*
* 对k--的理解：
* 1. 全部元素 = 前面的元素 + 后面的元素
* 2. f[k] = f[k-1] + f[k-2]
* 前面有k-1个元素，可继续分为 f[k-1] = f[k-2] + f[k-3]
* 即在f[k-1]的前面继续查找，k--
* 下次循环 mid = f[k-1-1] - 1
*/
index--;
} else if (key > temp[mid]) {
// 向数组后面部分查找
low = mid + 1;
index -= 2;
} else {
// 找到了，确定返回哪个下标
if (mid <= high) {
return mid;
} else {
return high;
}
}
}
return -1;
}
}
5. 分块查找¶
当数据表中的数据元素很多时，可以采用分块查找。
分块查找汲取了顺序查找和折半查找各自的优点，既有动态结构，又适于快速查找。
分块查找适用于数据较多但数据不会发生变化的情况，如果需要一边添加一边查找，建议使用哈希查找。
分块查找的过程：
- 把数据分成 N 多个小块，块与块之间不能有数据重复的交集
- 给每一块创建对象单独存储到数组当中
- 查找数据时，先在数组中查当前数据属于哪一块
- 再到这一块中顺序查找
代码示例：
public class A03_BlockSearchDemo {
public static void main(String[] args) {
/*
* 分块查找
* 核心思想：块内无序，块间有序
* 实现步骤：
* 1. 创建数组blockArr存放每一个块对象的信息
* 2. 先查找blockArr确定要查找的数据属于哪一块
* 3. 再单独遍历这一块数据即可
*/
int[] arr = {16, 5, 9, 12, 21, 18,
32, 23, 37, 26, 45, 34,
50, 48, 61, 52, 73, 66};
// 创建三个块的对象
Block b1 = new Block(21, 0, 5);
Block b2 = new Block(45, 6, 11);
Block b3 = new Block(73, 12, 17);
// 定义数组用来管理三个块的对象（索引表）
Block[] blockArr = {b1, b2, b3};
// 定义变量记录要查找的元素
int number = 37;
// 调用方法，传递索引表、数组、要查找的元素
int index = getIndex(blockArr, arr, number);
System.out.println(index);
}
// 利用分块查找原理，查询number的索引
private static int getIndex(Block[] blockArr, int[] arr, int number) {
// 1. 确定number在哪一块当中
int indexBlock = findIndexBlock(blockArr, number);
if (indexBlock == -1) {
return -1; // number不在数组当中
}
// 2. 获取这一块的起始索引和结束索引
int startIndex = blockArr[indexBlock].getStartIndex();
int endIndex = blockArr[indexBlock].getEndIndex();
// 3. 遍历
for (int i = startIndex; i <= endIndex; i++) {
if (arr[i] == number) {
return i;
}
}
return -1;
}
// 确定number在哪一块当中
public static int findIndexBlock(Block[] blockArr, int number) {
for (int i = 0; i < blockArr.length; i++) {
if (number <= blockArr[i].getMax()) {
return i;
}
}
return -1;
}
}
class Block {
private int max; // 最大值
private int startIndex; // 起始索引
private int endIndex; // 结束索引
public Block() {}
public Block(int max, int startIndex, int endIndex) {
this.max = max;
this.startIndex = startIndex;
this.endIndex = endIndex;
}
public int getMax() { return max; }
public void setMax(int max) { this.max = max; }
public int getStartIndex() { return startIndex; }
public void setStartIndex(int startIndex) { this.startIndex = startIndex; }
public int getEndIndex() { return endIndex; }
public void setEndIndex(int endIndex) { this.endIndex = endIndex; }
public String toString() {
return "Block{max = " + max + ", startIndex = " + startIndex + ", endIndex = " + endIndex + "}";
}
}
6. 哈希查找¶
哈希查找是分块查找的进阶版，适用于数据一边添加一边查找的情况。
一般是「数组 + 链表」或「数组 + 链表 + 红黑树」的结合体。
为便于理解，简单规定如下：
- 数组的 0 索引处存储 1~100
- 数组的 1 索引处存储 101~200
- 数组的 2 索引处存储 201~300
- 以此类推
但实际开发中一般不会采取这种方式，因为容易导致某一块区域添加的元素过多，效率偏低。
更常见的做法是：先计算出当前数据的哈希值，用哈希值与数组长度进行计算，计算出应存入的位置，再挂在数组后面形成链表。如果挂的元素太多且数组长度过长，会把链表转化为红黑树，进一步提高效率。
7. 树表查找¶
本知识点涉及数据结构：树。
基本思想：二叉查找树是先对待查找的数据生成树，确保树的左分支的值小于右分支的值，然后和每个节点的父节点比较大小，查找最适合的范围。这个算法的查找效率很高，但如果使用这种查找方法需要首先创建树。
二叉查找树（Binary Search Tree，也称二叉搜索树或二叉排序树 Binary Sort Tree），具有下列性质：
- 若任意节点左子树上所有的数据，均小于本身
- 若任意节点右子树上所有的数据，均大于本身
二叉查找树性质：对二叉查找树进行中序遍历，即可得到有序的数列。
基于二叉查找树进行优化，进而可以得到其他树表查找算法，如平衡树、红黑树等高效算法。不管是二叉查找树、平衡二叉树还是红黑树，查找的性能都比较高。
常见排序算法¶
1. 冒泡排序¶
冒泡排序（Bubble Sort）是一种简单直观的排序算法。
它重复地遍历要排序的数列，一次比较相邻的两个元素，如果顺序错误就把它们交换过来。越大的元素会经由交换慢慢"浮"到最后面。
算法步骤¶
- 相邻的元素两两比较，大的放右边，小的放左边
- 第一轮比较完毕之后，最大值就已经确定，第二轮可以少循环一次，后面以此类推
- 如果数组中有 n 个数据，总共执行 n-1 轮的代码即可
代码示例¶
public class A01_BubbleDemo {
public static void main(String[] args) {
/*
* 冒泡排序：
* 核心思想：
* 1. 相邻的元素两两比较，大的放右边，小的放左边
* 2. 第一轮比较完毕之后，最大值就已经确定，第二轮可以少循环一次
* 3. 如果数组中有n个数据，总共执行n-1轮
*/
// 1. 定义数组
int[] arr = {2, 4, 5, 3, 1};
// 2. 利用冒泡排序将数组中的数据变成 1 2 3 4 5
// 外循环：表示要执行多少轮，n个数据执行n-1轮
for (int i = 0; i < arr.length - 1; i++) {
// 内循环：每一轮中如何比较数据并找到当前的最大值
// -1：防止索引越界
// -i：提高效率，每一轮执行的次数比上一轮少一次
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
printArr(arr);
}
private static void printArr(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}
2. 选择排序¶
算法步骤¶
- 从 0 索引开始，跟后面的元素一一比较
- 小的放前面，大的放后面
- 第一次循环结束后，最小的数据已经确定
- 第二次循环从 1 索引开始，以此类推
代码示例¶
public class A02_SelectionDemo {
public static void main(String[] args) {
/*
* 选择排序：
* 1. 从0索引开始，跟后面的元素一一比较
* 2. 小的放前面，大的放后面
* 3. 第一次循环结束后，最小的数据已经确定
* 4. 第二次循环从1索引开始以此类推
*/
// 1. 定义数组
int[] arr = {2, 4, 5, 3, 1};
// 2. 利用选择排序让数组变成 1 2 3 4 5
// 外循环：几轮
// i：表示这一轮中拿着哪个索引上的数据跟后面的数据进行比较并交换
for (int i = 0; i < arr.length - 1; i++) {
// 内循环：拿着i跟i后面的数据进行比较交换
for (int j = i + 1; j < arr.length; j++) {
if (arr[i] > arr[j]) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
printArr(arr);
}
private static void printArr(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}
3. 插入排序¶
插入排序的工作原理是通过创建有序序列和无序序列，然后遍历无序序列得到每一个数字，把每一个数字插入到有序序列中正确的位置。插入排序在插入时可以采取二分查找优化。
算法步骤¶
将 0 索引的元素到 N 索引的元素看做有序的，把 N+1 索引的元素到最后一个当成无序的。
遍历无序的数据，将遍历到的元素插入有序序列中适当的位置，如遇到相同数据，插在后面。
N 的范围：0 ~ 最大索引。
代码示例¶
public class A03_InsertDemo {
public static void main(String[] args) {
/*
* 插入排序：
* 将0索引到N索引的元素看做有序的，把N+1索引到最后一个当成无序的
* 遍历无序的数据，将遍历到的元素插入有序序列中适当的位置
* 如遇到相同数据，插在后面
* N的范围：0~最大索引
*/
int[] arr = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
// 1. 找到无序的那一组数组是从哪个索引开始的
int startIndex = -1;
for (int i = 0; i < arr.length; i++) {
if (arr[i] > arr[i + 1]) {
startIndex = i + 1;
break;
}
}
// 2. 遍历从startIndex开始到最后一个元素
for (int i = startIndex; i < arr.length; i++) {
// 记录当前要插入数据的索引
int j = i;
while (j > 0 && arr[j] < arr[j - 1]) {
// 交换位置
int temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
j--;
}
}
printArr(arr);
}
private static void printArr(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}
4. 快速排序¶
快速排序是由东尼·霍尔所发展的一种排序算法，是分而治之思想在排序算法上的典型应用。它是处理大数据最快的排序算法之一。
算法步骤¶
- 从数列中挑出一个元素（一般是左边第一个数字），称为"基准数"
- 创建两个指针，一个从前往后走，一个从后往前走
- 先执行后面的指针，找出第一个比基准数小的数字
- 再执行前面的指针，找出第一个比基准数大的数字
- 交换两个指针指向的数字
- 直到两个指针相遇
- 将基准数跟指针指向位置的数字交换位置，称为"基准数归位"
- 第一轮结束后，基准数左边的数字都比基准数小，右边的都比基准数大
- 把基准数左边和右边分别看做一个序列，递归排序
代码示例¶
public class A05_QuickSortDemo {
public static void main(String[] args) {
int[] arr = {1, 1, 6, 2, 7, 9, 3, 4, 5, 1, 10, 8};
long start = System.currentTimeMillis();
quickSort(arr, 0, arr.length - 1);
long end = System.currentTimeMillis();
System.out.println(end - start);
System.out.println(Arrays.toString(arr));
}
/*
* 参数一：要排序的数组
* 参数二：要排序数组的起始索引
* 参数三：要排序数组的结束索引
*/
public static void quickSort(int[] arr, int i, int j) {
// 定义两个变量记录要查找的范围
int start = i;
int end = j;
if (start > end) {
return; // 递归出口
}
// 记录基准数
int baseNumber = arr[i];
// 利用循环找到要交换的数字
while (start != end) {
// 利用end从后往前找比基准数小的数字
while (true) {
if (end <= start || arr[end] < baseNumber) {
break;
}
end--;
}
// 利用start从前往后找比基准数大的数字
while (true) {
if (end <= start || arr[start] > baseNumber) {
break;
}
start++;
}
// 交换end和start指向的元素
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
}
// 当start和end指向同一个元素时，基准数归位
int temp = arr[i];
arr[i] = arr[start];
arr[start] = temp;
// 递归排序左右两部分
quickSort(arr, i, start - 1);
quickSort(arr, start + 1, j);
}
}
数据结构¶
二叉树、堆、队列、栈等数据结构，大都是在已有数据结构基础上加以某些条件限制或改造，以满足实际问题需要而得来的。
二叉树¶
计算机中，数据元素在不同的场合还可以被称作"结点""顶点""记录"等。在二叉树中，数据元素统称为"结点"。
"二叉树"是一个由结点组成的有限集合。这个集合或者为空，或者由一个称为"根"的结点及两棵不相交的二叉树组成，这两棵二叉树分别称为这个根结点的"左子树"和"右子树"。
当二叉树非空时，上层结点称为"父结点"，两个子结点称为父结点的"孩子"结点或"叶结点"。
由二叉树的定义可知，它其实是一个递归式的定义：一个结点的左、右子树也是二叉树。如果子树为空，那么该结点就没有"左孩子"或"右孩子"。
二叉树是一种非线性结构，无法使用线性方法知道一个结点的"下一个"是谁，只有人为做出限定，才能访问某结点中的数据。
二叉树遍历¶
所谓"遍历"二叉树，是指按照规定的路线对二叉树进行搜索，以保证每个结点被访问一次，且只被访问一次。
若用 T、L、R 分别表示二叉树的根结点、左子树、右子树，访问结点的顺序有以下 6 种组合：
- TLR — 先访问根结点，再访问左子树，最后访问右子树
- LTR — 先访问左子树，再访问根结点，最后访问右子树
- LRT — 先访问左子树，再访问右子树，最后访问根结点
- TRL — 先访问根结点，再访问右子树，最后访问左子树
- RTL — 先访问右子树，再访问根结点，最后访问左子树
- RLT — 先访问右子树，再访问左子树，最后访问根结点
如果约定总是"先访左、后访右"，则只剩下 3 种：TLR、LTR、LRT。
- TLR — 先根遍历（先序遍历）
- LTR — 中根遍历（中序遍历）
- LRT — 后根遍历（后序遍历）
对于任何一棵二叉树，先根遍历时根结点总是处于遍历序列之首；中根遍历时根结点位置"居中"，左子树所有结点在其左边，右子树所有结点在其右边；后根遍历时根结点总是在最后。这个结论对整棵二叉树和各子二叉树都成立。
代码示例：
class BinaryTree:
def __init__(self, value):
self.left = None
self.right = None
self.data = value
def insertLeftChild(self, value):
if self.left:
print('Left child tree already exists.')
else:
self.left = BinaryTree(value)
return self.left
def insertRightChild(self, value):
if self.right:
print('Right child tree already exists.')
else:
self.right = BinaryTree(value)
return self.right
def preOrder(self):
"""先根遍历"""
print(self.data)
if self.left:
self.left.preOrder()
if self.right:
self.right.preOrder()
def postOrder(self):
"""后根遍历"""
if self.left:
self.left.postOrder()
if self.right:
self.right.postOrder()
print(self.data)
def inOrder(self):
"""中根遍历：优先走左，走完左后输出当前结点，再走右"""
if self.left:
self.left.inOrder()
print(self.data)
if self.right:
self.right.inOrder()
if __name__ == '__main__':
b1 = BinaryTree("1")
b2 = BinaryTree("2")
b3 = BinaryTree("3")
b1.left = b2
b1.right = b3
b1.inOrder()
堆¶
二叉树中有一种"完全二叉树"，指除最后一层外，其余各层结点都是满的，且最后一层结点都集中在左边。
"堆"是一棵完全二叉树，且各结点关键字值满足：从根结点到任何孩子结点路径上的关键字值都是非递减的，即根结点和任何分支结点的关键字值均小于或等于其左右孩子结点的关键字值。
堆的三个要点：
- 根结点是堆中所有结点里关键字值最小的记录
- 堆的任何一棵子树本身也是一个堆
- 堆中任一结点的关键字值不大于左右孩子结点，但左右孩子结点之间没有大小关系
堆排序¶
堆排序的基本思想：先输出根结点，然后通过一定规则对剩余结点进行调整，使其重新成为堆，再输出新根结点，如此反复，最终得到由小到大的序列。
Python 中提供了 heapq 标准库模块来实现堆排序：
import heapq
# 往堆里插入关键字，自动调整使其保持堆性质
heapq.heappush(<堆>, <关键字>)
# 从堆里弹出（删除）顶元素并返回，自动调整剩余结点
heapq.heappop(<堆>)
# 将列表转换为具有堆特性的完全二叉树
heapq.heapify(<列表>)
# 替换最小堆元素
heapq.heapreplace(<堆>, <关键字>)
# 以降序/升序返回堆中n个结点的关键字
heapq.nlargest(n, <堆>)
heapq.nsmallest(n, <堆>)
# 查看堆中最小关键字值（不弹出）
<堆>[0]
# 示例
nums = [75, 79, 71, 68, 94, 16, 11, 28]
heap1 = []
for i in nums:
heapq.heappush(heap1, i)
print('堆中已有元素：', heap1)
heappush() 和 heapify() 的区别：前者是一个一个插入逐渐形成堆；后者是把已有列表直接改造为满足堆性质的列表。
队列¶
队列的关键在于确定哪一端是头（退出操作）、哪一端是尾（插入操作）。
先进先出队列（FIFO）¶
若对有序可变数据结构加以限定，使插入操作在一端进行，删除操作在另一端进行，这种结构称为"队列"。
- 进入队列（插入）限制在队列的一端（队尾）
- 退出队列（删除）限制在队列的另一端（队首）
最先进入队列的元素最先从队列中出去，因此队列具有"先进先出（FIFO）"或"后进后出（LILO）"的特点。
栈（后进先出 LIFO）¶
若对有序可变数据结构加以限定，使插入和删除操作只能在固定的同一端进行，这种结构称为"栈"。
- 被允许进行插入和删除的那一端称为"栈顶"
- 不能进行插入和删除的那一端称为"栈底"
最后插入栈顶的元素最先从栈中移出，因此栈具有"后进先出（LIFO）"或"先进后出（FILO）"的特点。
优先级队列（Priority Queue）¶
按指定的优先级高低进行排队，级别高的先获得使用权。进入优先级队列时按优先级大小重新调整，资源分配时总是分给队列中第一个申请者。
通常规定优先数越小，优先级越高。
Python 队列模块¶
import queue
# 创建FIFO队列
que = queue.Queue(maxsize=0)
# maxsize<=0：队列尺寸无限制
# 否则达到maxsize上限时会阻止元素进入
# 创建LIFO队列（栈）
queue.LifoQueue(maxsize=0)
# 创建优先级队列
queue.PriorityQueue(maxsize=0)
# 常用方法：
队列名.qsize() # 返回队列中当前拥有的元素个数
队列名.empty() # 队列为空返回True
队列名.full() # 队列已满返回True
队列名.put(item) # 往队列里插入元素
队列名.get() # 从队列中取出元素
自定义实现 FIFO¶
class MyQueue:
def __init__(self, size=10):
self.current = 0
self.size = size
self.content = []
def put(self, v):
if self.current < self.size:
self.content.append(v)
self.current = self.current + 1
else:
print("The queue is full!")
def get(self):
if self.content:
self.current = self.current - 1
return self.content.pop(0)
else:
print('The queue is empty!')
def show(self):
if self.content:
print(self.content)
else:
print('The queue is empty!')
def empty(self):
self.content = []
def isEmpty(self):
return not self.content
def isfull(self):
return self.current == self.size
自定义实现栈（LIFO）¶
class Stack:
def __init__(self, size=10):
self.content = []
self.size = size
self.current = 0
def empty(self):
self.content = []
self.current = 0
def isempty(self):
return not self.content
def setSize(self, size):
if size < self.current:
for i in range(size, self.current):
del self.content[i]
self.current = size
self.size = size
def isfull(self):
return self.current == self.size
def push(self, v):
if len(self.content) < self.size:
self.content.append(v)
self.current = self.current + 1
else:
print('Stack Full!')
def pop(self):
if self.content:
self.current = self.current - 1
return self.content.pop()
else:
print('Stack is empty!')
def show(self):
print(self.content)
def showRemainderSpace(self):
print('Stack can still PUSH', self.size - self.current, 'elements.')