使用Python进行队列和出列数据结构

队列（Queue）

队列数据结构也意味着数据元素排列在队列中的位置相同。队列的唯一性在于添加和删除项目的方式。队列从两端打开，意味着元素从后面添加并从前面移除。所以这是一种先入先出的方法。

可以使用python list实现队列，我们​​可以使用insert（）和pop（）方法添加和删除元素。数据元素总是添加在队列末尾，所以没有插入结构。

Queue操作如下所示。

• Queue（）创建一个空的新队列。它不需要参数并返回空队列。
• enqueue（item）将新项添加到队列的后面。它需要该项目并且不返回任何内容。
• dequeue（）从队列中删除前项。它不需要参数并返回该项目。队列被修改。
• isEmpty（）测试以查看队列是否为空。它不需要参数并返回一个布尔值。
• size（）返回队列中的项目数。它不需要参数并返回一个整数。

在Python中实现队列

它适合于使用list集合的强大功能和简单性来构建抽象数据类型队列的实现，以构建队列的内部表示。

我们可以假设后面位于列表中的位置0。这允许我们使用list上的insert函数向队列后面添加新元素。

pop操作可用于删除前端元素（列表的最后一个元素）。回想一下，这也意味着enqueue将是O（n）并且dequeue将是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）

Deque，也称为双端队列，它有两个末端，一个前部和一个后部，项目保留在集合中部位置。可以在前部或后部添加或移除新项目。

它不需要那些数据结构强制执行的LIFO和FIFO顺序。这取决于您对添加和删除操作的一致使用

Deque操作如下。

• Deque（）创建一个空的deque。它不需要参数并返回空双端队列。
• addFront（item）在双端队列的前面添加一个新项。它需要该项目并且不返回任何内容。
• addRear（item）在双端队列的后面添加一个新项目。它需要该项目并且不返回任何内容。
• removeFront（）从双端队列中删除前项。它不需要参数并返回该项目。双端队列被修改。
• removeRear（）从双端队列中删除后部项目。它不需要参数并返回该项目。双端队列被修改。
• isEmpty（）测试以查看deque是否为空。它不需要参数并返回一个布尔值。
• size（）返回双端队列中的项目数。它不需要参数并返回一个整数。

在Python中实现Deque

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)

使用Deindue for Palindrome-Checker

因为我们可以直接删除它们，所以我们可以比较它们，只有当它们匹配时才能继续。如果我们能够始终匹配第一个和最后一个项，那么最终我们要么耗尽字符，要么得到大小为1的deque，这取决于原始字符串的长度是偶数还是奇数。无论哪种情况，字符串都必须是回文。

from pythonds.basic.deque import Deque
def palchecker(aString):
chardeque = Deque()

for ch in aString:
chardeque.addRear(ch)

stillEqual = True

while chardeque.size() > 1 and stillEqual:
first = chardeque.removeFront()
last = chardeque.removeRear()
if first != last:
stillEqual = False

return stillEqual

print(palchecker(“lsdkjfskf”))
print(palchecker(“radar”))