TIL 15 | Python Stack


Stack

  • データにより制限されたデータ構造は、最新の第1出力(LIFO)データ管理方式を採用している.

    (出典:https://www.programiz.com/dsa/stack)
    これは、最上位要素へのポインタ(アドレス値)を含むアレイまたは単一チェーンリストによって実現できる連続的に格納されたデータ構造です.
  • メリットとデメリット
    利点:参照領域性を利用できます(一度参照した箇所は再参照の可能性が高い).
    欠点:データのナビゲーションが困難
  • 適用
    Page-visited history in a Web Browser
    Undo sequence in a text editor
    Matching Tags in HTML and XML
    Implementing function calls
    Auxiliary data structure for other algorithms
  • 主な機能と実施
    (1)主な機能
    push():スタックにデータを入れる
    Pop():スタックからデータを取り出す
    peek():スタックを変更せずに上部の値を出力
    is empty():スタックが空であるかどうかを確認します.
    (2)実施
  • class Node:
        def __init__(self, data):
            self.data = data
            self.next = None
    
    
    class Stack:
        def __init__(self):
            self.head= None
    
        def is_empty(self):
            if self.head :
                return False
            return True
    
        def push(self,data):
            new_node=Node(data)
            new_node.next= self.head
            self.head=new_node
       
        def pop(self):
            if self.is_empty():
                return -1
    
            data=self.head.data
            self.head=self.head.next
            return data
    
        def peek(self):
            if self.is_empty():
                return -1
            return self.head.data