Pythonのデータ構造 - スタックとキューの実装 (1)

1. スタック

スタックは、挿入と削除の操作を 1 つの位置のみに制限するテーブルであり、この位置はテーブルの最後であり、スタックの先頭と呼ばれます。スタックの基本操作は、PUSH (スタックへの) と POP (スタックへの) です。スタックは LIFO (後入れ先出し) テーブルとも呼ばれます。

1.1 スタック実装

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 スタックアプリケーション

1.2.1 プログラム内のペアになっているシンボルを確認する

プログラム内の構文エラーは、多くの場合、シンボルの欠落によって発生します。スタックを使用して、シンボルがペアになっているかどうかを確認できます。文字が開いたシンボル ('({[')) の場合は空のスタックを作成し、閉じたシンボル (')]}' の場合はスタックにプッシュします。は空です。「()}」の間違いに相当します。それ以外の場合は、スタックをポップします。ポップされたシンボルが対応するオープン シンボルでない場合は、'(}' のエラーに対応するエラーが報告されます。ファイルの最後でスタックが空の場合、エラーが報告されます。 '({}' のエラーに対応して報告されました。

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 10 進数変換

10 進数から 2 進数への変換: 商が 0 になるまで 10 進数を 2 進数に変換します。左下の数値から読み取りを開始し、次に数値を読み取ります。右側にある「アルゴリズムによる解決」を下から上に読んでください。 「データ構造」の画像:

コード:

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 後置記法

接尾辞記法 (後置)、スタックを使用、操作に遭遇したときにスタックに数値をプッシュするを使用すると、スタックからポップされた 2 つの要素に作用し、結果をスタックにポップします。

(7+8)/(3+2) は 7 8 + 3 2 + /

「アルゴリズムとデータ構造による問題解決」の図:

インフィックスからサフィックスへの変換: ときオペランドが読み取られると、出力に配置されます。演算子 (+、-、​​、/) が読み取られるとき、スタックが空の場合はスタックにプッシュし、そうでない場合はスタック要素をポップし、優先度の低い要素が見つかるまで出力に入れます。 「(」を読み取り、スタックにプッシュし、「)」を読み取り、スタック要素をポップし、「(」が見つかるまで出力に送信します。最後に、スタックが空になるまでスタック要素をポップします。

"より「アルゴリズムとデータ構造による問題解決」の画像:

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 キュー

キューを使用する場合、キューの基本的な操作は次のとおりです。 Enqueue. 、テーブルの最後（後部）に要素を挿入し、 dequeue（デキュー）、テーブルの先頭にある要素を削除します

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)

以上がPythonのデータ構造 - スタックとキューの実装の内容です。 1)、その他の関連記事については、PHP 中国語 Web サイト (www.php.cn) を参照してください