スタックって、そもそも何？
はい、データを貯めて、取り出す。それだけです。
但し、取り出し方は最後に貯めたデータを最初に取り出せるようにしたいです。
Σ(oдΟ;)
例えばですが以下にあるようにデータを 6 個、縦に積み上げながら
格納できる箱があったとします。
まずは、箱を空にして、A を格納した後に、取り出してみましょう。
A を格納して、取り出したら、元の空の状態に戻りました。
簡単ですね。
ではデータの格納を Push , 取り出しを Pop と命名したうえで、
データの Push / Pop を動きをもう少し図にしてみました。
A , B を Push し、最後に pop してみました。最後に箱に残るのは A ですよね。
このようにして、最後に Push したデータを最初に Pop するスタックの動きをイメージできるようになりました。
箱の深さが 6 無くても良かったんでは!?
細かい事は気にしない(笑)。
さぁ、次は Python で書いてみましょう。
っとその前に、ここでの記述が分からない場合は、
Progate での学習をお勧めします!!
https://prog-8.com/
では最初にスタックを実現するための箱を用意しましょう。
イメージはこんな感じです。
str という名の箱を用意し、何個データが入るかを capacity としました。
ptr は 1 ~ 6 の位置を表しています。
先ほどの図に ptr の動きを足してみました。
こんな感じで、ptr(ポインタ)は Push 出来る箱の位置を表しています。
ptr をイメージできたところで、やっと Python です。
箱を作ってみました。
def __init__(self,capacity:int = 10):
self.str = [None] * capacity
self.capa = capacity
self.ptr = 0
" def __ init __ " 用意したプログラム内の初期値を定めます! っという決まり文句です。
プログラムが走るときに最初に読み込んで貰わないと話が始まらないですよね。
次に Push です。
def push(self,value):
if self.ptr >= self.capa:
raise top.full
self.str[self.ptr] = value
print(self.str[self.ptr])
self.ptr += 1
間に print が入っていますが、無視しても良いです。
大切なのは、最初に ptr の位置が Full になっていないか確認することです。
ptr == capacity であれば Full (お腹いっぱい)
ptr > capacity であれば、プログラムが暴走してる!! ってことになります。
if self.ptr >= self.capa: で確認していることが分かります。
Full でなければ self.str[self.ptr] = value とし、無事に Push 完了です。
次の Push に備えて ptr を一つインクリメントしておきます。
Push でやっていることは以上です。
次に Pop です。
def pop(self):
if self.ptr <= 0:
raise top.empty
self.ptr -= 1
return self.str[self.ptr]
ポインタ ptr が マイナスになっていたとすると、
底を突き抜けて、地面にデータをねじ込むことになるので
一応 if 文でチェックを掛けます。
ここで疑問に思った方も居ると思いますので
補足しますが、Python の世界では格納領域は 1 から始まるわけではなく、
0 から始まります。
最初の図が良くなかった、すいません。
よって ptr = 0 の場合は、空を意味します。Empty ってやつです。
空じゃなければ以下のように ptr を 1 減らして、
取り出すデータを指定します。
後は return self.str[self.ptr] とすることで、格納したデータを取り出すことが出来ます。
いやいや、return でデータは返せたけど、
指定した領域は空になってないよね！？
Yes ! その通り!!ﾊﾞｺ~ﾝ!( - -)/☆(_)
実はですね、スタックは ptr の位置でデータの管理をしています。
たとえ、空にする処理をしていなくても、次の Push で自動的に書き換えられますよね？
だから ptr の動きだけ見ていればスタックは出来てしまうのです。
っというわけで、取り急ぎ用意したスタックの全体像を載せておきます。
class top:
class full(Exception):
pass
class empty(Exception):
pass
def __init__(self,capacity:int = 10):
self.str = [None] * capacity
self.capa = capacity
self.ptr = 0
def push(self,value):
if self.ptr >= self.capa:
raise top.full
self.str[self.ptr] = value
print(self.str[self.ptr])
self.ptr += 1
def pop(self):
if self.ptr <= 0:
raise top.empty
self.ptr -= 1
return self.str[self.ptr]
test = top()
while True:
num = int(input("select 1.push , 2.pop : "))
if num == 1 :
s = int(input("enter data: "))
try:
test.push(s)
except test.full:
print("full!")
elif num == 2:
try:
x = test.pop()
print(x)
except test.empty:
print("empty!")
else:
break
多分、"__ init __" , push , pop が肝なので、そこが分かれば、
ご理解いただけると思っています。
初めての投稿ですので、不足分、分かりにくい所があれば
ガンガン優しくご指摘御願い致します!!m(_ _)m
| その他の記事 |
|---|
| 1つの配列に 2 つのスタックを Python で実装してみる |
| Python で作ったスタックに最小値(min) を返す機能を追加するが push/pop/min は基本 O(1) !! |
| 再帰で階乗に挑戦してみる |
| ハノイの塔に再帰で挑む |