서론
스택은 자료구조 중 대표적인 선형구조이다. 우리가 흔히 게임이나 일상생활에서 "스택 쌓였다"라는 표현을 사용하는데, 완전히는 아니더라도 어느 정도 비슷한 개념을 가지고 있다.
스택
스택은 선형구조의 자료구조로서 일상생활 속에서 꽤나 많이 볼 수 있다. 예를 들어 프링글스 과자를 생각하면 쉽다. 우리가 프링글스를 먹을 때 가장 먹게 되는 감자칩은 가장 마지막에 넣은 감자칩이지 않을가? 이렇게 가장 늦게 넣은 것이 가장 먼저 나온다는 개념을 가졌다면 스택이다. 다른 예시로는 종이컵 더미가 있겠다. 종이컵 더미도 가장 늦게 쌓은 종이컵이 가장 먼저 나오니 말이다. 이를 가장늦게 넣은 것이 가장 먼저 나온다고 해서, 후입선출이라부른다.
스택은 한 곳에서 삽입과 삭제가 일어난다.
나중에 서술할 큐라는 다른 자료구조에서는 한쪽에서 삽입일어나고 반대쪽에서 삭제가 일어나는 반면,
스택은 한 곳에서 삽입 삭제가 이루어진다.
스택에서는 값의 삽입을 PUSH라고 부르고, 값의 삭제를 POP이라고 한다.
그렇다면 스택은 어떻게 값을 삽입하고 삭제할까?
스택은 top이라는 포인터로 삽입, 삭제가 가능하다.
이렇게 아무것도 없는 스택에는 top포인터가 -1을 가르키고 있다.(즉 top포인터의 초기값은 -1이다)
하지만 값을 넣게 되는 순간 top포인터가 1 증가하고 , top포인터가 가르키고 있는 곳에 값을 저장한다.
반대로 값을 삭제하려면 top포인터를 1 감소시키면 된다.
값을 삭제할때 top포인터만 감소시키고 실질적인 값을 삭제하지 않는 이유는 어짜피 top포인터로 가르키는 곳이 스택의 가장 위에 있는 값이기때문에 top포인터를 감소시키면 위에 값은 없다고 봐도 무방하기 때문.
| 3 |
예시상황으로 현재 스택에 아무것도 없는 상태에서 3이라는 값을 삽입하게 되면, top포인터는 1증가하여, 0번 인덱스를 가르키게 되고 0번 인덱스에 3이 삽입된다.
또 7이라는 값을 삽입하게 되면, top포인터가 또 1 증가하여, 1번 인덱스를 가르키게되고, 1번 인덱스에 7이라는 값이 삽입된다.
그리고 7이라는 값을 삭제하려면, top포인터를 1 감소시키면 된다.
만약 스택이 다 차버려서 값을 더 이상 넣게 될 수 없게 된다면 어떻게 될까?
이를 오버플로라고 부른다. 정해진 공간보다 그 이상의 값이 들어오면 오버플로가 일어난다.
반대로 텅 빈 스택에서 값을 삭제하려하면, 언더플로가 일어난다.
그럼 만약에 스택이 다 차있는 상태에서 0번 인덱스를 삭제하려면 어떻게 해야할까?
하는 수 없이 차례대로 위에 인덱스부터 삭제를 해야한다.
이제 파이썬으로 구현을 해보도록 하자.
stack = [None for _ in range(5)]
top_pointer = -1
stack_size = 4
def push(n):
global top_pointer
if top_pointer+1 >= stack_size:
print("stack overflow")
exit()
else:
top_pointer += 1
stack[top_pointer] = n
print(stack[top_pointer])
print(stack)
def pop():
global top_pointer
del stack[top_pointer]
top_pointer -= 1
print(stack[top_pointer])
print(stack)
while 1:
a = input()
if a == "push":
b = int(input("값을 입력하시오: "))
push(b)
elif a == "pop":
pop()
else:
exit()
위에 글에서는 값을 삭제할 때 직접 값을 삭제하지 않고 top포인터만 감소시켜도 된다고 했지만, 이 코드에는 그냥 보기 명확하게 값도 직접 삭제하였다.