Dieser Artikel vermittelt Ihnen relevantes Wissen über Python, in dem hauptsächlich Probleme im Zusammenhang mit Double-End-Warteschlangen vorgestellt werden, einschließlich der Grundkonzepte von Double-End-Warteschlangen, der Implementierung von Double-End-Warteschlangen und der Anwendungen von Double-End-Warteschlangen. Ich hoffe, dass es für alle hilfreich ist.
Empfohlenes Lernen: Python-Tutorial
0 Lernziele
Eine doppelendige Warteschlange ist eine weitere lineare Datenstruktur. Obwohl es sich im Gegensatz zu Stapeln und Warteschlangen auch um eine eingeschränkte lineare Tabelle handelt, weisen doppelseitige Warteschlangen nur wenige Einschränkungen auf. Ihre Grundoperationen sind ebenfalls eine Teilmenge der linearen Tabellenoperationen, unterscheiden sich jedoch aus Sicht des Datentyps erheblich von linearen Tabellen . In diesem Abschnitt werden die Definition einer doppelendigen Warteschlange und ihre verschiedenen Implementierungen vorgestellt und einige praktische Anwendungen einer doppelendigen Warteschlange gegeben.
Durch das Studium dieses Abschnitts sollten Sie die folgenden Inhalte beherrschen:
- Die Grundkonzepte und verschiedenen Implementierungsmethoden von Double-Ended-Warteschlangen
- Die Implementierung und zeitliche Komplexität der Grundoperationen von Double-End-Warteschlangen
- Verwendung der Grundoperationen von Double-Ended Queues zur Implementierung komplexer Algorithmen
1. Das Grundkonzept der Double-Ended Queue
1.1 Das Grundkonzept der Double-Ended Queue
Double-Ended Queue (double-end queue) code>, <code>deque) wird ebenfalls eingefügt und Löschvorgänge sind jeweils auf lineare Listen an beiden Enden der Sequenz beschränkt, aber im Gegensatz zu Stapeln und Warteschlangen unterliegen doppelendige Warteschlangen nur wenigen Einschränkungen , die Rückseite der Warteschlange (rear) und die Vorderseite der Warteschlange (front) ermöglichen sowohl das Einfügen als auch das Löschen von Elementen. Neue Elemente können am Anfang oder am Ende der Warteschlange hinzugefügt werden. Ebenso können vorhandene Elemente an beiden Enden entfernt werden. In gewissem Sinne kann eine doppelendige Warteschlange als eine Kombination aus einem Stapel und einer Warteschlange betrachtet werden. double-end queue, deque) 也是插入和删除操作分别被限制在序列两端的线性表，但与栈和队列不同的是，Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange的限制很少，对于Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange而言，队尾 (rear) 和队头 (front) 均允许插入元素和删除元素。新元素既可以被添加到队头， 也可以被添加到队尾。同理，已有的元素也能从任意一端移除。某种意义上，可以认为Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange是栈和队列的结合。
尽管Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange有栈和队列的很多特性，但是它并不要求按照这两种数据结构所限定的 LIFO 原则和 FIFO 原则操作元素。
1.2 Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange抽象数据类型
除了添加和移除元素外，Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange还具有初始化、判队空和求队长度等辅助操作。具体而言，Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange的抽象数据类型定义如下：
基本操作：
1. __itit__(): 初始化Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange
创建一个空Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange
2. size(): 求取并返回Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange中所含元素的个数 n
若Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange为空，则返回整数0
3. isempty(): 判断是否为空Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange
判断Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange中是否存储元素
4. addfront(data): Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange队头添加元素
将元素 data 插入队头
5. addrear(data): Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange队尾添加元素
将元素 data 插入队尾
6. removefront(): 删除Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange队头元素
删除并返回队头元素
7. removerear(): 删除Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange队尾元素
删除并返回队尾元素
2. Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange的实现
和普通队列一样，Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange同样有顺序存储和链式存储两种存储表示方式。
2.1 顺序Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange的实现
类似于顺序队列，Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange的顺序存储结构利用一组地址连续的存储单元依次存放从Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange头到Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange尾的元素，同时需要用两个指针 front 和 rear 分别指示队列头元素和队列尾元素的位置。初始化空Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange时，front=rear=0，当元素入队时，rear 加 1，而元素出队时，front 加 1，同时为了重复利用空闲空间，我们将顺序Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange假设尾环状空间，最后一个空间和第一个空间视为连续空间(具体原因参考)：
同样顺序Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange可以是固定长度和动态长度，当Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange满时，定长顺序Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange会抛出Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange满异常，动态顺序Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange则会动态申请空闲空间。
2.1.1 Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange的初始化
顺序Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange的初始化需要 4 部分信息：deque 列表用于存储数据元素，max_size 用于存储 queue 列表的最大长度，以及 front 和 rear
🎜🎜Obwohl die Deque eine hat Stapel und Warteschlangen, erfordert jedoch keine Betriebselemente gemäß den durch diese beiden Datenstrukturen definierten
LIFO-Prinzipien und
FIFO-Prinzipien. 🎜🎜🎜1.2 Abstrakter Datentyp der doppelendigen Warteschlange🎜🎜🎜Neben dem Hinzufügen und Entfernen von Elementen verfügen doppelendige Warteschlangen auch über Hilfsoperationen wie Initialisierung, Beurteilung der Warteschlangenleerheit und Warteschlangenlänge. Konkret ist der abstrakte Datentyp der Double-Ended-Warteschlange wie folgt definiert: 🎜
🎜 Grundoperationen: 🎜 ˜ 1. __itit__(): Initialisieren Sie die Deque 🎜 ˜Erstellen Sie eine leere Deque 🎜 ˜ 2. size(): Finden Sie die Union. Gibt die Anzahl n der in der doppelseitigen Warteschlange enthaltenen Elemente zurück. Wenn die doppelseitige Warteschlange leer ist, wird die Ganzzahl 0 zurückgegeben. Isempty(): Bestimmt, ob die doppelseitige Warteschlange leer ist. : Elemente zum Kopf der doppelendigen Warteschlange hinzufügen 🎜 Elementdaten am Anfang der Warteschlange einfügen 🎜 5. addrear(data): Elemente am Ende der doppelendigen Warteschlange hinzufügen 🎜 Elementdaten am Ende der Warteschlange einfügen queue 🎜 6. removefront(): Double entfernen Das Kopfelement der doppelendigen Warteschlange 🎜 ˆ ˜ löscht das vordere Element und gibt es zurück 🎜 ˆ 7. removerear(): löscht das hintere Element der doppelendigen Warteschlange 🎜 ˆ ˆ löscht und gibt das hintere Element der doppelendigen Warteschlange zurück 🎜
🎜2. Implementierung der doppelendigen Warteschlange 🎜🎜 und gewöhnliche Warteschlangen haben auch zwei Speicherdarstellungen: sequentielle Speicherung und Kettenspeicherung. 🎜🎜🎜2.1 Implementierung einer sequentiellen doppelendigen Warteschlange🎜🎜🎜Ähnlich einer sequentiellen Warteschlange verwendet die sequentielle Speicherstruktur einer doppelendigen Warteschlange eine Reihe von Speichereinheiten mit aufeinanderfolgenden Adressen, um Elemente vom Kopf der doppelendigen Warteschlange zu speichern Verwenden Sie zwei Zeiger
front und
rear, um die Positionen des Warteschlangenkopfelements bzw. des Warteschlangenendeelements anzuzeigen. Beim Initialisieren einer leeren doppelendigen Warteschlange wird
front=rear=0 verwendet, wenn ein Element zur Warteschlange hinzugefügt wird, wird
rear um 1 erhöht und wenn ein Element aus der Warteschlange entfernt wird ,
front wird um 1 erhöht, und um freien Speicherplatz wiederzuverwenden, gehen wir davon aus, dass die sequentielle doppelendige Warteschlange einen Endringraum hat und der letzte Raum und der erste Raum als kontinuierliche Räume betrachtet werden (Aus bestimmten Gründen siehe <sequentielle warteschlange>): 🎜🎜🎜🎜Ähnlich können sequentielle doppelendige Warteschlangen eine feste Länge und eine dynamische Länge haben. Wenn die doppelendige Warteschlange voll ist, löst die sequentielle doppelendige Warteschlange mit fester Länge eine Ausnahme aus. und die dynamische sequentielle doppelendige Warteschlange beantragt dynamisch freien Speicherplatz. 🎜<h4>🎜2.1.1 Initialisierung einer doppelendigen Warteschlange🎜</h4>🎜Die Initialisierung einer sequentiellen doppelendigen Warteschlange erfordert 4 Informationen: Die <code>deque-Liste wird zum Speichern von Datenelementen verwendet, max_size wird verwendet, um die maximale Länge der
queue-Liste zu speichern, und
front und
rear werden verwendet, um den Index aufzuzeichnen des Kopfelements bzw. des Schwanzelements :🎜
class Deque:
def __init__(self, max_size=6):
self.max_size = max_size
self.deque = [None] * self.max_size
self.front = 0
self.rear = 0
Nach dem Login kopieren
2.1.2 Finden Sie die Länge der doppelendigen Warteschlange
Da front und rear verwendet werden, um den Index des Kopfelements und des Schwanzelements aufzuzeichnen Dementsprechend können wir bequem die Länge der doppelseitigen Warteschlange berechnen. Gleichzeitig müssen wir berücksichtigen, dass die doppelseitige Warteschlange eine kreisförmige Warteschlange ist und front größer als sein kann hinten und kann nicht direkt durch rear-frontcode> geleitet werden. Wir müssen die Formelberechnung verwenden, um dieses Problem zu lösen:
front 和 rear 分别用于记录队头元素和队尾元素的索引，因此我们可以方便的计算出Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange的长度；同时我们需要考虑Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange为Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange，front 可能大于 rear，不能直接通过 rear-front，我们需要利用公式计算解决此问题：
Python 实现如下：
def size(self):
return (self.rear-self.front+self.max_size) % self.max_size
Nach dem Login kopieren
2.1.3 判Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange空
根据 front 和 rear 的值可以方便的判断Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange是否为空：
def isempty(self):
return self.rear==self.front
Nach dem Login kopieren
2.1.4 判Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange满
根据 front 和 rear 的值可以方便的判断Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange是否还有空余空间：
def isfull(self):
return ((self.rear+1) % self.max_size == self.front)
Nach dem Login kopieren
2.1.5 Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange队头和队尾添加元素
添加元素时，需要首先判断Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange中是否还有空闲空间，然后根据Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange为定长顺序Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange或动态顺序Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange，添加元素操作稍有不同：
[定长顺序Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange的添加元素操作] 如果队满，则引发异常：
# 注意队头和队尾修改索引的添加元素的不同顺序
def addrear(self, data):
if not self.isfull():
self.deque[self.rear] = data
self.rear = (self.rear+1) % self.max_size else:
raise IndexError("Full Deque Exception")
def addfront(self, data):
if self.isfull():
self.resize()
if self.isempty():
# 当Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange
self.deque[self.rear] = data
self.rear = (self.rear+1) % self.max_size else:
self.front = (self.front - 1 + self.max_size) % self.max_size
self.deque[self.front] = dataNach dem Login kopieren
[动态顺序Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange的添加元素操作] 如果Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange满，则首先申请新空间，然后再执行添加操作：
def resize(self):
new_size = 2 * self.max_size
new_deque = [None] * new_size
d = new_size - self.max_size for i in range(self.max_size):
new_deque[(self.front+i+d) % new_size] = self.deque[(self.front+i) % self.max_size]
self.deque = new_deque
self.front = (self.front+d) % new_size
self.max_size = new_size
# 注意队头和队尾修改索引的添加元素的不同顺序
def addrear(self, data):
if self.isfull():
self.resize()
self.deque[self.rear] = data
self.rear = (self.rear+1) % self.max_size def addfront(self, data):
if self.isfull():
self.resize()
self.front = (self.front - 1 + self.max_size) % self.max_size
self.deque[self.front] = data
Nach dem Login kopieren
与动态顺序队列类似，我们同样需要考虑复制之后的索引，否则可能出现存在不能用的空闲空间：
添加元素的时间复杂度为O(1)。虽然当动态顺序Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange满时，原Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange中的元素需要首先复制到新Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange中，然后添加新元素，但参考《顺序表及其操作实现》中顺序表追加操作的介绍，由于 n 次添加元素操作的总时间T(n) 与O(n) 成正比，因此其摊销时间复杂度可以认为O(1)。
2.1.6 删除队头或队尾的元素
若Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange不空，则删除并返回指定端元素：
# 注意队头和队尾修改索引的删除元素的不同顺序
def removefront(self):
if not self.isempty():
result = self.deque[self.front]
self.front = (self.front+1) % self.max_size return result else:
raise IndexError("Empty Deque Exception")
def removerear(self):
if not self.isempty():
self.rear = (self.rear - 1 + self.max_size) % self.max_size
result = self.deque[self.rear]
return result else:
raise IndexError("Empty Deque Exception")Nach dem Login kopieren
2.2 链Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange的实现
Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange的另一种存储表示方式是使用链式存储结构，因此也常称为链Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange，其中 addfront 操作和 addrear 操作分别是通过在链表头部和尾部插入元素来实现的，而 removefront 操作和 removerear 操作分别是通过从头部和尾部删除结点来实现的。为了降低在尾部删除结点的时间复杂度，接下来基于双向链表实现Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange。
2.2.1 Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange结点
Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange的结点实现与双向链表并无差别：
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
def __str__(self):
return str(self.data)
Nach dem Login kopieren
2.2.2 Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange的初始化
Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange的初始化函数中，使其队头指针 front 和队尾指针 rear 均指向 None，并初始化Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange长度：
class Deque:
def __init__(self):
self.front = None
self.rear = None
self.num = 0
Nach dem Login kopieren
2.2.3 求Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange长度
返回 num 的值用于求取Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange的长度，如果没有 num 属性，则需要遍历整个链表才能得到Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange长度：
def size(self):
return self.num
Nach dem Login kopieren
2.2.4 判Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange空
根据Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange的长度可以很容易的判断其是否为空Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange：
def isempty(self):
return self.num <h4>2.2.5 添加元素</h4><p>Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange添加元素时，可以在队尾或队头插入新元素，因此需要修改 <code>rear</code> 和 <code>front</code> 指针，并且同时也要修改结点的 <code>next</code> 和 <code>previous</code></p><code>Python</code> ist wie folgt implementiert: 🎜<div class="code" style="position:relative; padding:0px; margin:0px;"><pre class="brush:php;toolbar:false"> def addrear(self, data):
node = Node(data)
# 如果添加元素前Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange为空，则添加结点时，需要将front指针也指向该结点
if self.front is None:
self.rear = node
self.front = node else:
node.previous = self.rear
self.rear.next = node
self.rear = node
self.num += 1
def addfront(self, data):
node = Node(data)
# 如果添加元素前Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange为空，则添加结点时，需要将rear指针也指向该结点
if self.rear is None:
self.front = node
self.rear = node else:
node.next = self.front
self.front.previous = node
self.front = node
self.num += 1
Nach dem Login kopieren
Nach dem Login kopieren
🎜🎜2.1.3 Feststellen, dass die Double-Ended-Warteschlange leer ist🎜🎜🎜gemäß
front und <code>rear können leicht ermittelt werden ob die doppelendige Warteschlange leer ist: 🎜
def removefront(self):
if self.isempty():
raise IndexError("Empty Queue Exception")
result = self.front.data
self.front = self.front.next
self.num -= 1
if self.isempty():
self.rear = self.front else:
# 若删除操作完成后，Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange不为空，将 front 指针的前驱指针指向 None
self.front.previous = None
return result
def removerear(self):
if self.isempty():
raise IndexError("Empty Queue Exception")
result = self.rear.data
self.rear = self.rear.previous
self.num -= 1
if self.isempty():
self.front = self.rear else:
# 若删除操作完成后，Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange不为空，将 rear 指针的后继指针指向 None
self.rear.next = None
return resultNach dem Login kopieren
Nach dem Login kopieren
🎜🎜2.1.4 Bestimmen Sie, ob die doppelendige Warteschlange voll ist🎜🎜🎜gemäß
vorne und dem Wert von
hinten kann leicht feststellen, ob in der doppelendigen Warteschlange freier Speicherplatz vorhanden ist: 🎜
# 初始化一个最大长度为5的Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlangedq = Deque(5)print('Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange空?', dq.isempty())for i in range(3):
print('队头添加元素：', 2*i)
dq.addfront(2*i)
print('队尾添加元素：', 2*i+1)
dq.addrear(2*i+1)print('Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange长度为：', dq.size())for i in range(3):
print('队尾删除元素：', dq.removerear())
print('队头删除元素：', dq.removefront())print('Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange长度为：', dq.size())Nach dem Login kopieren
Nach dem Login kopieren
🎜2.1.5 Fügen Sie Elemente zum Kopf und Ende der doppelendigen Warteschlange hinzu🎜🎜Beim Hinzufügen von Elementen müssen Sie zuerst das doppelendige Ob bestimmen In der Warteschlange ist freier Speicherplatz vorhanden. Abhängig davon, ob es sich bei der doppelendigen Warteschlange um eine sequentielle doppelendige Warteschlange mit fester Länge oder um eine dynamische sequentielle doppelendige Warteschlange handelt, unterscheidet sich die Operation zum Hinzufügen von Elementen geringfügig:
🎜 [Elementoperation der sequenziellen doppelendigen Warteschlange fester Länge hinzufügen]🎜 Wenn die Warteschlange voll ist, wird eine Ausnahme ausgelöst: 🎜
Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange空? True队头添加元素： 0队尾添加元素： 1队头添加元素： 2队尾添加元素： 3队头添加元素： 4队尾添加元素： 5Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange长度为： 6队尾删除元素： 5队头删除元素： 4队尾删除元素： 3队头删除元素： 2队尾删除元素： 1队头删除元素： 0Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange长度为： 0
Nach dem Login kopieren
Nach dem Login kopieren
🎜🎜[Elementoperation der dynamischen Sequenz-Deque hinzufügen]🎜 Wenn die Deque voll ist, ist neuer Speicherplatz vorhanden Zuerst wird ein Antrag gestellt und dann wird der Add-Vorgang ausgeführt: 🎜
# 初始化新队列dq = Deque()print('Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange空?', dq.isempty())for i in range(3):
print('队头添加元素：', i)
dq.addfront(2*i)
print('队尾添加元素：', i+3)
dq.addrear(2*i+1)print('Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange长度为：', dq.size())for i in range(3):
print('队尾删除元素：', dq.removerear())
print('队头删除元素：', dq.removefront())print('Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange长度为：', dq.size())Nach dem Login kopieren
Nach dem Login kopieren
🎜Mit dynamischer Reihenfolge Die Warteschlange ist ähnlich. Wir müssen auch den Index nach dem Kopieren berücksichtigen, da sonst möglicherweise nicht nutzbarer freier Speicherplatz vorhanden ist: 🎜🎜
🎜🎜Die zeitliche Komplexität des Hinzufügens von Elementen beträgt
O( 1). Wenn die dynamische sequentielle Doppelendwarteschlange voll ist, müssen die Elemente in der ursprünglichen Doppelendwarteschlange zwar zuerst in die neue Doppelendwarteschlange kopiert werden, und dann werden neue Elemente hinzugefügt. Beachten Sie jedoch die Einführung in die sequentielle Tabellenanhängeoperation in „Sequenztabelle und ihre Operationsimplementierung“, aufgrund der Gesamtzeit von
n Operationen zum Hinzufügen von Elementen
T ( n) und
O(n) ist proportional zur amortisierten Zeitkomplexität von ">
O span>(1). 🎜🎜🎜2.1.6 Löschen Sie das Element am Anfang oder Ende der Warteschlange🎜🎜🎜Wenn die doppelendige Warteschlange nicht leer ist, löschen Sie das angegebene Endelement und geben Sie es zurück: 🎜
Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange空? True队头添加元素： 0队尾添加元素： 3队头添加元素： 1队尾添加元素： 4队头添加元素： 2队尾添加元素： 5Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange长度为： 6队尾删除元素： 5队头删除元素： 4队尾删除元素： 3队头删除元素： 2队尾删除元素： 1队头删除元素： 0Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange长度为： 0
Nach dem Login kopieren
Nach dem Login kopieren
🎜2.2 Implementierung von Kettendoppel- beendete Warteschlange🎜
🎜Eine andere Speicherdarstellung einer doppelendigen Warteschlange ist die Verwendung einer Kettenspeicherstruktur, daher wird sie oft auch als Ketten-doppelendige Warteschlange bezeichnet, bei der die Operation
addfront und Die Operation
addrear erfolgt jeweils. Dies wird durch das Einfügen von Elementen am Kopf und Ende der verknüpften Liste erreicht, während die Operationen
removefront und
removerear implementiert sind durch Löschen von Knoten am Kopf bzw. Schwanz. Um die zeitliche Komplexität des Löschens von Knoten am Ende zu verringern, wird eine doppelendige Warteschlange basierend auf einer doppelt verknüpften Liste implementiert. 🎜🎜
🎜🎜2.2.1 Doppelt -endiger Warteschlangenknoten 🎜🎜Die Knotenimplementierung der doppelendigen Warteschlange unterscheidet sich nicht von der der doppelt verknüpften Liste: 🎜
def ispalindrome(string):
deque = Deque()
for ch in string:
deque.addfront(ch)
flag = True
while deque.size() > 1 and flag:
ch1 = deque.removefront()
ch2 = deque.removerear()
if ch1 != ch2:
flag = False
return flag
Nach dem Login kopieren
Nach dem Login kopieren
🎜2.2.2 Initialisierung der doppelendigen Warteschlange🎜🎜In der Initialisierungsfunktion der doppelendigen Warteschlange, setzen Sie ihren Kopfzeiger
front und den Warteschlangenendzeiger
rear, die beide auf
None zeigen, und initialisieren Sie die Länge der doppelendigen Warteschlange: 🎜
print('abcba是否为回文序列：', ispalindrome('abcba'))print('charaahc是否为回文序列：', ispalindrome('charaahc'))Nach dem Login kopieren
Nach dem Login kopieren
🎜2.2.3 Ermitteln Sie die Länge der doppelendigen Warteschlange. 🎜🎜return
Der Wert von num wird verwendet, um die Länge der doppelendigen Warteschlange zu ermitteln. Wenn kein
num vorhanden ist Attribut, Sie müssen die gesamte verknüpfte Liste durchlaufen, um die Länge der doppelseitigen Warteschlange zu erhalten: 🎜
abcba是否为回文序列： True
charaahc是否为回文序列： False
Nach dem Login kopieren
Nach dem Login kopieren
🎜2.2.4 Bestimmung der doppelseitigen Warteschlange Die Warteschlange ist leer🎜🎜Sie können leicht beurteilen, ob sie leer ist entsprechend der Länge der Deque: 🎜rrreee🎜2.2.5 Elemente hinzufügen🎜🎜Beim Hinzufügen von Elementen zur Deque können Sie neue Elemente am Ende oder am Kopf der Warteschlange einfügen, also am
hintencode>- und <code>front-Zeiger müssen geändert werden, und die
next- und
previous-Zeiger des Knotens müssen gleichzeitig geändert werden Die doppelseitige Warteschlange ist leer, bevor Elemente hinzugefügt werden. Sie müssen entsprechend damit umgehen: 🎜
def addrear(self, data):
node = Node(data)
# 如果添加元素前Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange为空，则添加结点时，需要将front指针也指向该结点
if self.front is None:
self.rear = node
self.front = node else:
node.previous = self.rear
self.rear.next = node
self.rear = node
self.num += 1
def addfront(self, data):
node = Node(data)
# 如果添加元素前Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange为空，则添加结点时，需要将rear指针也指向该结点
if self.rear is None:
self.front = node
self.rear = node else:
node.next = self.front
self.front.previous = node
self.front = node
self.num += 1
Nach dem Login kopieren
2.2.6 删除元素
若Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange不空，可以从删除队头或队尾元素并返回，删除操作需要更新队头指针 front 以及尾指针 rear，同时也要修改结点的 next 和 previous 指针，若出队元素尾队中最后一个结点，还需要进行相应处理：
def removefront(self):
if self.isempty():
raise IndexError("Empty Queue Exception")
result = self.front.data
self.front = self.front.next
self.num -= 1
if self.isempty():
self.rear = self.front else:
# 若删除操作完成后，Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange不为空，将 front 指针的前驱指针指向 None
self.front.previous = None
return result
def removerear(self):
if self.isempty():
raise IndexError("Empty Queue Exception")
result = self.rear.data
self.rear = self.rear.previous
self.num -= 1
if self.isempty():
self.front = self.rear else:
# 若删除操作完成后，Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange不为空，将 rear 指针的后继指针指向 None
self.rear.next = None
return resultNach dem Login kopieren
Nach dem Login kopieren
2.3 Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange的不同实现对比
Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange的不同实现对比与栈的不同实现类似，可以参考《栈及其操作实现》。
3. Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange应用
接下来，我们首先测试上述实现的Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange，以验证操作的有效性，然后利用实现的基本操作来解决实际算法问题。
3.1 顺序Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange的应用
首先初始化一个顺序Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange deque，然后测试相关操作：
# 初始化一个最大长度为5的Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlangedq = Deque(5)print('Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange空?', dq.isempty())for i in range(3):
print('队头添加元素：', 2*i)
dq.addfront(2*i)
print('队尾添加元素：', 2*i+1)
dq.addrear(2*i+1)print('Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange长度为：', dq.size())for i in range(3):
print('队尾删除元素：', dq.removerear())
print('队头删除元素：', dq.removefront())print('Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange长度为：', dq.size())Nach dem Login kopieren
Nach dem Login kopieren
测试程序输出结果如下：
Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange空? True队头添加元素： 0队尾添加元素： 1队头添加元素： 2队尾添加元素： 3队头添加元素： 4队尾添加元素： 5Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange长度为： 6队尾删除元素： 5队头删除元素： 4队尾删除元素： 3队头删除元素： 2队尾删除元素： 1队头删除元素： 0Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange长度为： 0
Nach dem Login kopieren
Nach dem Login kopieren
3.2 链Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange的应用
首先初始化一个链Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange queue，然后测试相关操作：
# 初始化新队列dq = Deque()print('Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange空?', dq.isempty())for i in range(3):
print('队头添加元素：', i)
dq.addfront(2*i)
print('队尾添加元素：', i+3)
dq.addrear(2*i+1)print('Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange长度为：', dq.size())for i in range(3):
print('队尾删除元素：', dq.removerear())
print('队头删除元素：', dq.removefront())print('Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange长度为：', dq.size())Nach dem Login kopieren
Nach dem Login kopieren
测试程序输出结果如下：
Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange空? True队头添加元素： 0队尾添加元素： 3队头添加元素： 1队尾添加元素： 4队头添加元素： 2队尾添加元素： 5Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange长度为： 6队尾删除元素： 5队头删除元素： 4队尾删除元素： 3队头删除元素： 2队尾删除元素： 1队头删除元素： 0Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange长度为： 0
Nach dem Login kopieren
Nach dem Login kopieren
3.3 利用Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange基本操作实现复杂算法
[1] 给定一字符串 string (如：abamaba)，检查其是否为回文。
使用Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange可以快速检查一字符串是否为回文序列，只需要将字符串中字符依次入队，然后从Python-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange两端依次弹出元素，对比它们是否相等：
def ispalindrome(string):
deque = Deque()
for ch in string:
deque.addfront(ch)
flag = True
while deque.size() > 1 and flag:
ch1 = deque.removefront()
ch2 = deque.removerear()
if ch1 != ch2:
flag = False
return flag
Nach dem Login kopieren
Nach dem Login kopieren
验证算法有效性：
print('abcba是否为回文序列：', ispalindrome('abcba'))print('charaahc是否为回文序列：', ispalindrome('charaahc'))Nach dem Login kopieren
Nach dem Login kopieren
结果输出如下：
abcba是否为回文序列： True
charaahc是否为回文序列： False
Nach dem Login kopieren
Nach dem Login kopieren
推荐学习：python教程
Das obige ist der detaillierte Inhalt vonPython-Datenstruktur und Algorithmus-Lernen mit doppelseitiger Warteschlange. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
