久しぶりに書きました本当に.再帰に触れたことがない私にとって、木の資料の構造は恐ろしいので、すぐに手を放して、2週間ぐらい経ってやっと目が覚めて、勉強を再開しました.
木型資料構造の学習を無理に終えた後,近年スタックとdek,qを簡単に学習し,文章を書き直し,これらの資料構造を整理しようとした.
その前に前回整理した木を簡単に整理しておきましょう
ツリー構造の特徴

ツリーは最上位のノードルートを起点とし,サブノードが延び,ツリーに類似した非線形資料構造を形成する.

はバイナリツリーを多く使用しており,同じ資料量を探索しても配列に比べてO(n^2)の時間的複雑さが現れる.

再帰的性質を利用するためにもよく用いられる.

バイナリツリーの巡回方式は、前列、中列、後列の巡回方式がある.

バイナリツリーの種類は、正バイナリツリー、完全バイナリツリー、偏バイナリツリー、飽和バイナリツリーなどがある.

📘 実は多くの人が使ったことがあるはずなのですが...?

スタックの資料構造とは,並べ替えや接続リストで容易に表現できるが,よく用いられるため,用語で定義し,その資料構造がどのような形態を持っているかを整理する.
スタック資料構造には、私たちがよく見るスマートフォンアプリケーションのゲームもあります.
このゲームの目的は最下層から木を積み上げ、タワーを最大限に積み上げることです.

私たちが学ぶスタックもそうです.
でも、タワーを建てれば、降りられるはずです.
どうすれば塔が崩れず、何もない初期状態に戻ることができますか?

📘 後に挿入と削除

一番上のブロックから順番に取り除くのが一番いい方法で、塔が崩れずに最初の状態に戻ります.真ん中にも、底の一番上にも積み木を取り外さないと、塔が崩れず、何もない最初の状態に簡単に戻ることができません.
スタックも同じです.
最後に挿入し、同様に削除しても後になります.
したがって,挿入と削除はいずれも後に行われるため,最初に入った資料は遅くとも入った先入後出(First In Last Out)形式の資料構造である.
通常、これらのスタック材料構造は、コンピュータのプロセス実行または関数実行によく用いられ、後から挿入および削除されるため、挿入および削除にはO(1)を記述する時間的複雑さが必要である.

📌 実施資料型

よく使われる資料構造であるため、実施資料の種類や実施形態自体も難しくない.最も一般的で最も使いやすいデータ型には、接続リストと配列があり、配列は通常動的配列を使用します.
この整理文で整理された実装体はPython 3であるため,動的配列ともいえるPythonのList資料型を用いた.

📘 Programming

インプリメンテーションは、基本インプリメンテーションスタックの10828号スタックによって説明される.

💻 Init(作成者)

import sys

class stack:
    def __init__(self) -> None:
        self.stack = []
        self.cnt = 0

クラス名はstackによって決定され、ジェネレータによってオブジェクト変数stackリストとcntが生成されてデータ型宣言が行われます.
ここで使用するstackはstack資料構造を表し,cntは資料の挿入と削除に伴って増減することを示し,資料の数や空白などの確認に声明を出した.

💻 push

def push(self, num):
    self.stack.append(num)
    self.cnt += 1

pushメソッドはappend関数によりスタックの一番後ろに値を追加し,値を追加するたびにcnt変数の値を増加させる.

💻 pop

def pop(self):
    if self.cnt == 0:
        print(-1)
    else:
        print(self.stack.pop())
        self.cnt -= 1

popメソッドはpop関数で値を削除してstackの一番後ろに出力し、値を削除するたびにcnt変数の値を減らします.

💻 size

def size(self):
    print(self.cnt)

sizeメソッドはスタック内のすべての資料を数えます.このとき、値の増減に応じて、データの個数をcnt変数に指定し、cntの値を直接出力する.

💻 top

def top(self):
    if self.cnt == 0:
    	print(-1)
    else:
    	print(self.stack[-1])

topメソッドが出力する値はスタックの上部(リストの末尾)に対応し、削除を実行せずにpopとは異なる値のみが出力されます.

💻 empty

def empty(self):
    if self.cnt == 0:
    	print(1)
    else:
    	print(0)

空のメソッドは、スタック内の値が空であるかどうかを判断するメソッドであり、cnt変数によって値が存在するかどうかを決定します.

💻 main

st = stack()
for _ in range(int(input())):
    test_list = sys.stdin.readline().split()

    if test_list[0] == 'push':
        st.push(test_list[1])

    if test_list[0] == 'pop':
        st.pop()

    if test_list[0] == 'size':
        st.size()
    
    if test_list[0] == 'top':
        st.top()

    if test_list[0] == 'empty':
        st.empty()

stという名前のオブジェクトが作成され、最初のコマンドで入力した回数を入力することでクエリーの繰り返し回数が決定されます.
次に、コマンドの形式はpush 1/pop/size/top/emptyであるため、入力した文字列をスペース区切りリストで返すsplit関数を用いてpushメソッドに入るコマンドと値を区別し、if文条件で適切なコマンドを入力して実行する方法を記述した.