Structure de données linéaire
Dans ce chapitre, nous présenterons l'un des types de structures de données les plus fondamentaux et les plus couramment utilisés —structure de données linéaire。
Structure de données linéaireComme une rangée de personnes faisant la queue :
- Chaque personne (élément) a une relation claire d'avant et d'après
- À l'exception du premier et du dernier, chaque personne a un prédécesseur et un successeur
- Les éléments de données ont une relation linéaire un à un
Imaginez que vous faites la queue pour acheter un café, ou que vous rangez des livres sur une étagère.
Ces scénarios partagent un point commun : les éléments sont disposés les uns après les autres, formant une ligne.
En informatique, une telle collection ordonnée de données est une structure de données linéaire.
La caractéristique d'une structure de données linéaire est : à l'exception du premier et du dernier élément, chaque élément a un et un seulprédécesseuret unsuccesseur。
Structures de données linéaires courantes :
- tableau: comme une rangée de casiers numérotés, chaque casier a une position fixe
- Liste chaînée: comme une chaîne de personnes qui se tiennent par la main, chaque personne ne se souvient que des personnes devant et derrière
- Pile: comme une pile d'assiettes, les éléments ne peuvent être pris et posés que sur le dessus
- FileComme lorsqu'on fait la queue pour acheter des billets, premier arrivé, premier servi
La figure ci-dessous montre la taxonomie des structures de données linéaires. Chaque structure a ses scénarios d'application et ses caractéristiques de performance spécifiques :
La figure ci-dessous montre le processus de fonctionnement de base d'une pile, qui suit le principe LIFO (Last In, First Out) :
Tableau
Tableau statique
| Fonctionnalités | Description | Complexité temporelle |
|---|---|---|
| Accéder aux éléments | Accès direct via index | O(1) |
| Insérer un élément | Il faut décaler les éléments suivants | O(n) |
| Supprimer un élément | Il faut décaler les éléments suivants | O(n) |
| Allocation mémoire | Taille fixe, préallouée | O(1) |
Tableau dynamique
| Fonctionnalités | Description | Complexité temporelle |
|---|---|---|
| Accéder aux éléments | Accès direct via index | O(1) |
| Insérer un élément | Peut nécessiter un redimensionnement et une copie | En moyenne O(1), dans le pire des cas O(n) |
| Supprimer un élément | Il faut décaler les éléments suivants | O(n) |
| Allocation mémoire | Redimensionnement automatique | O(n) (lors du redimensionnement) |
Liste chaînée
Liste simplement chaînée
| Opération | Description | Complexité temporelle |
|---|---|---|
| Accéder aux éléments | Il faut parcourir depuis le début | O(n) |
| Insertion en tête | Insertion directe | O(1) |
| Insertion en queue | Il faut parcourir jusqu'à la queue | O(n) |
| Insertion au milieu | Il faut d'abord trouver la position | O(n) |
| Supprimer un élément | Il faut d'abord trouver la position | O(n) |
Liste doublement chaînée
| Opération | Description | Complexité temporelle |
|---|---|---|
| Accéder aux éléments | Il faut parcourir depuis la tête ou la queue | O(n) |
| Insertion en tête | Insertion directe | O(1) |
| Insertion en queue | Insertion directe (s'il y a un pointeur de queue) | O(1) |
| Insertion au milieu | Il faut d'abord trouver la position | O(n) |
| Supprimer un élément | Il faut d'abord trouver la position | O(n) |
Pile
| Opération | Description | Complexité temporelle |
|---|---|---|
| push | Ajouter un élément au sommet de la pile | O(1) |
| pop | Retirer l'élément au sommet de la pile | O(1) |
| peek(voir) | Voir l'élément au sommet de la pile | O(1) |
| isEmpty(test de vacuité) | Vérifier si la pile est vide | O(1) |
File
| Opération | Description | Complexité temporelle |
|---|---|---|
| enqueue | Ajouter un élément à la queue de la file | O(1) |
| dequeue | Retirer l'élément de tête de la file | O(1) |
| front (voir la tête de la file) | Afficher l'élément de tête de la file | O(1) |
| isEmpty(test de vacuité) | Vérifier si la file est vide | O(1) |
Diagramme de comparaison des structures de données linéaires
Tableau : un immeuble d'appartements à taille fixe pour les données
Les tableaux sont la structure de données linéaire la plus simple et la plus directe.
On peut l'imaginer comme un bâtimentUn immeuble d'appartements avec un nombre fixe d'étages。
Concepts et caractéristiques de base
- Stockage contiguUn tableau occupe un bloc contigu en mémoireContiguL'espace est comme des pièces dans un immeuble d'appartements qui sont juste à côté les unes des autres.
- Taille fixe: La capacité (longueur) d'un tableau doit être déterminée au moment de la création et ne peut généralement pas être modifiée par la suite, tout comme le nombre de pièces dans un immeuble d'appartements est fixé une fois qu'il est construit.
- Accès par index: Chaque élément (pièce) possède un numéro unique, appelé unindexDans la plupart des langages de programmation, l'indexation commence à
0À partir de. Vous pouvez accéder directement et rapidement à n'importe quel élément via son index, avec une complexité temporelle deO(1)。
Opérations essentielles et exemples de code
Démontrons les tableaux avec Python (en Python, on utilise généralementlistpour simuler, mais notez que celui de Pythonlistqui est dynamique) opérations de base.
Exemple
# 1. Créer un tableau
apartment_building = ['Chambre 101 - Zhang San', 'Chambre 102 - Li Si', 'Chambre 103 - Wang Wu', 'Chambre 104 - libre', 'Chambre 105 - libre']
print("Résidents de l'immeuble :", apartment_building)
# 2. Accéder aux éléments (par index)
# Accéder à la chambre 102
tenant = apartment_building[1] # L'index commence à 0, donc 1 correspond au deuxième élément
print(f"Le résident de la chambre 102 est : {tenant}")
# 3. Mettre à jour les éléments
# Un nouveau résident Zhao Liu a emménagé dans la chambre 104
apartment_building[3] = 'Chambre 104 - Zhao Liu'
print("Après l'emménagement de Zhao Liu :", apartment_building)
# 4. Insérer des éléments (l'ajout à la fin est relativement efficace, simulant une "expansion")
# Supposons que nous ayons le droit d'ajouter une chambre 106 à la fin
apartment_building.append('Chambre 106 - Sun Qi')
print("Après l'ajout de la chambre 106 :", apartment_building)
# 5. Supprimer des éléments
# Wang Wu a quitté la chambre 103
# Méthode 1 : Marquer comme vacant (suppression logique)
# apartment_building[2] = 'Chambre 103 - vacante'
# Méthode 2 : Supprimer l'élément ; les éléments suivants doivent être décalés vers l'avant (suppression physique, relativement inefficace)
removed_tenant = apartment_building.pop(2) # Supprimer l'élément à l'indice 2
print(f"{removed_tenant} a déménagé.")
print("Après le départ de Wang Wu :", apartment_building)
apartment_building = ['Chambre 101 - Zhang San', 'Chambre 102 - Li Si', 'Chambre 103 - Wang Wu', 'Chambre 104 - libre', 'Chambre 105 - libre']
print("Résidents de l'immeuble :", apartment_building)
# 2. Accéder aux éléments (par index)
# Accéder à la chambre 102
tenant = apartment_building[1] # L'index commence à 0, donc 1 correspond au deuxième élément
print(f"Le résident de la chambre 102 est : {tenant}")
# 3. Mettre à jour les éléments
# Un nouveau résident Zhao Liu a emménagé dans la chambre 104
apartment_building[3] = 'Chambre 104 - Zhao Liu'
print("Après l'emménagement de Zhao Liu :", apartment_building)
# 4. Insérer des éléments (l'ajout à la fin est relativement efficace, simulant une "expansion")
# Supposons que nous ayons le droit d'ajouter une chambre 106 à la fin
apartment_building.append('Chambre 106 - Sun Qi')
print("Après l'ajout de la chambre 106 :", apartment_building)
# 5. Supprimer des éléments
# Wang Wu a quitté la chambre 103
# Méthode 1 : Marquer comme vacant (suppression logique)
# apartment_building[2] = 'Chambre 103 - vacante'
# Méthode 2 : Supprimer l'élément ; les éléments suivants doivent être décalés vers l'avant (suppression physique, relativement inefficace)
removed_tenant = apartment_building.pop(2) # Supprimer l'élément à l'indice 2
print(f"{removed_tenant} a déménagé.")
print("Après le départ de Wang Wu :", apartment_building)
Sortie :
寓楼住户情况： ['101室-张三', '102室-李四', '103室-王五', '104室-空置', '105室-空置'] 102室的住户是：102室-李四 赵六入住后： ['101室-张三', '102室-李四', '103室-王五', '104室-赵六', '105室-空置'] 加盖106室后： ['101室-张三', '102室-李四', '103室-王五', '104室-赵六', '105室-空置', '106室-孙七'] 103室-王五 已搬走。 王五搬走后： ['101室-张三', '102室-李四', '104室-赵六', '105室-空置', '106室-孙七']
Avantages et inconvénients
| Avantages | Inconvénients |
|---|---|
| Accès aléatoire rapide: On peut accéder à n'importe quel élément en temps constant via son indice. | Taille fixe: Une fois qu'un tableau statique est créé, sa capacité est difficile à modifier. |
| Efficacité mémoire élevée: Stockage contigu, aucun espace supplémentaire nécessaire pour stocker les relations entre les éléments. | Coût élevé d'insertion/suppression: L'insertion ou la suppression d'éléments au milieu nécessite de décaler de nombreux éléments suivants pour maintenir la contiguïté. |
Liste chaînée : un train de chasse au trésor pour les données
Lorsque la taille fixe des tableaux et l'inefficacité de l'insertion/suppression deviennent problématiques, les listes chaînées entrent en scène. Une liste chaînée est comme un trainTrain, chaque wagon (nœud) transporte un chargement (données) et est relié au wagon suivant par un attelage (pointeur).
Concepts de base et types
Chaque nœud de la liste chaînéenœudContient au moins deux parties :
- Champ de donnéesStocke la valeur réelle de la donnée.
- Champ pointeur: stocke l'adresse du nœud suivant en mémoire.
La figure ci-dessus montre une structure deliste simplement chaînée. Le pointeur de tête pointe vers le premier nœud, et chaque nœud a unNextpointeur qui pointe vers le nœud suivant, et celui du dernier nœudNextPointe versNULLMarque la fin de la liste chaînée.
Principaux types de listes chaînées :
- Liste simplement chaînéeLe nœud pointe uniquement vers le nœud suivant.
- Liste doublement chaînée: les nœuds pointent à la fois vers le nœud précédent et le nœud suivant, permettant un parcours bidirectionnel.
- Liste chaînée circulaire: le nœud de queue pointe vers le nœud de tête, formant un anneau.
Opérations essentielles et exemples de code
Implémentons une liste simplement chaînée simple.
Exemple
class ListNode:
"""Définit la classe de nœud de liste chaînée"""
def __init__(self, data):
self.data = data # Champ de données
self.next = None # Champ pointeur, pointe initialement vers null
class LinkedList:
"""Définir une classe de liste simplement chaînée"""
def __init__(self):
self.head = None # Pointeur de tête de la liste chaînée
def append(self, data):
"""Ajouter un nœud à la fin de la liste chaînée"""
new_node = ListNode(data)
if not self.head: # Si la liste chaînée est vide, le nouveau nœud devient le nœud de tête
self.head = new_node
return
last_node = self.head
while last_node.next: # Parcourir jusqu'au dernier nœud
last_node = last_node.next
last_node.next = new_node # Attacher le nouveau nœud à la fin
def prepend(self, data):
"""Ajouter un nœud en tête de la liste chaînée"""
new_node = ListNode(data)
new_node.next = self.head
self.head = new_node
def delete(self, key):
"""Supprimer le premier nœud ayant la valeur key"""
current_node = self.head
# Si le nœud à supprimer est le nœud de tête
if current_node and current_node.data == key:
self.head = current_node.next
current_node = None
return
prev_node = None
# Parcourir pour trouver le nœud à supprimer
while current_node and current_node.data != key:
prev_node = current_node
current_node = current_node.next
if current_node is None: # Non trouvé
return
# Une fois trouvé, contourner le nœud pour connecter
prev_node.next = current_node.next
current_node = None
def print_list(self):
"""Affiche tous les éléments de la liste chaînée"""
current_node = self.head
while current_node:
print(current_node.data, end=" -> ")
current_node = current_node.next
print("NULL")
# Tester la liste chaînée
print("=== Démo des opérations de liste simplement chaînée ===")
train = LinkedList()
train.append("Wagon 1 - Charbon")
train.append("Wagon 2 - Bois")
train.prepend("Locomotive") # Ajouter en tête
train.append("Wagon 3 - Acier")
print("Train initial :")
train.print_list() # Sortie : Locomotive -> Wagon 1 - Charbon -> Wagon 2 - Bois -> Wagon 3 - Acier -> NULL
train.delete("Wagon 2 - Bois")
print("Après déchargement du bois :")
train.print_list() # Output: locomotive -> carriage1-coal -> carriage3-steel -> NULL
"""Définit la classe de nœud de liste chaînée"""
def __init__(self, data):
self.data = data # Champ de données
self.next = None # Champ pointeur, pointe initialement vers null
class LinkedList:
"""Définir une classe de liste simplement chaînée"""
def __init__(self):
self.head = None # Pointeur de tête de la liste chaînée
def append(self, data):
"""Ajouter un nœud à la fin de la liste chaînée"""
new_node = ListNode(data)
if not self.head: # Si la liste chaînée est vide, le nouveau nœud devient le nœud de tête
self.head = new_node
return
last_node = self.head
while last_node.next: # Parcourir jusqu'au dernier nœud
last_node = last_node.next
last_node.next = new_node # Attacher le nouveau nœud à la fin
def prepend(self, data):
"""Ajouter un nœud en tête de la liste chaînée"""
new_node = ListNode(data)
new_node.next = self.head
self.head = new_node
def delete(self, key):
"""Supprimer le premier nœud ayant la valeur key"""
current_node = self.head
# Si le nœud à supprimer est le nœud de tête
if current_node and current_node.data == key:
self.head = current_node.next
current_node = None
return
prev_node = None
# Parcourir pour trouver le nœud à supprimer
while current_node and current_node.data != key:
prev_node = current_node
current_node = current_node.next
if current_node is None: # Non trouvé
return
# Une fois trouvé, contourner le nœud pour connecter
prev_node.next = current_node.next
current_node = None
def print_list(self):
"""Affiche tous les éléments de la liste chaînée"""
current_node = self.head
while current_node:
print(current_node.data, end=" -> ")
current_node = current_node.next
print("NULL")
# Tester la liste chaînée
print("=== Démo des opérations de liste simplement chaînée ===")
train = LinkedList()
train.append("Wagon 1 - Charbon")
train.append("Wagon 2 - Bois")
train.prepend("Locomotive") # Ajouter en tête
train.append("Wagon 3 - Acier")
print("Train initial :")
train.print_list() # Sortie : Locomotive -> Wagon 1 - Charbon -> Wagon 2 - Bois -> Wagon 3 - Acier -> NULL
train.delete("Wagon 2 - Bois")
print("Après déchargement du bois :")
train.print_list() # Output: locomotive -> carriage1-coal -> carriage3-steel -> NULL
Sortie :
=== 单向链表操作演示 === 初始列车： 车头 -> 车厢1-煤炭 -> 车厢2-木材 -> 车厢3-钢材 -> NULL 卸下木材后： 车头 -> 车厢1-煤炭 -> 车厢3-钢材 -> NULL
Avantages et inconvénients
| Avantages | Inconvénients |
|---|---|
| Taille dynamique: Pas besoin de préallouer un espace fixe ; elle peut s'agrandir et se réduire de manière flexible. | Surcharge mémoire: Chaque nœud nécessite un espace supplémentaire pour stocker un pointeur. |
| Insertion/suppression efficaces: Lorsque la position d'un nœud est connue, il suffit de modifier les pointeurs sans déplacer de nombreux éléments. | Accès séquentiel: Contrairement aux tableaux, on ne peut pas accéder directement aux éléments par indice ; il faut parcourir depuis la tête. |
| Peu adapté au cache: Les nœuds sont dispersés en mémoire, ce qui n'est pas propice à la prélecture du cache CPU. |
Pile : des assiettes empilées pour les données
Une pile est une structure de donnéesdernier entré, premier sorti (Last-in, first-out), comme des assiettes empilées dans un restaurant ; on prend toujours celle du dessus (la dernière posée).
Concepts et opérations de base
La pile n'autorise les opérations qu'à une seule extrémité (appeléesommet de la pile) pour insérer (Push) et supprimer (Pop) opérations. L'autre extrémité est appeléebas de la pile。
Opérations essentielles :
- push(data)Empile les données au sommet de la pile.
- pop()Dépile et renvoie l'élément au sommet de la pile.
- peek() / top()Consulte l'élément au sommet de la pile sans le dépiler.
- is_empty()Vérifie si la pile est vide.
Scénarios d'application et exemples de code
Les piles sont extrêmement largement utilisées en informatique, par ex. les piles d'appels de fonctions, la navigation avant/arrière du navigateur, l'évaluation d'expressions, la correspondance des parenthèses, etc.
Exemple
class Stack:
"""Utiliser une liste pour implémenter une pile"""
def __init__(self):
self.items = []
def push(self, item):
"""Empiler"""
self.items.append(item) # Utiliser la fin de la liste comme sommet de la pile
def pop(self):
"""Pop, renvoie None si la pile est vide"""
if not self.is_empty():
return self.items.pop()
return None
def peek(self):
"""Consulte l'élément au sommet"""
if not self.is_empty():
return self.items[-1]
return None
def is_empty(self):
"""Vérifie si la pile est vide"""
return len(self.items) == 0
def size(self):
"""Renvoie la taille de la pile"""
return len(self.items)
# Exemple d'application : vérification de correspondance des parenthèses
def is_balanced_parentheses(expression):
"""
Vérifie si les parenthèses dans l'expression correspondent
Par exemple : (()) est équilibré, (() est déséquilibré
"""
stack = Stack()
# Correspondance des parenthèses
matching_bracket = {')': '(', ']': '[', '}': '{'}
for char in expression:
if char in '([{': # Si c'est une parenthèse ouvrante, empiler sur la pile
stack.push(char)
elif char in ')]}': # Si c'est une parenthèse fermante
if stack.is_empty():
return False # Pile vide, donc il y a trop de crochets fermants
top_char = stack.pop()
if matching_bracket[char] != top_char: # Vérifier s'ils correspondent
return False
# Après la boucle, la pile doit être vide
return stack.is_empty()
# Tester la pile et la correspondance des crochets
print("\n=== Démo de correspondance de pile et de crochets ===")
plate_stack = Stack()
plate_stack.push("Assiette 1")
plate_stack.push("Assiette 2")
plate_stack.push("Assiette 3")
print(f"Retirez l'assiette du dessus : {plate_stack.pop()}") # Sortie : Assiette 3
print(f"Maintenant, l'assiette du haut est : {plate_stack.peek()}") # Sortie : Assiette 2
# Tester la correspondance des parenthèses
test_cases = ["((1+2)*3)", "({[ ]})", "((())", ")( )"]
for test in test_cases:
result = balanced if is_balanced_parentheses(test) else unbalanced
print(fLes parenthèses dans l'expression '{test}' sont {result}.)
"""Utiliser une liste pour implémenter une pile"""
def __init__(self):
self.items = []
def push(self, item):
"""Empiler"""
self.items.append(item) # Utiliser la fin de la liste comme sommet de la pile
def pop(self):
"""Pop, renvoie None si la pile est vide"""
if not self.is_empty():
return self.items.pop()
return None
def peek(self):
"""Consulte l'élément au sommet"""
if not self.is_empty():
return self.items[-1]
return None
def is_empty(self):
"""Vérifie si la pile est vide"""
return len(self.items) == 0
def size(self):
"""Renvoie la taille de la pile"""
return len(self.items)
# Exemple d'application : vérification de correspondance des parenthèses
def is_balanced_parentheses(expression):
"""
Vérifie si les parenthèses dans l'expression correspondent
Par exemple : (()) est équilibré, (() est déséquilibré
"""
stack = Stack()
# Correspondance des parenthèses
matching_bracket = {')': '(', ']': '[', '}': '{'}
for char in expression:
if char in '([{': # Si c'est une parenthèse ouvrante, empiler sur la pile
stack.push(char)
elif char in ')]}': # Si c'est une parenthèse fermante
if stack.is_empty():
return False # Pile vide, donc il y a trop de crochets fermants
top_char = stack.pop()
if matching_bracket[char] != top_char: # Vérifier s'ils correspondent
return False
# Après la boucle, la pile doit être vide
return stack.is_empty()
# Tester la pile et la correspondance des crochets
print("\n=== Démo de correspondance de pile et de crochets ===")
plate_stack = Stack()
plate_stack.push("Assiette 1")
plate_stack.push("Assiette 2")
plate_stack.push("Assiette 3")
print(f"Retirez l'assiette du dessus : {plate_stack.pop()}") # Sortie : Assiette 3
print(f"Maintenant, l'assiette du haut est : {plate_stack.peek()}") # Sortie : Assiette 2
# Tester la correspondance des parenthèses
test_cases = ["((1+2)*3)", "({[ ]})", "((())", ")( )"]
for test in test_cases:
result = balanced if is_balanced_parentheses(test) else unbalanced
print(fLes parenthèses dans l'expression '{test}' sont {result}.)
Sortie :
=== 栈与括号匹配演示 ===
取出最上面的盘子: 盘子3
现在最上面的盘子是: 盘子2
表达式 '((1+2)*3)' 的括号是 平衡 的。
表达式 '({[ ]})' 的括号是 平衡 的。
表达式 '((())' 的括号是 不平衡 的。
表达式 ')( )' 的括号是 不平衡 的。
File : un canal de file d'attente pour les données
Une file est unepremier entré, premier sortiUne structure de données, comme tout endroit de la vie où l'on doit faire la queue (par ex., la caisse d'un supermarché), les personnes qui arrivent en premier sont servies en premier.
Concepts et opérations de base
La file permet des opérations à une extrémité (appeléequeue) pour insérer (Enqueue) des opérations, et à l'autre extrémité (appeléetête) pour supprimer (Dequeue) l'opération.
Opérations essentielles :
- enqueue(data)Ajouter des données à la queue de la file.
- dequeue()Supprimer et renvoyer les données de la tête de la file.
- front() / peek()Voir la donnée en tête de la file sans la retirer.
- is_empty()Vérifier si la file est vide.
Scénarios d'application et exemples de code
Les files sont souvent utilisées dans des scénarios où les tâches doivent être traitées dans l’ordre, comme : les files de travaux d’impression, les files de messages, la recherche en largeur d’abord, etc.
Exemple
from collections import deque # Utiliser deque de Python, qui offre des opérations efficaces en tête et en queue
class Queue:
"""Implémenter une file à l'aide de collections.deque"""
def __init__(self):
self.items = deque()
def enqueue(self, item):
"""Mettre en file"""
self.items.append(item) # Ajouter depuis la droite (queue)
def dequeue(self):
"""Défiler, renvoyer None si la file est vide"""
if not self.is_empty():
return self.items.popleft() # Retirer depuis la gauche (tête)
return None
def front(self):
"""Consulter l'élément de tête"""
if not self.is_empty():
return self.items[0]
return None
def is_empty(self):
"""Vérifier si la file est vide"""
return len(self.items) == 0
def size(self):
"""Retourner la taille de la file"""
return len(self.items)
# Exemple d'application : simulation de tâches d'impression
print("\n=== Simulation de file d'attente et de tâches d'impression ===)
printer_queue = Queue()
# Simuler l'arrivée de trois tâches d'impression
tasks = ["Alice's resume.pdf", "Bob's report.doc", "Charlie's chart.png"]
for task in tasks:
printer_queue.enqueue(task)
print(f"La tâche '{task}' a été ajoutée à la file d'impression.")
# Traiter les tâches d'impression
print("\nDébut de l'impression...)
while not printer_queue.is_empty():
current_task = printer_queue.dequeue()
print(f"Impression : {current_task}")
# Simuler le temps d'impression
print("Toutes les tâches d'impression ont été terminées.")
class Queue:
"""Implémenter une file à l'aide de collections.deque"""
def __init__(self):
self.items = deque()
def enqueue(self, item):
"""Mettre en file"""
self.items.append(item) # Ajouter depuis la droite (queue)
def dequeue(self):
"""Défiler, renvoyer None si la file est vide"""
if not self.is_empty():
return self.items.popleft() # Retirer depuis la gauche (tête)
return None
def front(self):
"""Consulter l'élément de tête"""
if not self.is_empty():
return self.items[0]
return None
def is_empty(self):
"""Vérifier si la file est vide"""
return len(self.items) == 0
def size(self):
"""Retourner la taille de la file"""
return len(self.items)
# Exemple d'application : simulation de tâches d'impression
print("\n=== Simulation de file d'attente et de tâches d'impression ===)
printer_queue = Queue()
# Simuler l'arrivée de trois tâches d'impression
tasks = ["Alice's resume.pdf", "Bob's report.doc", "Charlie's chart.png"]
for task in tasks:
printer_queue.enqueue(task)
print(f"La tâche '{task}' a été ajoutée à la file d'impression.")
# Traiter les tâches d'impression
print("\nDébut de l'impression...)
while not printer_queue.is_empty():
current_task = printer_queue.dequeue()
print(f"Impression : {current_task}")
# Simuler le temps d'impression
print("Toutes les tâches d'impression ont été terminées.")
Sortie :
=== 队列与打印任务模拟 === 任务 'Alice的简历.pdf' 已加入打印队列。 任务 'Bob的报告.doc' 已加入打印队列。 任务 'Charlie的图表.png' 已加入打印队列。 开始打印... 正在打印: Alice的简历.pdf 正在打印: Bob的报告.doc 正在打印: Charlie的图表.png 所有打印任务已完成。
Résumé et comparaison
Nous avons appris quatre structures de données linéaires de base. Le tableau ci-dessous vous aide à examiner et à comparer rapidement leurs caractéristiques principales :
| Fonctionnalités | array | Liste chaînée | Pile | File |
|---|---|---|---|---|
| Méthode de stockage | Mémoire contiguë | Mémoire dispersée, reliée par des pointeurs | Implémentée à partir de tableaux ou de listes chaînées | Implémentée à partir de tableaux ou de listes chaînées |
| Mode d'accès | Accès aléatoire (via un index) | Accès séquentiel (nécessite un parcours) | Limité au sommet de la pile (LIFO) | Limité à la tête de la file (FIFO) |
| Efficacité d'insertion/suppression | Rapide à la queue, lent au milieu/à la tête (nécessite de décaler les éléments) | Rapide lorsque la position est connue (il suffit de modifier les pointeurs) | Opérations au sommet de la pile, O(1) | Enfiler à la queue, défiler à la tête, O(1) |
| Size | Fixe (tableau statique) | Dynamique | Dynamique | Dynamique |
| Applications principales | Recherche rapide, collection de taille fixe | Insertions/suppressions fréquentes, taille incertaine | Appels de fonction, backtracking, correspondance de parenthèses | Ordonnancement des tâches, tamponnage, BFS |
Comment choisir ?
- nécessiteUn accès aléatoire rapideet lorsque la quantité de données est connue, choisissezun tableau。
- nécessiteInsertion ou suppression fréquente à des positions arbitrairesd'éléments, et lorsque la quantité de données varie considérablement, choisissezune liste chaînée。
- Besoin d'implémenter"Annuler"fonction outraitement inverselorsqu'en séquence, envisagezPile。
- Besoin d'appliquer"Premier arrivé, premier servi"lors du traitement des tâches dans l'ordre, utilisezFile。