스택의 기본과 간단구현

 1  스택의 개념

스택(Stack) 자료구조는 한쪽 끝이 막힌 형태이다. 입구 겸 출구를 공통으로 사용하는 모든 형태를 스택 예로 볼 수 있다.

스택의 가장 큰 특징은 FILO(First In Last Out)이라고 하거나 LIFO(Last In First Out)이다. 피로 보단 리포라고 많이 쓴다.

스택의 주의할 점은 넣을 때는 사용자가 원하는 순서로 넣을 수 있지만 빼낼 때는 특정 선택해서 빼낼 수 없다.

빼낼 떄는 항상 가장 위에 있는 것이 나오고 원하는 것을 빼려면 그것의 위치까지 하나하나 다 빼야 하는 것이다.

 

 2  스택의 원리

아까 말했듯이 스택은 한 곳만 열려 있기에 삽입과 추출이 한곳에서 진행된다.

스택에 데이터를 삽입하는 작동을 push라고 하며, 반대로 추출하는 작동을 pop이라고 한다.

스택에선 top이란 것이 중요한데, 현재 스택에 들어 있는 가장 위의 데이터를 가리킨다는 용어이다.

 

스택은 배열 형태로 구현할 수 있다. 배열 크기를 미리 정한 후 해당 크기의 빈 스택을 만든다.

스택은 초기에 크기를 지정하고 배열로 생성할 수 있다. 스택의 맨 위쪽을 표현하는 top은 데이터가 없을 땐 -1이다.

 

 3  데이터 삽입 : push

스택의 데이터를 삽입하는 push 과정은 스택이 모두 빈 상태, 즉 top이 -1인 상태에서 삽입하면 top을 1 증가시킨다.

top이 0이 되면 그 자리인 0번 칸에 데이터를 삽입한다.

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

top += 1
stack[top] = "커피"
top += 1
stack[top] = "녹차"
top += 1
stack[top] = "꿀물"

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

 

 4  데이터 추출 : pop

스택에서 데이터를 추출하는 pop 과정은 맨 위에 있는 데이터를 꺼내는 과정이다.

입구가 하나뿐인 스택은 맨 위에 있는 것만 꺼낼 수밖에 없으며, 중간에 있는 데이터는 꺼낼 수 없다.

그렇기에 스택에선 삭제보단 꺼내다의 의미를 가진 추출이 더욱 적합하다.

데이터를 삽입한 스택에서 데이터를 추출하는 과정은 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]
stack[top] = None
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])