Comment implémenter la structure de données de la technologie sous-jacente de Python

Comment implémenter la structure de données de la technologie sous-jacente de Python

La structure des données est une partie très importante de l'informatique. Elle est utilisée pour organiser et stocker les données afin qu'elles puissent être manipulées et accessibles efficacement. En tant que langage de programmation de haut niveau, Python fournit une multitude de structures de données intégrées, telles que des listes, des tuples, des dictionnaires, etc., mais nous devons parfois également implémenter certaines structures de données sous-jacentes pour répondre à des besoins spécifiques.

Cet article expliquera comment utiliser Python pour implémenter plusieurs structures de données sous-jacentes courantes, notamment les piles, les files d'attente et les listes chaînées, et fournira des exemples de code correspondants.

1. Stack

La pile est une structure de données dernier entré, premier sorti (LIFO) qui autorise uniquement les opérations d'insertion (push) et de suppression (pop) en haut de la pile. En Python, vous pouvez utiliser des listes pour implémenter une pile simple.

class Stack:
    def __init__(self):
        self.items = []

    def is_empty(self):
        return len(self.items) == 0

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if not self.is_empty():
            return self.items.pop()

    def peek(self):
        if not self.is_empty():
            return self.items[-1]

    def size(self):
        return len(self.items)

Utilisez la classe Stack pour créer un objet pile et effectuer des opérations :

stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.size())    # 输出：3
print(stack.pop())     # 输出：3
print(stack.peek())    # 输出：2
print(stack.is_empty())     # 输出：False

2. Queue (Queue)

Queue est une structure de données premier entré, premier sorti (FIFO) qui permet uniquement l'insertion (mise en file d'attente) à l'opération de fin de file d'attente, effectue une opération de retrait de file d'attente en tête de la file d'attente. Vous pouvez utiliser des listes pour implémenter une file d'attente simple en Python.

class Queue:
    def __init__(self):
        self.items = []

    def is_empty(self):
        return len(self.items) == 0

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        if not self.is_empty():
            return self.items.pop(0)

    def size(self):
        return len(self.items)

Utilisez la classe Queue pour créer un objet file d'attente et effectuer des opérations :

queue = Queue()
queue.enqueue('a')
queue.enqueue('b')
queue.enqueue('c')
print(queue.size())    # 输出：3
print(queue.dequeue())     # 输出：'a'
print(queue.is_empty())    # 输出：False

3. Liste chaînée

Une liste chaînée est une structure de données dynamique composée d'une série de nœuds, chaque nœud contient deux parties : des données et un pointeur. au nœud suivant. En Python, vous pouvez utiliser des classes pour implémenter une simple liste chaînée.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def is_empty(self):
        return self.head is None

    def add_node(self, data):
        new_node = Node(data)
        if self.is_empty():
            self.head = new_node
        else:
            current_node = self.head
            while current_node.next:
                current_node = current_node.next
            current_node.next = new_node

    def remove_node(self, data):
        if not self.is_empty():
            current_node = self.head
            if current_node.data == data:
                self.head = current_node.next
            else:
                while current_node.next:
                    if current_node.next.data == data:
                        current_node.next = current_node.next.next
                        break
                    current_node = current_node.next

    def get_size(self):
        size = 0
        current_node = self.head
        while current_node:
            size += 1
            current_node = current_node.next
        return size

Utilisez la classe LinkedList pour créer un objet de liste chaînée et effectuer des opérations :

linked_list = LinkedList()
print(linked_list.is_empty())    # 输出：True

linked_list.add_node(1)
linked_list.add_node(2)
linked_list.add_node(3)
print(linked_list.get_size())    # 输出：3

linked_list.remove_node(2)
print(linked_list.get_size())    # 输出：2

À travers les exemples de code ci-dessus, nous montrons comment utiliser Python pour implémenter des structures de données sous-jacentes courantes telles que des piles, des files d'attente et des listes chaînées. Ces structures de données sont largement utilisées dans les algorithmes et le traitement des données. La maîtrise de leurs principes de mise en œuvre et de leurs méthodes d'utilisation est très importante pour améliorer davantage les capacités de programmation.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!