python数据结构之栈、队列及双端队列

目录
  • 1.线性数据结构的定义
  • 2.栈
    • 2.1 栈的定义
    • 2.2 栈的数据类型
    • 2.3 用python实现栈
    • 2.4 栈的应用
  • 3. 队列
    • 3.1 队列的定义
    • 3.2 队列抽象数据类型
    • 3.3 用python实现队列
    • 3.3 队列的应用
  • 4. 双端队列
    • 4.1 双端队列的定义
    • 4.2 双端队列抽象数据类型
    • 4.3 用python实现双端队列
    • 4.3 双端队列的应用
  • 5.链表
    • 5.1 链表定义
    • 5.2 用python实现链表

前文学习:

python数据类型: python数据结构:数据类型.
python的输入输出: python数据结构输入输出及控制和异常.
python面向对象: python数据结构面向对象.
python算法分析: python数据结构算法分析.

今天来学习数据结构之栈、队列和双端队列,主要是使用python来实现这些基础的数据结构,了解他们的性能,可能还会接触到二叉树,还会了解用这些结构来解决什么样的问题。总而言之,很重要就对了。

1.线性数据结构的定义

我们首先学习 4 种简单而强大的数据结构。栈、队列、双端队列和列表都是有序的数据集合, 其元素的顺序取决于添加顺序或移除顺序。一旦某个元素被添加进来,它与前后元素的相对位置将保持不变。这样的数据集合经常被称为线性数据结构。
线性数据结构可以看作有两端。这两端有时候被称作“左端”和“右端”,有时候也被称作 “前端”和“后端”。当然,它们还可以被称作“顶端”和“底端”。名字本身并不重要,真正区分线性数据结构的是元素的添加方式和移除方式,尤其是添加操作和移除操作发生的位置。举例来说,某个数据结构可能只允许在一端添加新元素,有些则允许从任意一端移除元素。

2.栈

2.1 栈的定义

栈有时也被称作“下推栈”。它是有序集合,添加操作和移除操作总发生在同一端,即“顶端”,另一端则被称为“底端”。

栈中的元素离底端越近,代表其在栈中的时间越长,因此栈的底端具有非常重要的意义。最新添加的元素将被最先移除。这种排序原则被称作 LIFO(last-in first-out),即后进先出。它提供了一种基于在集合中的时间来排序的方式。最近添加的元素靠近顶端,旧元素则靠近底端。

给大家举个例子:比如你放书,你最先看过的书会被放在最底下。

栈的特点:每次的操作只能在栈道顶端进行。先进后出!插入和取出的顺序相反。

2.2 栈的数据类型

栈这种数据类型是人为定义的,在基础数据类型不存在,需要我们自己定义,它有一下操作:

  • Stack()创建一个空栈。它不需要参数,且会返回一个空栈
  • push(item)将一个元素添加到栈的顶端。它需要一个参数 item,且无返回值
  • pop()将栈顶端的元素移除。它不需要参数,但会返回顶端的元素,并且修改栈的内容
  • peek()返回栈顶端的元素,但是并不移除该元素。它不需要参数,也不会修改栈的内容
  • isEmpty()检查栈是否为空。它不需要参数,且会返回一个布尔值
  • size()返回栈中元素的数目。它不需要参数,且会返回一个整数。

例如下图是一个新创建的空栈。展示了对栈进行一系列操作的结果。在“栈内容”一列中,栈顶端的元素位于最右侧。

2.3 用python实现栈

在前面一章中我们说到,python是一门面向对象的编程语言,每当需要在 Python 中实现像栈这样的抽象数据类型时,就可以创建新类。栈的操作通过方法实现。更进一步地说,因为栈是元素的集合,所以完全可以利用 Python 提供的强大、简单的原生集合来实现。这里我们基于列表来实现栈。

class stack:
    def __init__(self):#构建空栈
        self.items = []
    def isEmpty(self):#判断是否为空
        return self.item==[]
    def push(self, item):#向栈内押送数据
        self.items.append(item)
    def pop(self):#移除栈顶的元素
        return self.items.pop()
    def peek(self):#返回栈顶顶元素
        return self.items[len(self.items)-1]
    def size(self):#返回栈的长度
        return len(self.items)

演示:

2.4 栈的应用

  • 计算机中匹配括号
  • 将十进制数转换成二进制数
  • 前序、中序和后序表达式

3. 队列

3.1 队列的定义

队列是有序集合,添加操作发生在“尾部”,移除操作则发生在“头部”。新元素从尾部进入队列,然后一直向前移动到头部,直到成为下一个被移除的元素。
最新添加的元素必须在队列的尾部等待,在队列中时间最长的元素则排在最前面。这种排序原则被称作 FIFO(first-in first-out),即先进先出,也称先到先得。

在日常生活中,我们经常排队,这便是最简单的队列例子。进电影院要排队,在超市结账要 排队,买咖啡也要排队(等着从盘子栈中取盘子)。好的队列只允许一头进,另一头出,不可能发生插队或者中途离开的情况,给大家看一个图:

3.2 队列抽象数据类型

队列抽象数据类型由下面的结构和操作定义。如前所述,队列是元素的有序集合,添加操作发生在其尾部,移除操作则发生在头部。队列的操作顺序是 FIFO,

它支持以下操作:

  • Queue()创建一个空队列。它不需要参数,且会返回一个空队列
  • enqueue(item)在队列的尾部添加一个元素。它需要一个元素作为参数,不返回任何值
  • dequeue()从队列的头部移除一个元素。它不需要参数,且会返回一个元素,并修改队列内容
  • isEmpty()检查队列是否为空。它不需要参数,且会返回一个布尔值
  • size()返回队列中元素的数目。它不需要参数,且会返回一个整数

如下图:展示了对 q 进行一系列操作的结果。假设 q 是一个新创建的空队列。在“队列内容”列中,队列的头部位于右端。4 是第一个被添加到队列中的元素,因此它也是第一个被移除的元素。

3.3 用python实现队列

创建一个新类来实现队列抽象数据类型是十分合理的。像之前一样,我们利用简洁强大的列表来实现队列。假设队列的尾部在列表的位置 0 处。如此一来,便可以使用 insert 函数向队列的尾部添加新元素。pop 则可 用于移除队列头部的元素(列表中的最后一个元素)。这意味着添加操作的时间复杂度是 O(n) , 移除操作则是O(1)。

class queue:
    def __init__(self): #构建初始队列
        self.items=[]
    def isEmpty(self):#判断是否为空
        return self.items==[]
    def enqueue(self,item):#加入队列
        self.items.insert(0,item)
    def dequeue(self):#删除队列元素
        return self.items.pop()
    def size(self):#展示队列长度
        return len(self.items)

演示:

3.3 队列的应用

  • 著名的约瑟夫环
  • 排队任务

4. 双端队列

双端队列与栈和队列不同的是,双端队列的限制很少。注意,不要把它的英文名 deque(与 deck 同音)和队列的移除操作 dequeue 搞混了。

4.1 双端队列的定义

双端队列是与队列类似的有序集合。它有一前、一后两端,元素在其中保持自己的位置。与 队列不同的是,双端队列对在哪一端添加和移除元素没有任何限制。新元素既可以被添加到前端, 也可以被添加到后端。同理,已有的元素也能从任意一端移除。某种意义上,双端队列是栈和队 列的结合。

下图展示了由 Python 数据对象组成的双端队列:

值得注意的是,尽管双端队列有栈和队列的很多特性,但是它并不要求按照这两种数据结构分别规定的 LIFO 原则和 FIFO 原则操作元素。具体的排序原则取决于其使用者。

4.2 双端队列抽象数据类型

双端队列抽象数据类型由下面的结构和操作定义。如前所述,双端队列是元素的有序集合,其任何一端都允许添加或移除元素。

双端队列支持以下操作:

  • Deque()创建一个空的双端队列。它不需要参数,且会返回一个空的双端队列。
  • addFront(item)将一个元素添加到双端队列的前端。它接受一个元素作为参数,没有返回值。
  • addRear(item)将一个元素添加到双端队列的后端。它接受一个元素作为参数,没有返 回值。
  • removeFront()从双端队列的前端移除一个元素。它不需要参数,且会返回一个元素, 并修改双端队列的内容。
  • removeRear()从双端队列的后端移除一个元素。它不需要参数,且会返回一个元素, 并修改双端队列的内容。
  • isEmpty()检查双端队列是否为空。它不需要参数,且会返回一个布尔值。
  • size()返回双端队列中元素的数目。它不需要参数,且会返回一个整数。

下图展示了对 d 进行一系列操作的结果。假设 d 是一个新创建的空双端队列,注意,前端 在列表的右端。记住前端和后端的位置可以防止混淆。

4.3 用python实现双端队列

和前面一样,我们通过创建一个新类来实现双端队列抽象数据类型。Python 列表再一次提供了很多简便的方法来帮助我们构建双端队列。在下图中,我们假设双端队列的后端是列表的位置 0 处。

class Deque:
    def __init__(self):#创建新的双端队列
        self.items = []
    def isEmpty(self):#判断是否为空
        return self.items == []
    def addFront(self, item):#在前端添加元素
        self.items.append(item)
    def addRear(self, item):#在后端添加字符
        self.items.insert(0, item)
    def removeFront(self):#移除前端的字符
        return self.items.pop()
    def removeRear(self):#在后端异常字符
        return self.items.pop(0)
    def size(self):#双端队列的长度
        return len(self.items)

演示:

4.3 双端队列的应用

  • 回文数检测

5.链表

5.1 链表定义

链表必须指明列表中第一个元素的位置。一旦知道第一个元素的位置,就能根据 其中的链接信息访问第二个元素,接着访问第三个元素,依此类推。指向链表第一个元素的引用被称作头。最后一个元素需要知道自己没有下一个元素。

5.2 用python实现链表

==节点(node)==是构建链表的基本数据结构。每一个节点对象都必须持有至少两份信息。首先,节点必须包含列表元素,我们称之为节点的数据变量。其次,节点必须保存指向下一个节点的引用。

#声明一个链表节点的结构
class Node:
    def __init__(self, initdata):#初始化节点,next为none
        self.data = initdata
        self.next = None
    def getData(self):#节点的值
        return self.data
    def getNext(self):#节点的下一个节点
        return self.next
    def setData(self, newdata):#设置节点的值
        self.data = newdata
    def setNext(self, newnext):#设置节点的下一节点连接值
        self.next = newnext

链表是基于节点集合来构建的,每一个节点都通过显式的引用指向下一个节点。只要知道第一个节点的位置(第一个节点包含第一个元素),其后的每一个元素都能通过下一个引用找到。因此,节点类必须包含指向第一个节点的引用。注意,每一个列表对象都保存了指向列表头部的引用。

#声明一个链表开头
class UnorderedList:
    def __init__(self):
        self.head = None

最开始构建列表时,其中没有元素,赋值语句 mylist = UnorderedList()将创建下图的链表,与在 Node 类中一样,特殊引用值 None 用于表明列表的头部没有指向任何节点。列表的头部指向包含列表第 一个元素的节点。这个节点包含指向下一个节点(元素)的引用,依此类推。非常重要的一点是, 列表类本身并不包含任何节点对象,而只有指向整个链表结构中第一个节点的引用。

关于链表的操作我们这里就一下子给大家了:

#声明节点结构,在创建链表是会用到改结构
class Node:
    def __init__(self, initdata):#初始化节点,next为none
        self.data = initdata
        self.next = None
    def getData(self):#节点的值
        return self.data
    def getNext(self):#节点的下一个节点
        return self.next
    def setData(self, newdata):#设置节点的值
        self.data = newdata
    def setNext(self, newnext):#设置节点的下一节点连接值
        self.next = newnext
#声明一个链表结构,里面包含很多节点
class UnorderedList:
    def __init__(self):
        self.head = None
    def add(self, item): #增加一个节点
        temp = Node(item)
        temp.setNext(self.head)
        self.head = temp

    def length(self): #链表长度
        current = self.head
        count = 0
        while current != None:
            count = count + 1
            current = current.getNext()
        return count

    def search(self, item): #查找是否存在该节点
        current = self.head
        found = False
        while current != None and not found:
            if current.getData() == item:
                found = True
            else:
                current = current.getNext()
        return found
    def remove(self, item): #移除该节点
        current = self.head
        previous = None
        found = False
        while not found:
            if current.getData() == item:
                found = True
            else:
                previous = current
                current = current.getNext()
        if previous == None:
            self.head = current.getNext()
        else:
            previous.setNext(current.getNext())

下面是一些对链表的操作:

总结:
其实这里只是简单介绍了一下栈、队列和链表,以及简单的实现,其实他们实现的方式有很多种,我们这里只用了简单的实现方式。

参考资料

  • 《python数据结构与算法》
  • 《大话数据结构》

到此这篇关于python数据结构之栈、队列及双端队列的文章就介绍到这了,更多相关python栈、队列和双端队列内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • python数据结构输入输出及控制和异常

    目录 1. 输入 input 2. 输出 print 2.1 普通输出 2.2 格式化输出 3. 控制语句 4. 异常处理 前言: python数据类型: python数据结构之数据类型. 今天我们主要来介绍一些内置函数,比如输入输出,控制,和异常的用法,尤其是输出和控制,用的太多了,写算法题,输出数据格式问题,对以后都会很有帮助. 1. 输入 input 程序经常需要与用户进行交互,以获得数据或者提供某种结果.Python 提供了一个函数,它使得我们可以要求用户输入数据并且返回一个字 符串的引

  • python数据结构之面向对象

    目录 1. 面向对象编程 2. 构建类 3. 继承 3.1 继承案例 python数据结构:数据类型.  python数据结构输入输出及控制和异常. 今天我们来学习面向对象编程,面向对象这种编程方式非常重要,我们以后学习到的栈.队列.链表都是通过面向对象的方式实现的. 1. 面向对象编程 定义:面向对象是按照人们客观世界的系统思维方式,采用基于对象(实体)的概念建立模型 ,模拟客观世界分析,设计,实现软件的办法.通过面向对象的理念使计算机软件系统能与现实世界中的系统的一一对应. 听到这很多同学应

  • python数据结构:数据类型

    目录 1.数据是什么? 2.数据类型 2.1内建原子数据类型 2.2 内建集合数据类型 3.集合数据类型的方法 3.1 列表 3.2 字符串 3.3 元祖 3.4 集合 3.5 字典 1.数据是什么? 在 Python 以及其他所有面向对象编程语言中,类都是对数据的构成(状态)以及数据 能做什么(行为)的描述.由于类的使用者只能看到数据项的状态和行为,因此类与抽象数据类 型是相似的.在面向对象编程范式中,数据项被称作对象.一个对象就是类的一个实例. 2.数据类型 2.1内建原子数据类型 Pyth

  • 使用python实现数组、链表、队列、栈的方法

    引言 什么是数据结构? 数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成. 简单来说,数据结构就是设计数据以何种方式组织并存储在计算机中. 比如:列表,集合和字典等都是数据结构 N.Wirth:"程序=数据结构+算法" 数据结构按照其逻辑结构可分为线性结构.树结构.图结构 线性结构:数据结构中的元素存在一对一的互相关系. 树结构:数据结构中的元素存在一对多的互相关系. 图结构:数据结构中的元素存在多对多的互相关系. 数组 在python中是没有数

  • Python双端队列deque的实现

    目录 前言 基本用法 填充 线程安全 旋转 限制双端队列大小 前言 双端队列deque支持从任意一端增加和删除元素.其中,栈和队列就是双端队列的退化形式,它们的输入输出被限制在某一端. 基本用法 首先,我们来看看容器collections.deque()函数的基本用法.具体代码如下所示: import collections c = collections.deque('abcdefg') print("输出双端队列:", c) print("双端队列的长度:",

  • python双端队列原理、实现与使用方法分析

    本文实例讲述了python双端队列原理.实现与使用方法.分享给大家供大家参考,具体如下: 双端队列 双端队列(deque,全名double-ended queue),是一种具有队列和栈的性质的数据结构. 双端队列中的元素可以从两端弹出,其限定插入和删除操作在表的两端进行.双端队列可以在队列任意一端入队和出队. 操作 Deque() 创建一个空的双端队列 add_front(item) 从队头加入一个item元素 add_rear(item) 从队尾加入一个item元素 remove_front(

  • python数据结构算法分析

    目录 1.算法分析的定义 2. 大O记法 3. 不同算法的大O记法 3.1 清点法 3.2 排序法 3.3 蛮力法 3.4 计数法 4. 列表和字典操作的复杂度 4.1 列表 4.2 字典 前文学习: python数据类型: python数据结构:数据类型. python的输入输出: python数据结构输入输出及控制和异常. python面向对象: python数据结构面向对象. 今天我们来学习的内容是面试题中都避免不小了的问题,就是算法分析了,什么是算法分析,算法分析是用来分析一个算法的好坏

  • Python实现栈和队列的简单操作方法示例

    本文实例讲述了Python实现栈和队列的简单操作方法.分享给大家供大家参考,具体如下: 先简单的了解一下数据结构里面的栈和堆: 栈和队列是两种基本的数据结构,同为容器类型.两者根本的区别在于: stack:后进先出 queue:先进先出 stack和queue是不能通过查询具体某一个位置的元素而进行操作的.但是他们的排列是按顺序的 对于stack我们可以使用python内置的list实现,因为list是属于线性数组,在末尾插入和删除一个元素所使用的时间都是O(1),这非常符合stack的要求.当

  • Python 实现数据结构-堆栈和队列的操作方法

    队.栈和链表一样,在数据结构中非常基础一种数据结构,同样他们也有各种各样.五花八门的变形和实现方式.但不管他们形式上怎么变,队和栈都有其不变的最基本的特征,我们今天就从最基本,最简单的实现来看看队列和堆栈. 不管什么形式的队列,它总有的一个共同的特点就是"先进先出".怎么理解呢?就像是超市排队结账,先排队的人排在队的前面,先结账出队.这是队列的特征. 而堆栈则和队列相反,它是"先进后出",怎么理解呢?基本所有的编辑器都有一个撤销功能,就是按Ctrl+Z.当你写了一段

  • python数据结构之栈、队列及双端队列

    目录 1.线性数据结构的定义 2.栈 2.1 栈的定义 2.2 栈的数据类型 2.3 用python实现栈 2.4 栈的应用 3. 队列 3.1 队列的定义 3.2 队列抽象数据类型 3.3 用python实现队列 3.3 队列的应用 4. 双端队列 4.1 双端队列的定义 4.2 双端队列抽象数据类型 4.3 用python实现双端队列 4.3 双端队列的应用 5.链表 5.1 链表定义 5.2 用python实现链表 前文学习: python数据类型: python数据结构:数据类型. py

  • JS中队列和双端队列实现及应用详解

    队列 队列 双端队列数据结构 应用 用击鼓传花游戏模拟循环队列 用双端对列检查一个词是否构成回文 生成 1 到 n 的二进制数 队列和双端队列 队列遵循先进后出(FIFO, 也称为先来先服务) 原则的. 日常有很多这样场景: 排队购票.银行排队等. 由对列的特性,银行排队为例, 队列应该包含如下基本操作: 加入队列(取号) enqueue 从队列中移除(办理业务离开) dequeue 当前排队号码(呼叫下一个人) peek 当前队列长度(当前排队人数) size 判断队列是不是空 isEmpty

  • Python数据结构与算法的双端队列详解

    目录 什么是双端队列​ ​用Python实现双端队列 运用双端队列构建回文检测器 总结 什么是双端队列​ 双端队列是与队列类似的有序集合.它有一前.一后两端,元素在其中保持自己的位置.与队列不同的是,双端队列对在哪一端添加和移除元素没有任何限制.新元素既可以被添加到前端,也可以被添加到后端.同理,已有的元素也能从任意一端移除.某种意义上,双端队列可以是栈和队列的结合. 值得注意的是,尽管双端队列有栈和队列的很多特性,但是它并不要求按照这两种数据结构分别规定的LIFO原则和FIFO原则操作元素.具

  • javascript实现双端队列

    本文实例为大家分享了javascript实现双端队列的具体代码,供大家参考,具体内容如下 1.双端队列 双端队列是一种允许我们同时从前端和后端添加和移除元素的特殊队列 2.双端队列的应用 一个刚买了票的入如果只是还需要再问一些简单的信息,就可以直接回到队伍头部,另外队伍末尾的人如果赶时间也可以直接离开队伍 3.双端队列的方法 addFront(element):该方法在双端队列前端添加新的元素 addBack(element):该方法在双端队列后端添加新的元素(实现方法和 Queue 类中的en

  • Python实现的数据结构与算法之双端队列详解

    本文实例讲述了Python实现的数据结构与算法之双端队列.分享给大家供大家参考.具体分析如下: 一.概述 双端队列(deque,全名double-ended queue)是一种具有队列和栈性质的线性数据结构.双端队列也拥有两端:队首(front).队尾(rear),但与队列不同的是,插入操作在两端(队首和队尾)都可以进行,删除操作也一样. 二.ADT 双端队列ADT(抽象数据类型)一般提供以下接口: ① Deque() 创建双端队列 ② addFront(item) 向队首插入项 ③ addRe

  • Python数据结构之栈、队列的实现代码分享

    1. 栈 栈(stack)又名堆栈,它是一种运算受限的线性表.其限制是仅允许在表的一端进行插入和删除运算.这一端被称为栈顶,相对地,把另一端称为栈底.向一个栈插入新元素又称作进栈.入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素:从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素. 栈(Stack)是限制插入和删除操作只能在一个位置进行的表,该位置是表的末端,称为栈的顶(top).栈的基本操作有PUSH(入栈)和POP(出栈).栈又被称为LIF

  • Python双端队列实现回文检测

    目录 一.双端队列 二.回文检测 补充 一.双端队列 双端队列 Deque 是一种有次序的数据集,跟队列相似,其两端可以称作"首" 和 "尾"端,但 Deque 中数据项既可以从队首加入,也可以从队尾加入:数据项也可以从两端移除.某种意义上说,双端队列集成了栈和队列的能力. 但双端队列并不具有内在的 LIFO 或者 FIFO 特性,如果用双端队列来模拟栈或队列,需要由使用者自行维护操作的一致性. 用 Python 实现抽象数据类型Deque,Deque定义的操作如下

  • 详解Python的collections模块中的deque双端队列结构

    deque 是 double-ended queue的缩写,类似于 list,不过提供了在两端插入和删除的操作. appendleft 在列表左侧插入 popleft 弹出列表左侧的值 extendleft 在左侧扩展 例如: queue = deque() # append values to wait for processing queue.appendleft("first") queue.appendleft("second") queue.appendl

随机推荐