亲宝软件园·资讯

展开

python栈、队列和双端队列

柳小葱 人气:0

前文学习:

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

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

1.线性数据结构的定义

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

2.栈

2.1 栈的定义

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

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

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

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

2.2 栈的数据类型

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

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

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,

它支持以下操作:

如下图:展示了对 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 双端队列抽象数据类型

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

双端队列支持以下操作:

下图展示了对 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())



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

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

参考资料

加载全部内容

相关教程
猜你喜欢
用户评论