「データ構造」スタックの基本概念、構造、および簡単な実装(Python)

私は今この教材を参考にして勉強していると同時に、易趣の「資料構造と一緒に勉強するアルゴリズム入門」という本も参考にしています.

スタックベース

스택(Stack)は、一時的にデータを格納するための基本的なデータ構造である.教材ではアイスクリームの筒と解釈している.🍦

上の写真のように、アイスクリームおじさんがアイスクリームを山積みするには、「イチゴ->バニラ->キャラメル」の味で山積みする必要があります.でもイチゴ味は『キャラメル->バニラ->イチゴ』の順に食べます
彼らは構造をフリンゲルストンと考えればいいと言った.1つの入口と1つの出口しかない構造であるため、データの입력と출력とを比較すると、データの入出力順序が逆であり、LIFOと呼ばれる.Last In First Outは、後入先出構造である.

スタックの原理

スタックは片側のみを貫通する構造であるため,挿入と抽出は片側のみで行う.
スタックにデータを入れる動作を푸시(push)、スタックからデータを取り出す動作を팝(pop)と呼ぶ.一番上はtop、一番下はbottomです.

データの挿入:push

スタックの5つのセルはすべて空です.topの値は空なので、-1を指定します.
データをプッシュするとtopは1増加します.次に、ステップ2で追加したtop位置0にデータを挿入する.

データ抽出:pop

スタックからデータをポップアップするのは、上部からデータをポップアップするプロセスです.まず、中央または一番下のデータを取り出すことはできません.
だから上から一つ一つ抽出する方法topが指す位置からデータを取り出し、topを1減少させる方法がある.

スタックの容易な実装

5칸 짜리의 빈 스택 만들기

stack = [None, None, None, None, None]  # 크기가 5칸인 빈 상태의 스택 생성
top = -1                                # top은 아직 데이터가 없으므로 -1로 초기화(빈 상태)

데이터 삽입: push

# 2. 데이터 삽입: push
# 생성한 스택에 데이터를 넣으려면 top을 1 증가시킨 후 데이터를 넣는다.

## 크기가 5칸인 스택의 생성과 데이터 3개 입력 ##
stack = [None, None, None, None, None]
top = -1

top += 1
stack[top] = '커피'
top += 1
stack[top] = '녹차'
top += 1
stack[top] = '꿀물'     # top을 1씩 증가시키고, 해당 위치에 데이터를 삽입하는 과정

print('------스택 상태------')
for i in range(len(stack)-1, -1, -1):
    print(stack[i])


# len(stack)-1은 스택의 맨 위쪽부터 -1씩 감소하면서 출력한다
# 즉, 4,3,2,1,0번째 데이터가 출력된다.

데이터 추출: pop

# 3. 데이터 추출: pop
# 데이터가 3개 있는 스택에서 데이터를 추출하려면 top 위치의 데이터를 밖으로 추출한 후, top의 위치 데이터는 None으로 만들고 top을 1씩 감소시킨다.

## 스택에서 데이터 3개 추출 ##
stack = ['커피', '녹차', '꿀물', None, None]
top = 2

print('------스택 상태------')
for i in range(len(stack)-1, -1, -1):
    print(stack[i])

print('---------------------')
data = stack[top]                   # 현재 top 위치의 데이터를 추출
stack[top] = None                   # top 위치에 None을 대입해서 데이터 삭제
top -= -1                           # top을 1 감소 시킴
print('pop--->', data)              # 추출한 데이터를 출력

data = stack[top]
stack[top] = None
top -= -1
print('pop--->', data)

data = stack[top]
stack[top] = None
top -= -1
print('pop--->', data)
print('---------------------')

print('------스택 상태------')
for i in range(len(stack)-1, -1, -1):
    print(stack[i])

りんごが足りない

------스택 상태------
None
None
꿀물
녹차
커피
---------------------
pop---> 꿀물
pop---> None
pop---> None
---------------------
------스택 상태------
None
None
None
녹차
커피

これで,スタックの基本概念と構造を理解し,コードで簡単に実装した.