Stapel und Warteschlange || Python || Datenstrukturen und Algorithmen

Stapel

Stapel - Es handelt sich um einen Lagerbehälter, der die Entnahme nach der LIFO-Reihenfolge (Last-In, First-Out) unterstützt. Stapel sind wahrscheinlich der richtige Container, wenn die Abrufreihenfolge überhaupt keine Rolle spielt, beispielsweise bei der Verarbeitung von Batch-Jobs.

Stellen Sie sich zum Beispiel einen Tellerstapel vor, der in Kantinen verwendet wird: Die Reihenfolge, in der die Teller aus dem Stapel entnommen werden, ist umgekehrt zur Reihenfolge, in der sie hinzugefügt wurden, da nur der oberste Teller zugänglich ist .

Die INSERT-Operation auf einem Stapel wird oft als PUSH bezeichnet, und die DELETE-Operation, die kein Elementargument akzeptiert, wird oft als POP bezeichnet.

Push (x,s):Element x oben in Stapel s einfügen.

Pop(s) : Das oberste Element des Stapels zurückgeben (und entfernen) s.

In meinen Kühlschrank eingelegte Lebensmittel werden trotz der Anreize durch das Verfallsdatum normalerweise auf die gleiche Weise wieder ausgegeben. Algorithmisch gesehen geschieht LIFO tendenziell im Zuge der Ausführung rekursiver Algorithmen.

Anwendungen von Stack -

1. Funktionsaufrufe:Wird zur Verwaltung der Funktionsausführung und Rekursion verwendet.
2. Vorgänge rückgängig machen: Verfolgt Änderungen in Editoren für „Rückgängig/Wiederherstellen“.
3. Browserverlauf: Speichert besuchte Seiten zum Zurückverfolgen.
4. Ausdrucksanalyse:Bewertet und konvertiert mathematische Ausdrücke.
5. Syntaxvalidierung: Entspricht Klammern oder Tags im Code.
6. Speicherverwaltung: Verwaltet Aufrufstapel während der Programmausführung.
7. DFS: Implementiert die Tiefensuche in Diagrammalgorithmen.

Stack mit Array implementieren -

• push() – Füge ein Element in den Stapel ein
• pop() – Entferne ein Element vom Stapel
• top() – Gibt das oberste Element des Stapels zurück.
• isEmpty() – Gibt „true“ zurück, wenn der Stapel leer ist, andernfalls „false“.

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]

Warteschlange

Warteschlange – Es handelt sich um einen Lagerbehälter, der die Entnahme nach der First-In-First-Out-Reihenfolge (FIFO) unterstützt. Wir rufen die INSERT-Operation für eine Warteschlange ENQUEUE auf und die DELETE-Operation rufen wir DEQUEUE auf. Wie die Stapeloperation POP akzeptiert DEQUEUE kein Elementargument. Stapel und Warteschlangen sind dynamische Mengen, in denen das durch die DELETE-Operation aus der Menge entfernte Element vordefiniert ist.

Enqueue(x,q):Element x am Ende der Warteschlange q einfügen.

Aus der Warteschlange entfernen(q): Das vordere Element aus der Warteschlange q zurückgeben (und entfernen).

Die Warteschlange hat einen Kopf und einen Schwanz.

• Wenn ein Element in die Warteschlange gestellt wird, nimmt es seinen Platz am Ende der Warteschlange ein, genauso wie ein neu ankommender Kunde einen Platz am Ende der Warteschlange einnimmt.

• Das aus der Warteschlange entfernte Element ist immer dasjenige, das an der Spitze der Warteschlange steht, wie der Kunde an der Spitze der Warteschlange, der am längsten gewartet hat.

Anwendungen der Warteschlange -

1. Aufgabenplanung:Verwaltet CPU-Prozesse und Jobs in der richtigen Reihenfolge.
2. BFS: Implementiert die Breitensuche in Diagrammen.
3. Druckwarteschlangen: Verarbeitet Druckaufträge nacheinander.
4. Netzwerk-Routing: Puffert Datenpakete für die Übertragung.
5. Callcenter: Verwaltet Kundenanrufe in Wartereihenfolge.
6. Streaming: Puffert Video- oder Audiostreams in Echtzeit.
7. Eingabeereignisse: Verarbeitet Tastatur- und Mauseingaben in GUI-Systemen.

Warteschlange mit Array implementieren-

• enqueue() –Einfügung von Elementen in die Warteschlange.
• dequeue() –Entfernen von Elementen aus der Warteschlange.
• peek() oder front()- Erfasst das am vorderen Knoten der Warteschlange verfügbare Datenelement, ohne es zu löschen.
• isEmpty() – Prüft, ob die Warteschlange leer ist.

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]

Warteschlange mithilfe von Stacks implementieren -

• push(x) - Verschieben Sie alle Elemente von Stapel 1 nach Stapel 2, um ihre Reihenfolge umzukehren, und verschieben Sie dann und wieder alle Elemente zurück von Stapel 2 nach Stapel 1.
• pop() - Entfernt das Element vom Anfang der Warteschlange und gibt es zurück
• peek() - Gibt das Element an der Spitze der Warteschlange zurück
• empty() - Gibt true zurück, wenn die Warteschlange leer ist, andernfalls false

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)

Stack mithilfe von Warteschlangen implementieren -

• push(x) - Neues Element zur zweiten Warteschlange hinzufügen, dann alle Elemente von Warteschlange 1 in Warteschlange 2 verschieben, um die Stapelreihenfolge (LIFO) beizubehalten und die Warteschlangen auszutauschen.
• pop() - Entfernt das Element oben im Stapel und gibt es zurück
• peek or top() - Gibt das Element am Anfang der Warteschlange zurück
• empty() - Gibt true zurück, wenn die Warteschlange leer ist, andernfalls false

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

Das obige ist der detaillierte Inhalt vonStapel und Warteschlange || Python || Datenstrukturen und Algorithmen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!