queue python一、什么是数据结构？二、数据结构的

一、什么是数据结构？

二、数据结构的分类

数据结构按照其逻辑结构可分为线性结构、树结构、图结构

线性结构：数据结构中的元素存在的相互关系

树结构：数据结构中的元素存在一对多的相互关系

图结构：数据结构中的元素存在多对多的相互关系

下面就来说说线性结构，树结构见链接，图结构待续。。

三、线性结构

（1）栈

1、定义：栈是一个数据集合，可以理解为只能在一端进行插入或者删除操作的列表。

2、栈的特点：后进先出（last-in，first-out），简称LTFO表

3、栈的概念：

栈顶：允许插入和删除的这一端称之为栈顶

栈底：另一固定的一端称为栈底

空栈：不含任何元素的栈称为空栈

4、栈的基本操作：

进栈（压栈）：push

出栈：pop

取栈顶：gettop

如图：

5、栈的Python实现

不需要自己定义，使用列表结构即可。queue python

进栈函数：append

出栈函数：pop

查看栈顶元素：li[-1]

6、栈的应用----括号匹配问题

问题：给一个字符串，其中包含小括号，中括号，大括号，求该字符串中的括号是否匹配

例如：

代码如下：

（2）队列

1、介绍

队列是一个数据集合，仅允许在列表的一端进行插入，另一端进行删除，

进行插入的一端称为队尾（rear），插入动作称之为进队或入队

进行删除的一端称之为对头（front），删除动作称为出队

双向队列：对列的两端都允许进行进队和出队操作

2、队列的实现

队列能否简单用列表实现？为什么？

初步设想：列表+两个下标指针

创建一个列表和两个变量，front变量指向队首，rear变量指向队尾。初始时，front和rear都为0。

进队操作：元素写到li[rear]的位置，rear自增1。

出队操作：返回li[front]的元素，front自减1。

3、队列的实现原理-----环形对列

环形队列：当队尾指针front == Maxsize + 1时，再前进一个位置就自动到0。

实现方式：求余数运算

队首指针前进1：front = (front + 1) % MaxSize

队尾指针前进1：rear = (rear + 1) % MaxSize

队空条件：rear == front

队满条件：(rear + 1) % MaxSize == front

3、对列的内置模块

使用方法：from collections import deque #deque是支持双向队列的

创建队列：queue = deque(li)

进队：append

出队：popleft

双向队列队首进队：appendleft

双向队列队尾进队：pop

（3）单链表

链表中每一个元素都是一个对象，每一个对象都是一个节点，包含有数据域key和指向下一个节点的指针next。通过各个节点之间的互相连接，最终串联成一个列表

1、节点定义：

2、建立链表

头插法

尾插法

3、链表的遍历

4、链表节点的插入和删除

插入：

删除：

< >（4）双链表

双链表中的每个节点有两个指针：一个指向后面节点、一个指向前面节点

1、节点定义：

2、双链表节点的插入和删除

（1）

（2）

（3）

（4）

这四张图片分别对应上面的四行代码

（5）哈希表

哈希表（又称为散列表），是一种线性表的存储结构。哈希表由一个顺序表（数组）和一个哈希函数组成。哈希函数h(k)将k作为自变量，返回元素的存储下标。

1、简单哈希函数

除法哈希：h(k) = k mod m #mod就是% #除留余数法

乘法哈希：h(k) = floor(m(kA mod 1)) 0<A<1 #floor是向下取整

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-65114-1.html