【Pythonでゼロから作るデータ構造】スタック(Stack)編

ご挨拶

はじめまして^^

hrm441といいます、よろしくお願いします

今回は基礎的なデータ構造であるスタックを、Pythonのクラスを使って自作してみました

タイトルの "ゼロから" というのは、「listオブジェクトにある'append'や'pop'などの内部メソッドを使わず、それらも自分の手で実装してみよう」という意味を込めてのものです！

大学の課題やコーディングテスト対策として参考になれば幸いです♪(自分はこれが初めてのインターン面接で出されて爆死しました)

コード

#スタックの実装
#スタックとはLIFO(Last in First out)のデータ構造
#作成日 2024/2/17
class Stack:
    INITIAL_SIZE = 10 #配列の初期サイズ
    
    def __init__(self):
        self.items = [None] * Stack.INITIAL_SIZE  #初期化
        self.size = 0 #現在のスタックのサイズ
        
    def is_empty(self):
        return self.size == 0
    
    def push(self, item):
        if self.size < len(self.items):
            self.items[self.size] = item
            self.size += 1
        else:
            raise OverflowError("Stack overflow")
    
    def pop(self):
        if self.is_empty():
            raise IndexError("pop from empty stack")
        else:
            self.size -= 1
            item = self.items[self.size]
            self.items[self.size] = None #削除された要素はNoneで置き換え
            return item
    
    def top(self):
        if self.is_empty():
            raise IndexError("top from empty stack")
        else:
            return self.items[self.size - 1]
        
    def get_size(self):
        return self.size