0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

スタックを Python で書いてみた

Last updated at Posted at 2020-09-23

スタックって、そもそも何?
はい、データを貯めて、取り出す。それだけです。
但し、取り出し方は最後に貯めたデータを最初に取り出せるようにしたいです。
Σ(oдΟ;)

例えばですが以下にあるようにデータを 6 個、縦に積み上げながら
格納できる箱があったとします。
図1.PNG

まずは、箱を空にして、A を格納した後に、取り出してみましょう。
図2.PNG
A を格納して、取り出したら、元の空の状態に戻りました。
簡単ですね。

ではデータの格納を Push , 取り出しを Pop と命名したうえで、
データの Push / Pop を動きをもう少し図にしてみました。
A , B を Push し、最後に pop してみました。最後に箱に残るのは A ですよね。
図3.PNG
このようにして、最後に Push したデータを最初に Pop するスタックの動きをイメージできるようになりました。

箱の深さが 6 無くても良かったんでは!?
細かい事は気にしない(笑)。
さぁ、次は Python で書いてみましょう。

っとその前に、ここでの記述が分からない場合は、
Progate での学習をお勧めします!!
https://prog-8.com/

では最初にスタックを実現するための箱を用意しましょう。
イメージはこんな感じです。
図4.PNG
str という名の箱を用意し、何個データが入るかを capacity としました。
ptr は 1 ~ 6 の位置を表しています。
先ほどの図に ptr の動きを足してみました。
図5.PNG
こんな感じで、ptr(ポインタ)は Push 出来る箱の位置を表しています。
ptr をイメージできたところで、やっと Python です。
箱を作ってみました。

stack.py
    def __init__(self,capacity:int = 10):
        self.str  = [None] * capacity
        self.capa = capacity
        self.ptr  = 0

" def __ init __ " 用意したプログラム内の初期値を定めます! っという決まり文句です。
プログラムが走るときに最初に読み込んで貰わないと話が始まらないですよね。
次に Push です。

stack.py
    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 です。

stack.py
    def pop(self):
        if self.ptr <= 0:
            raise top.empty
        self.ptr -= 1
        return self.str[self.ptr]

ポインタ ptr が マイナスになっていたとすると、
底を突き抜けて、地面にデータをねじ込むことになるので
一応 if 文でチェックを掛けます。
ここで疑問に思った方も居ると思いますので
補足しますが、Python の世界では格納領域は 1 から始まるわけではなく、
0 から始まります。
最初の図が良くなかった、すいません。
図9.PNG
よって ptr = 0 の場合は、空を意味します。Empty ってやつです。
空じゃなければ以下のように ptr を 1 減らして、
取り出すデータを指定します。
図10.PNG
後は return self.str[self.ptr] とすることで、格納したデータを取り出すことが出来ます。

いやいや、return でデータは返せたけど、
指定した領域は空になってないよね!?
Yes ! その通り!!バコ~ン!( - -)/☆(_)

実はですね、スタックは ptr の位置でデータの管理をしています。
たとえ、空にする処理をしていなくても、次の Push で自動的に書き換えられますよね?
だから ptr の動きだけ見ていればスタックは出来てしまうのです。
っというわけで、取り急ぎ用意したスタックの全体像を載せておきます。

stack.py
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) !!
再帰で階乗に挑戦してみる
ハノイの塔に再帰で挑む
0
1
2

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?