这篇文章给大家分享的是有关python中如何定义栈、队列及双端队列的内容。小编觉得挺实用的，因此分享给大家做个参考，一起跟随小编过来看看吧。
我们首先学习 4 种简单而强大的数据结构。栈、队列、双端队列和列表都是有序的数据集合， 其元素的顺序取决于添加顺序或移除顺序。一旦某个元素被添加进来，它与前后元素的相对位置将保持不变。这样的数据集合经常被称为线性数据结构。
线性数据结构可以看作有两端。这两端有时候被称作“左端”和“右端”，有时候也被称作 “前端”和“后端”。当然，它们还可以被称作“顶端”和“底端”。名字本身并不重要，真正区分线性数据结构的是元素的添加方式和移除方式，尤其是添加操作和移除操作发生的位置。举例来说，某个数据结构可能只允许在一端添加新元素，有些则允许从任意一端移除元素。
栈有时也被称作“下推栈”。它是有序集合，添加操作和移除操作总发生在同一端，即“顶端”，另一端则被称为“底端”。
栈中的元素离底端越近，代表其在栈中的时间越长，因此栈的底端具有非常重要的意义。最新添加的元素将被最先移除。这种排序原则被称作 LIFO(last-in first-out)，即后进先出。它提供了一种基于在集合中的时间来排序的方式。最近添加的元素靠近顶端，旧元素则靠近底端。
给大家举个例子：比如你放书，你最先看过的书会被放在最底下。
栈的特点：每次的操作只能在栈道顶端进行。先进后出！插入和取出的顺序相反。
栈这种数据类型是人为定义的，在基础数据类型不存在，需要我们自己定义，它有一下操作：
Stack()创建一个空栈。它不需要参数，且会返回一个空栈
push(item)将一个元素添加到栈的顶端。它需要一个参数 item，且无返回值
pop()将栈顶端的元素移除。它不需要参数，但会返回顶端的元素，并且修改栈的内容
peek()返回栈顶端的元素，但是并不移除该元素。它不需要参数，也不会修改栈的内容
isEmpty()检查栈是否为空。它不需要参数，且会返回一个布尔值
size()返回栈中元素的数目。它不需要参数，且会返回一个整数。
例如下图是一个新创建的空栈。展示了对栈进行一系列操作的结果。在“栈内容”一列中，栈顶端的元素位于最右侧。
在前面一章中我们说到，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)
演示：
计算机中匹配括号
将十进制数转换成二进制数
前序、中序和后序表达式
队列是有序集合，添加操作发生在“尾部”，移除操作则发生在“头部”。新元素从尾部进入队列，然后一直向前移动到头部，直到成为下一个被移除的元素。
最新添加的元素必须在队列的尾部等待，在队列中时间最长的元素则排在最前面。这种排序原则被称作 FIFO(first-in first-out)，即先进先出，也称先到先得。
在日常生活中，我们经常排队，这便是最简单的队列例子。进电影院要排队，在超市结账要 排队，买咖啡也要排队(等着从盘子栈中取盘子)。好的队列只允许一头进，另一头出，不可能发生插队或者中途离开的情况，给大家看一个图：
队列抽象数据类型由下面的结构和操作定义。如前所述，队列是元素的有序集合，添加操作发生在其尾部，移除操作则发生在头部。队列的操作顺序是 FIFO，
它支持以下操作：
Queue()创建一个空队列。它不需要参数，且会返回一个空队列
enqueue(item)在队列的尾部添加一个元素。它需要一个元素作为参数，不返回任何值
dequeue()从队列的头部移除一个元素。它不需要参数，且会返回一个元素，并修改队列内容
isEmpty()检查队列是否为空。它不需要参数，且会返回一个布尔值
size()返回队列中元素的数目。它不需要参数，且会返回一个整数
如下图：展示了对 q 进行一系列操作的结果。假设 q 是一个新创建的空队列。在“队列内容”列中，队列的头部位于右端。4 是第一个被添加到队列中的元素，因此它也是第一个被移除的元素。
创建一个新类来实现队列抽象数据类型是十分合理的。像之前一样，我们利用简洁强大的列表来实现队列。假设队列的尾部在列表的位置 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)
演示：
著名的约瑟夫环
排队任务
双端队列与栈和队列不同的是，双端队列的限制很少。注意，不要把它的英文名 deque(与 deck 同音)和队列的移除操作 dequeue 搞混了。
双端队列是与队列类似的有序集合。它有一前、一后两端，元素在其中保持自己的位置。与 队列不同的是，双端队列对在哪一端添加和移除元素没有任何限制。新元素既可以被添加到前端， 也可以被添加到后端。同理，已有的元素也能从任意一端移除。某种意义上，双端队列是栈和队 列的结合。
下图展示了由 Python 数据对象组成的双端队列：
值得注意的是，尽管双端队列有栈和队列的很多特性，但是它并不要求按照这两种数据结构分别规定的 LIFO 原则和 FIFO 原则操作元素。具体的排序原则取决于其使用者。
双端队列抽象数据类型由下面的结构和操作定义。如前所述，双端队列是元素的有序集合，其任何一端都允许添加或移除元素。
双端队列支持以下操作：
Deque()创建一个空的双端队列。它不需要参数，且会返回一个空的双端队列。
addFront(item)将一个元素添加到双端队列的前端。它接受一个元素作为参数，没有返回值。
addRear(item)将一个元素添加到双端队列的后端。它接受一个元素作为参数，没有返 回值。
removeFront()从双端队列的前端移除一个元素。它不需要参数，且会返回一个元素， 并修改双端队列的内容。
removeRear()从双端队列的后端移除一个元素。它不需要参数，且会返回一个元素， 并修改双端队列的内容。
isEmpty()检查双端队列是否为空。它不需要参数，且会返回一个布尔值。
size()返回双端队列中元素的数目。它不需要参数，且会返回一个整数。
下图展示了对 d 进行一系列操作的结果。假设 d 是一个新创建的空双端队列，注意，前端 在列表的右端。记住前端和后端的位置可以防止混淆。
和前面一样，我们通过创建一个新类来实现双端队列抽象数据类型。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)
演示：
回文数检测
链表必须指明列表中第一个元素的位置。一旦知道第一个元素的位置，就能根据 其中的链接信息访问第二个元素，接着访问第三个元素，依此类推。指向链表第一个元素的引用被称作头。最后一个元素需要知道自己没有下一个元素。
==节点(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中如何定义栈、队列及双端队列”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，让大家可以学到更多知识，如果觉得文章不错，可以把它分享出去让更多的人看到吧！
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
