Python-Datenstruktur - Implementierung von Stapel und Warteschlange (1)

1. Stapel

Ein Stapel ist eine Tabelle, die Einfüge- und Löschvorgänge auf nur eine Stelle beschränkt. Dieser Ort ist das Ende der Tabelle und wird als oberste Stelle des Stapels bezeichnet. Die Grundoperationen des Stapels sind PUSH (in den Stapel) und POP (in den Stapel). Der Stapel wird auch als LIFO-Tabelle (Last In, First Out) bezeichnet.

1.1 Stack-Implementierung

class Stack(object):
    def __init__(self):
        self.stack=[]
    def isEmpty(self):
        return self.stack==[]
    def push(self,item):
        self.stack.append(item)
    def pop(self):
        if self.isEmpty():
            raise IndexError,'pop from empty stack'
        return self.stack.pop()
    def peek(self):
        return self.stack[-1]
    def size(self):
        return len(self.stack)

1.2 Stack-Anwendung

1.2.1 Überprüfen Sie die gepaarten Symbole im Programm

Die Syntaxfehler des Programms sind Wird häufig durch ein fehlendes Symbol verursacht. Mithilfe des Stapels kann überprüft werden, ob Symbole gepaart sind. Erstellen Sie einen leeren Stapel. Wenn das Zeichen ein offenes Symbol ist ('({[')), schieben Sie es auf den Stapel. Wenn das Symbol ein geschlossenes Symbol ist (')]}'), wird beim Stapeln ein Fehler gemeldet ist leer, was dem Fehler „()}“ entspricht. Andernfalls wird der Stapel geöffnet. Wenn das geöffnete Symbol nicht das entsprechende offene Symbol ist, wird ein Fehler gemeldet, der dem Fehler von „(}“ entspricht. Wenn der Stapel am Ende leer ist, wird ein Fehler angezeigt gemeldet, entsprechend dem Fehler von '({}'.

def match(i,j):
    opens='([{'
    closes=')]}'
    return opens.index(i)==closes.index(j)
def syntaxChecker(string):
    stack=Stack()
    balanced=True
    for i in string:
        if i in '([{':
            stack.push(i)
        elif i in ')]}':
            if stack.isEmpty():
                balanced=False
                break
            else:
                j=stack.pop()
                if not match(j,i):
                    balanced=False
                    break
    if not stack.isEmpty():
        balanced=False
    return balanced

1.2.2 Dezimalkonvertierung

Dezimalkonvertierung in Binärzahl: Dezimalzahl in Binärzahl umwandeln, bis der Quotient 0 ist. Beginnen Sie mit dem Lesen Von der unteren linken Zahl, dann lesen Sie die rechte Zahl, beginnend mit Lesen Sie unten

Von Problemlösung mit Algorithmen und Bild „Datenstrukturen“:

Code:

def decimal_to_bin(dec):
    stack=Stack()
    cur=dec
    while cur>0:
        a=cur%2
        cur=cur/2
        stack.push(a)
    binstr=''
    while not stack.isEmpty():
        binstr+=str(stack.pop())
    return binstr

1.2.3 Suffix-Notation

Die Postfix-Notation (Postfix) verwendet einen Stapel. Wenn sie eine Zahl sieht, wird sie in den Stapel verschoben. Wenn sie auf einen Operator trifft, wirkt sie auf die beiden aus dem Stapel entnommenen Elemente und legt das Ergebnis in den Stapel.

(7+8)/(3+2) kann geschrieben werden als 7 8 + 3 2 + /

Bild aus „Problemlösung mit Algorithmen und Datenstrukturen“:

Konvertierung von Infix zu Suffix: Wenn ein Operand gelesen wird, fügen Sie ihn in die Ausgabe ein. Wenn der Operator (+,-,*,/) gelesen wird und der Stapel leer ist, wird er in den Stapel verschoben. Andernfalls wird das Stapelelement entfernt und in die Ausgabe eingefügt, bis ein Element mit einer niedrigeren Priorität gefunden wird. Nachdem Sie „(“ gelesen haben, schieben Sie es auf den Stapel, und wenn Sie „)“ lesen, packen Sie die Stapelelemente ein und senden Sie sie an die Ausgabe, bis „(“ gefunden wird. Am Ende schieben Sie die Stapelelemente hinein, bis der Stapel leer ist.

Bilder aus „Problemlösung mit Algorithmen und Datenstrukturen“:

def infixtoPostfix(infix):
    a={}
    a['*']=3
    a['/']=3
    a['+']=2
    a['-']=2
    a['(']=1
    stack=Stack()
    post=''
    for i in infix:
        if i not in a and i!=')':
            post+=i
        elif i=='(':
            stack.push(i)
        elif i==')':
            top=stack.pop()
            while top!='(':
                post+=top
                top=stack.pop()
        else:          
            while not stack.isEmpty() and a[i]<=a[stack.peek()]:
                post+=stack.pop()
            stack.push(i)
    while not stack.isEmpty():
        post+=stack.pop()
    return post
                   
def postfixExp(postfix):
    stack=Stack()
    postlist=postfix.split()
    for i in postlist:
        if i not in &#39;+-*/&#39;:
            stack.push(i)
        else:
            a=stack.pop()
            b=stack.pop()
            result=math(i,b,a)
            stack.push(result)
    return stack.pop()
def math(x,y,z):
    if x==&#39;+&#39;:
        return float(y)+float(z)
    if x==&#39;-&#39;:
        return float(y)-float(z)
    if x==&#39;*&#39;:
        return float(y)*float(z)
    if x==&#39;/&#39;:
        return float(y)/float(z)

2 Queue

Queue (Warteschlange) ist auch dabei Eine Tabelle, verwenden Sie die Warteschlange. Das Einfügen und Löschen erfolgt an verschiedenen Enden. Die Grundoperationen der Warteschlange sind Enqueue (enqueue), wodurch ein Element am Ende der Tabelle (hinten) eingefügt wird, und dequeue (Dequeue), wodurch das Element gelöscht wird am Anfang der Tabelle. 🎜>

Das Obige ist der Inhalt der Python-Datenstruktur – Implementierung von Stapel und Warteschlange (1). Weitere verwandte Artikel finden Sie auf der chinesischen PHP-Website (www.php.cn). )

class Queue(object):
    def __init__(self):
        self.queue=[]
    def isEmpty(self):
        return self.queue==[]
    def enqueue(self,x):
        self.queue.append(x)
    def dequeue(self):
        if self.queue:
            a=self.queue[0]
            self.queue.remove(a)
            return a
        else:
            raise IndexError,'queue is empty'
    def size(self):
        return len(self.queue)