Pile et file d'attente || Python || Structures de données et algorithmes

Empiler

Stack - Il s'agit d'un conteneur de stockage qui prend en charge la récupération par ordre du dernier entré, premier sorti (LIFO). Les piles sont probablement le bon conteneur à utiliser lorsque l’ordre de récupération n’a aucune importance, par exemple lors du traitement de tâches par lots.

Par exemple, considérons une pile d'assiettes utilisée dans les cafétérias : l'ordre dans lequel les assiettes sont retirées de la pile est l'inverse de l'ordre dans lequel elles ont été ajoutées, car seule l'assiette supérieure est accessible .

L'opération INSERT sur une pile est souvent appelée PUSH, et l'opération DELETE, qui ne prend pas d'argument d'élément, est souvent appelée POP.

Push (x,s) : Insérez l'élément x en haut de la pile s.

Pop(s) : Renvoie (et supprime) l'élément supérieur de la pile s.

Les aliments insérés dans mon réfrigérateur sortent généralement de la même manière, malgré l'incitation des dates de péremption. Sur le plan algorithmique, LIFO a tendance à se produire au cours de l'exécution d'algorithmes récursifs.

Applications de Stack -

1. Appels de fonction : Utilisés pour gérer l'exécution et la récursivité des fonctions.
2. Opérations d'annulation : Suit les modifications dans les éditeurs pour "Annuler/Rétablir".
3. Historique du navigateur : Stocke les pages visitées pour un retour en arrière.
4. Analyse d'expression : Évalue et convertit les expressions mathématiques.
5. Validation de la syntaxe : Correspond aux parenthèses ou aux balises dans le code.
6. Gestion de la mémoire : Gère les piles d'appels pendant l'exécution du programme.
7. DFS : Implémente la recherche en profondeur d'abord dans les algorithmes graphiques.

Implémenter la pile à l'aide d'un tableau -

• push() - Insérer un élément dans la pile
• pop() - Supprimer un élément de la pile
• top() - Renvoie l'élément supérieur de la pile.
• isEmpty() - Renvoie vrai si la pile est vide sinon faux.

class Stack:
    def __init__(self):
        #Initializes an empty stack 
        self.stack = []

    def isEmpty(self) -> bool:
        #Returns True if the stack is empty, False otherwise.

        return len(self.stack) == 0

    def push(self, item) -> None:
        #Pushes an item onto the stack.
        self.stack.append(item)

    def pop(self):
        #Removes and returns the top item from the stack.
        if self.isEmpty():
            return None
        return self.stack.pop()

    def peek(self):
        #Returns the top item from the stack without removing it.
        if self.isEmpty():
            return None
        return self.stack[-1]

File d'attente

File d'attente - Il s'agit d'un conteneur de stockage qui prend en charge la récupération par ordre premier entré, premier sorti (FIFO). Nous appelons l'opération INSERT sur une file d'attente ENQUEUE, et nous appelons l'opération DELETE DEQUEUE. Comme l'opération de pile POP, DEQUEUE ne prend aucun argument d'élément. Les piles et les files d'attente sont des ensembles dynamiques dans lesquels l'élément supprimé de l'ensemble par l'opération DELETE est prédéfini.

Enqueue(x,q): Insérez l'élément x à la fin de la file d'attente q.

Dequeue(q): Renvoie (et supprime) l'élément de premier plan de la file d'attente q.

La file d'attente a une tête et une queue.

• Lorsqu'un élément est mis en file d'attente, il prend sa place en queue de file, tout comme un client nouvellement arrivé prend place en fin de file.

• L'élément sorti de la file d'attente est toujours celui en tête de file, comme le client en tête de file, qui a attendu le plus longtemps.

Applications de file d'attente -

1. Planification des tâches : Gère les processus et les tâches du processeur dans l'ordre.
2. BFS : Implémente la recherche en largeur d'abord dans les graphiques.
3. Files d'attente d'impression : Gère les tâches d'impression de manière séquentielle.
4. Routage réseau : Met en mémoire tampon les paquets de données pour la transmission.
5. Centres d'appels : Gère les appels des clients en ordre d'attente.
6. Streaming : Met en mémoire tampon les flux vidéo ou audio en temps réel.
7. Événements d'entrée : Traite les entrées du clavier et de la souris dans les systèmes GUI.

Implémenter la file d'attente à l'aide d'un tableau-

• enqueue() – Insertion d'éléments dans la file d'attente.
• dequeue() – Suppression d'éléments de la file d'attente.
• peek() ou front()- Acquiert l'élément de données disponible au nœud avant de la file d'attente sans le supprimer.
• isEmpty() – Vérifie si la file d'attente est vide.

class Stack:
    def __init__(self):
        #Initializes an empty stack 
        self.stack = []

    def isEmpty(self) -> bool:
        #Returns True if the stack is empty, False otherwise.

        return len(self.stack) == 0

    def push(self, item) -> None:
        #Pushes an item onto the stack.
        self.stack.append(item)

    def pop(self):
        #Removes and returns the top item from the stack.
        if self.isEmpty():
            return None
        return self.stack.pop()

    def peek(self):
        #Returns the top item from the stack without removing it.
        if self.isEmpty():
            return None
        return self.stack[-1]

Implémenter la file d'attente à l'aide de Stacks -

• push(x) - Déplacez tous les éléments de la pile 1 à la pile 2 pour inverser leur ordre, puis déplacez à nouveau tous les éléments de la pile 2 à la pile 1.
• pop() - Supprime l'élément du début de la file d'attente et le renvoie
• peek() - Renvoie l'élément en début de file d'attente
• empty() - Renvoie vrai si la file d'attente est vide, faux sinon

class MyQueue:
    def __init__(self):
        # Store elements
        self.queue = []
        # A pointer to indicate the start position
        self.p_start = 0

    def enQueue(self, x):
        #Insert an element into the queue. 
        self.queue.append(x)
        return True # Return True if the operation is successful

    def deQueue(self):
        #Delete an element from the queue. 
        if self.isEmpty():
            return False
        self.p_start += 1
        return True #Return True if the operation is successful

    def Front(self):
        #Get the front item from the queue.
        if not self.isEmpty():
            return self.queue[self.p_start]
        return None  # Return None if the queue is empty

    def isEmpty(self):
        #Checks whether the queue is empty or not
        return self.p_start >= len(self.queue)

Implémenter la pile à l'aide de files d'attente -

• push(x) - Ajoutez un nouvel élément à la deuxième file d'attente, puis déplacez tous les éléments de la file d'attente 1 vers la file d'attente 2 pour maintenir l'ordre de la pile (LIFO) et échangez les files d'attente.
• pop() - Supprime l'élément en haut de la pile et le renvoie
• peek ou top() - Renvoie l'élément en début de file d'attente
• empty() - Renvoie vrai si la file d'attente est vide, faux sinon

class MyQueue:

    def __init__(self):
        self.stack_1 = []  # Main stack for enqueue operations
        self.stack_2 = []  # Temporary stack for dequeue operations
        self.front = None

    # Pushes element x to the back of the queue.
    def push(self, x):

        # Move all elements from stack1 to stack 2 to reverse their order
        while self.stack_1:
            self.stack_2.append(self.stack_1.pop())
        self.stack_2.append(x)

        # Move all elements back from stack2 to stack 1 as a queue
        while self.stack_2:
            self.stack_1.append(self.stack_2.pop())

    # Removes the element from the front of the queue and returns it
    def pop(self):
        return self.stack_1.pop()

    # Returns the element at the front of the queue
    def peek(self):
        return self.stack_1[-1]

    # Returns true if the queue is empty, false otherwise
    def empty(self):
        return not self.stack_1

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!