pythonデータ構造の3つのスタックとキュー
31372 ワード
pythonデータ構造チュートリアルの第3課では、一般的なデータ構造では、格納された要素の格納、管理、使用をサポートするコンテナと呼ばれる構造があり、スタックとキューは最もよく使用される2つのコンテナです.
一.简介二.スタックとキューの抽象データ型(ADT)3.スタックのpython実現1.スタックの順序表実現2.スタックのチェーン表実現3.スタックの応用——括弧マッチング、接尾辞式、Ackerman関数4.キューのpython実現1.キューの循環線形表実現2.キューの応用——ダンサーペアリング問題
一.概要
スタックおよびキューは、主に計算中に一時的なデータを保存するために使用されます.これらのデータは計算中に発見または生成され、後で計算で使用される可能性があります.このような状況は計算の中でよく見られます.仕事で発生したデータはしばらく使わないか、使いきれないので、その時すぐに使えなかったデータを保存する必要があります.格納が必要なデータ項目が事前に特定できない場合は、バッファリングまたはキャッシュと呼ばれる一定のメカニズムで格納および管理する必要があります.スタックとキューは、最も多く使用されるバッファストレージ構造スタックであり、要素の後進先出(Last In First Out,LIFO)関係を保証する構造であり、LIFO構造キューと略称するのは、要素の先進先出(First In First Out,FIFO)関係を保証する構造であり、FIFO構造と略称する
二.スタックとキューの抽象データ型(ADT)
スタックの基本的な方法は、空スタックの作成、入スタック、出スタック、空スタック判定㩐があり、その基本ADTは以下の通りである.
キューのプロパティとメソッドはスタックと似ていますが、スタックに出入りするメソッドでは異なります.基本的なADTは次のとおりです.
三.スタックのpython実装
線形テーブルを用いるスタックを実現するのは最も自然な方法であり、順序テーブルの実現に対して後端で挿入と削除を行うのは効率的な操作であり、この一端をスタックトップとすべきであり、リンクテーブルを用いる実現時には正反対である.スタックのシーケンステーブル実装
テストコード:
結果:
2.スタックのチェーンテーブル実装
テストコード:
結果:
3.スタックの応用——括弧マッチング、接尾辞式、Ackerman関数1)pythonプログラムの中の括弧の不一致を検出する場合:テキストの中の括弧の不一致を検出するのはスタックの1つの比較的簡単な応用で、括弧を発見する時、直接括弧をスタックに入れて、閉じた括弧に遭遇する時スタックの中から1つの要素を弾き出す.空のスタックまたはカッコが一致しない場合は、テキストのカッコに問題があり、エラーが発生します.ここで注意すべきは、pythonプログラムではコメントも存在するため、合格カッコを検出するためのサブ関数parenthesesがある
テストコード:
2)接尾辞式の計算接尾辞式は,我々が一般的に用いる演算式の書き方であり,演算子は「a+b」のように演算対象の中間に書かれており,この形式は最も人間の自然認識に合致するが,計算機にとっては「(3+5)*2+5」の計算のように比較的複雑であり,ここでの計算順序は括弧と演算優先度の影響を受けている.コンピュータは直接計算をスキャンすることができなくて、スタックのストレージに協力する必要があります.次にアルゴリズムロジックを与えます.
@は2つのスタックを創立して、1つは演算子を記憶するために用いて、1つは数字@を記憶するために左から右へ1つずつテキストを読み取って、数字が直接スタックに入ることに出会って、オペレータに出会う情況は比較的に複雑で、接尾辞の表現の中で1つのオペレータに出会う時直接計算することができなくて、プログラムはこの時2元演算子の1つの演算オブジェクトだけを読み取ったため、別の演算オブジェクトを読み込む必要があるので、オペレータをスタックに入れる必要があります.次に、状況別に説明します@オペレータを読むと、オペレータスタックが空であるか、またはオペレータが'(')である場合は、先にそのオペレータをスタックに入れる必要があります@読み出されたオペレータが')である場合は、1つのオペレータと2つのオペランドを絶えずポップアップして演算し、演算結果を'(’,それをポップアップ@遭遇したオペレータが4則演算である場合,そのオペレータとスタックトップオペレータの優先度を比較する必要があるが,スタックトップの優先度以下であれば,スタックトップのオペレータと2つのオペランドをポップアップし,結果としてスタックを圧し,読み出した操作をスタックに読み込み,スタックトップの優先度より大きい場合は簡単にスタックを圧し,これで解すべてのかっこと優先度の問題@1つのオペレータと2つの数字を絶えずポップアップし、演算を行い、演算結果を演算子スタックが空になるまでスタックに圧縮します.
テストコード:
結果:
3)Ackerman関数Ackermen関数の解Ackermen関数はスタック運用問題において非常に古典的なものであり,この例を挙げる目的は,いずれかの再帰的に定義された関数が,1つのスタックが中間結果を保存する方式を導入し,非再帰的プロセスに翻訳できることを説明することである.ループを含むプログラムは、ループを含まない再帰関数Ackerman関数として次のように翻訳できます.
ここでは、この関数が実現する反復方法とスタックの非反復方法を示し、論理分析を行わず、興味のある学生は自分でコードに基づいてスタックの管理状況を描くことができ、プログラミングの難点はこれが二重反復であり、反復の深さが非常に高く、入力パラメータが大きすぎないことであり、そうしないとプログラムがクラッシュしやすいことである.非反復メソッドには、2つのスタックと2つのループ反復メソッドが必要です.
非反復メソッドの実装:
テストコード:
結果:
四.キューのpython実装
pythonのリニアテーブルでキュークラスを実現すると、キューの一端が一端に入る特性のため、listやチェーンテーブルを使用する際に大量の搬送、移動操作が必要となり、コードの効率が低いため、ループリニアテーブルでキュー1を実現する.キューのループ線形テーブル実装listオブジェクトを1つのリングと見なし、末尾の追加とヘッダのポップアップは、このリング内で行われます.ここではhead変数を定義し、ストレージオブジェクトの変化に従っていく必要があります.長さが足りない場合は、ストレージスペースを拡張する必要があります.
2.行列の応用——ダンサーペアの問題循環行列の一つの小さな応用、舞踏会ペアの問題は今晩、男女が一列に並んで、両チームの人数は必ずしも同じとは限らない.
テストコード:
結果:
一.简介二.スタックとキューの抽象データ型(ADT)3.スタックのpython実現1.スタックの順序表実現2.スタックのチェーン表実現3.スタックの応用——括弧マッチング、接尾辞式、Ackerman関数4.キューのpython実現1.キューの循環線形表実現2.キューの応用——ダンサーペアリング問題
一.概要
スタックおよびキューは、主に計算中に一時的なデータを保存するために使用されます.これらのデータは計算中に発見または生成され、後で計算で使用される可能性があります.このような状況は計算の中でよく見られます.仕事で発生したデータはしばらく使わないか、使いきれないので、その時すぐに使えなかったデータを保存する必要があります.格納が必要なデータ項目が事前に特定できない場合は、バッファリングまたはキャッシュと呼ばれる一定のメカニズムで格納および管理する必要があります.スタックとキューは、最も多く使用されるバッファストレージ構造スタックであり、要素の後進先出(Last In First Out,LIFO)関係を保証する構造であり、LIFO構造キューと略称するのは、要素の先進先出(First In First Out,FIFO)関係を保証する構造であり、FIFO構造と略称する
二.スタックとキューの抽象データ型(ADT)
スタックの基本的な方法は、空スタックの作成、入スタック、出スタック、空スタック判定㩐があり、その基本ADTは以下の通りである.
ADT Stack：
Stack(self) #
is_empty(self) #
top(self) #
pop(self) #
push(self,elem) #
len(self) # キューのプロパティとメソッドはスタックと似ていますが、スタックに出入りするメソッドでは異なります.基本的なADTは次のとおりです.
ADT Queue:
Queue(self) #
is_empty(self) #
enqueue(self,elem) #
dequeue(self) #
peek(self) #
len(self) # 三.スタックのpython実装
線形テーブルを用いるスタックを実現するのは最も自然な方法であり、順序テーブルの実現に対して後端で挿入と削除を行うのは効率的な操作であり、この一端をスタックトップとすべきであり、リンクテーブルを用いる実現時には正反対である.スタックのシーケンステーブル実装
#
class StackUnderflow(ValueError):
pass
class SStack():
def __init__(self): #
self._elems = []
def is_empty(self): #
return self._elems == []
def push(self,elem): #
self._elems.append(elem)
def pop(self): #
if self._elems == []:
raise StackUnderflow('in SStack.pop()')
return self._elems.pop()
def peek(self): #
if self._elems == []:
return None
return self._elems[-1]
def deep(self): #
return len(self._elems)テストコード:
st1 = SStack()
st1.push(3)
st1.push(5)
while not st1.is_empty():
print(st1.pop())結果:
5
32.スタックのチェーンテーブル実装
'''
， LNode
，
'''
#LNode
class LNode():
def __init__(self,elem = None,next_ = None):
self.elem = elem
self.next = next_
#
class LStack():
def __init__(self): #
self._top = None
def is_empty(self): #
return self._top is None
def top(self): #
if self._top is None:
raise StackUnderflow('in LStack.top()')
return self._top.elem
def push(self,elem): #
self._top = LNode(elem,self._top)
def pop(self): #
if self._top is None:
raise StackUnderflow('in LStack.pop()')
p = self._top
self._top = p.next
return p.elemテストコード:
#
list1 = list([1,2,3,4,5,6,7,8])
print（list1）
st1 = SStack()
for x in list1:
st1.push(x)
list2 = []
while not st1.is_empty():
list2.append(st1.pop())
print(list2)結果:
[1, 2, 3, 4, 5, 6, 7, 8]
[8, 7, 6, 5, 4, 3, 2, 1]3.スタックの応用——括弧マッチング、接尾辞式、Ackerman関数1)pythonプログラムの中の括弧の不一致を検出する場合:テキストの中の括弧の不一致を検出するのはスタックの1つの比較的簡単な応用で、括弧を発見する時、直接括弧をスタックに入れて、閉じた括弧に遭遇する時スタックの中から1つの要素を弾き出す.空のスタックまたはカッコが一致しない場合は、テキストのカッコに問題があり、エラーが発生します.ここで注意すべきは、pythonプログラムではコメントも存在するため、合格カッコを検出するためのサブ関数parenthesesがある
''' python ( )， 、 '''
def check_py_parens(py_name):
parens = '()[]{}'
open_parens = '([{'
opposite = {')':'(',']':'[','}':'{'}
def parentheses(py_name): #
row = 0 # python
st0 = SStack() #
flag = 1 #
for line in open(py_name):
row += 1
column = 0
for char in line:
if char == '#':
break
elif (char == '\'' or char == '\"') and st0.is_empty():
st0.push(char)
column += 1
flag = 0
elif (not st0.is_empty()) and (char == '\'' or char == '\"') and char == st0.pop():
flag = 1
column += 1
else:
column += 1
if flag == 1:
if char in parens:
yield char,row,column
st = SStack() #
for pr,row,column in parentheses(py_name):
if pr in open_parens: #
st.push(pr)
elif st.is_empty() or st.pop() != opposite[pr]: #
print(pr,row,column)
return False
return Trueテストコード:
# hello.py py ，
print(check_py_parens('hello.py')) 2)接尾辞式の計算接尾辞式は,我々が一般的に用いる演算式の書き方であり,演算子は「a+b」のように演算対象の中間に書かれており,この形式は最も人間の自然認識に合致するが,計算機にとっては「(3+5)*2+5」の計算のように比較的複雑であり,ここでの計算順序は括弧と演算優先度の影響を受けている.コンピュータは直接計算をスキャンすることができなくて、スタックのストレージに協力する必要があります.次にアルゴリズムロジックを与えます.
@は2つのスタックを創立して、1つは演算子を記憶するために用いて、1つは数字@を記憶するために左から右へ1つずつテキストを読み取って、数字が直接スタックに入ることに出会って、オペレータに出会う情況は比較的に複雑で、接尾辞の表現の中で1つのオペレータに出会う時直接計算することができなくて、プログラムはこの時2元演算子の1つの演算オブジェクトだけを読み取ったため、別の演算オブジェクトを読み込む必要があるので、オペレータをスタックに入れる必要があります.次に、状況別に説明します@オペレータを読むと、オペレータスタックが空であるか、またはオペレータが'(')である場合は、先にそのオペレータをスタックに入れる必要があります@読み出されたオペレータが')である場合は、1つのオペレータと2つのオペランドを絶えずポップアップして演算し、演算結果を'(’,それをポップアップ@遭遇したオペレータが4則演算である場合,そのオペレータとスタックトップオペレータの優先度を比較する必要があるが,スタックトップの優先度以下であれば,スタックトップのオペレータと2つのオペランドをポップアップし,結果としてスタックを圧し,読み出した操作をスタックに読み込み,スタックトップの優先度より大きい場合は簡単にスタックを圧し,これで解すべてのかっこと優先度の問題@1つのオペレータと2つの数字を絶えずポップアップし、演算を行い、演算結果を演算子スタックが空になるまでスタックに圧縮します.
# ， ，
def op_calculate(a,b,op):
a = float(a)
b = float(b)
if op == '+':
return a+b
elif op == '-':
return b-a
elif op == '*':
return a*b
elif op == '/':
return b/a
# , ,
def infix_calculator(line):
st_num = SStack() #
st_op = SStack() #
operator = '+-*/()'
priority = {'+':1,'-':1,'*':2,'/':2,'(':0}
exp = line.split() #
for char in exp: #
if char not in operator:
st_num.push(char)
elif char in operator:
if st_op.is_empty() or char == '(':
st_op.push(char)
elif char == ')':
while st_op.peek() is not '(':
op = st_op.pop()
a = st_num.pop()
b = st_num.pop()
st_num.push(op_calculate(a,b,op))
st_op.pop()
elif char in '+-*/':
if priority[char] <= priority[st_op.peek()]:
op = st_op.pop()
a = st_num.pop()
b = st_num.pop()
st_num.push(op_calculate(a,b,op))
st_op.push(char)
elif priority[char] > priority[st_op.peek()]:
st_op.push(char)
while not st_op.is_empty(): #
op = st_op.pop() #
a = st_num.pop()
b = st_num.pop()
st_num.push(op_calculate(a,b,op))
return st_num.pop() # テストコード:
print(infix_calculator(' ( 3 + 5 ) + 2 * ( 5 - ( 1 + 2 ) )'))
print(infix_calculator(' 3 + 5 * 2')) 結果:
12.0
13.03)Ackerman関数Ackermen関数の解Ackermen関数はスタック運用問題において非常に古典的なものであり,この例を挙げる目的は,いずれかの再帰的に定義された関数が,1つのスタックが中間結果を保存する方式を導入し,非再帰的プロセスに翻訳できることを説明することである.ループを含むプログラムは、ループを含まない再帰関数Ackerman関数として次のように翻訳できます.
Ack(m,n)
= n+1 , m = 0
= Ack(m-1,1) , m != 0 and n = 0
= Ack(m-1,Ack(n-1)) , m != 0 and n != 0ここでは、この関数が実現する反復方法とスタックの非反復方法を示し、論理分析を行わず、興味のある学生は自分でコードに基づいてスタックの管理状況を描くことができ、プログラミングの難点はこれが二重反復であり、反復の深さが非常に高く、入力パラメータが大きすぎないことであり、そうしないとプログラムがクラッシュしやすいことである.非反復メソッドには、2つのスタックと2つのループ反復メソッドが必要です.
def Ackerman(m,n):
if m == 0:
return n+1
elif n == 0:
return Ackerman(m-1,1)
elif n != 0:
return Ackerman(m-1,Ackerman(m,n-1))非反復メソッドの実装:
def Ackerman_stack(m,n):
st1 = SStack()
st2 = SStack()
st1.push(m)
st2.push(n)
while m != 0:
if n != 0:
st1.push(m)
n -= 1
st2.push(n)
elif n == 0:
m = st1.pop() - 1
n = 1
st2.pop()
st1.push(m)
st2.push(1)
while m == 0 and st2.deep() > 1:
st1.pop()
n = st2.pop()
m = st1.pop()
st2.pop()
m -= 1
n += 1
st1.push(m)
st2.push(n)
return (st2.pop() + 1)テストコード:
print(Ackerman(2,3))
print(Ackerman_stack(2,3))
print(Ackerman(3,3))
print(Ackerman_stack(3,4))結果:
9
9
61
125四.キューのpython実装
pythonのリニアテーブルでキュークラスを実現すると、キューの一端が一端に入る特性のため、listやチェーンテーブルを使用する際に大量の搬送、移動操作が必要となり、コードの効率が低いため、ループリニアテーブルでキュー1を実現する.キューのループ線形テーブル実装listオブジェクトを1つのリングと見なし、末尾の追加とヘッダのポップアップは、このリング内で行われます.ここではhead変数を定義し、ストレージオブジェクトの変化に従っていく必要があります.長さが足りない場合は、ストレージスペースを拡張する必要があります.
''' '''
#
class QueueUnderflow(ValueError):
pass
class SQueue():
def __init__(self,init_len = 8): #
self._len = init_len
self._elems = [0]*init_len #
self._head = 0
self._num = 0
def __len__(self): #
return self._num
def is_empty(self): #
return self._num == 0
def peek(self): #
if self._num == 0:
raise QueueUnderflow
return self._elems[self._head]
def dequeue(self): #
if self._num == 0: #
raise QueueUnderflow
e = self._elems[self._head]
self._head = (self._head + 1) % self._len
self._num -= 1
return e
def dequeue_tail(self): #
if self._num == 0:
raise QueueUnderflow
e = self._elems[(self._head+self._num-1) % self._len]
self._num -= 1
return e
def enqueue(self,e): #
if self._num == self._len:
self.__extend()
self._elems[(self._head+self._num) % self._len] = e
self._num += 1
def enqueue_head(self,e): #
if self._num == self._len:
self.__extend()
self._head = (self._head + 1) % self._len
self._elems[self._head] = e
def __extend(self): #
old_len = self._len
self._len *= 2
new_elems = [0]*self._len
for i in range(old_len):
new_elems[i] = self._elems[(self._head+i)%old_len]
self._elems,self._head = new_elems,0
2.行列の応用——ダンサーペアの問題循環行列の一つの小さな応用、舞踏会ペアの問題は今晩、男女が一列に並んで、両チームの人数は必ずしも同じとは限らない.
#
def party(men_num,women_num,times):
men = SQueue(men_num)
men_dance = SQueue()
women = SQueue(women_num)
women_dance = SQueue()
for i in range(men_num):
men.enqueue(i+1)
for i in range(women_num):
women.enqueue(i+1)
t = 0
while t < times:
print(' '+str(t+1)+' ：')
n = 0
m = 0
while n < men_num and m < women_num:
print(' : '+str(men._head+1)+','+' : '+str(women._head+1))
men_dance.enqueue(men.dequeue())
women_dance.enqueue(women.dequeue())
n += 1
m += 1
if women_num == men_num:
print(' ')
elif women_num == m:
print(' : ' + str(men._head+1))
elif men_num == n:
print(' : ' + str(women._head+1))
while not men_dance.is_empty():
men.enqueue(men_dance.dequeue())
women.enqueue(women_dance.dequeue())
t += 1テストコード:
party(10,12,3) 結果:
1 ：
: 1, : 1
: 2, : 2
: 3, : 3
: 4, : 4
: 5, : 5
: 6, : 6
: 7, : 7
: 8, : 8
: 9, : 9
: 10, : 10
: 11
2 ：
: 1, : 11
: 2, : 12
: 3, : 1
: 4, : 2
: 5, : 3
: 6, : 4
: 7, : 5
: 8, : 6
: 9, : 7
: 10, : 8
: 9
3 ：
: 1, : 9
: 2, : 10
: 3, : 11
: 4, : 12
: 5, : 1
: 6, : 2
: 7, : 3
: 8, : 4
: 9, : 5
: 10, : 6
: 7