스택(Stack)이란?
스택은 데이터 저장 방식의 하나이며, 데이터의 삽입과 삭제 시에 순서의 제약을 받는데, 이는 큐와 마찬가지이다.
스택은 영단어 Stack에 맞게 박스 쌓기에 비유할 수 있다. 박스는 아래에서부터 위로 차곡차곡 쌓고, 치울 때는 위에서부터 아래로 치우게 된다. 스택 또한 마찬가지로, 스택에 데이터를 삽입할 때는 아래에서 위로 삽입하게 되고, 스택에서 데이터를 제거할 때는 위에서 아래로 데이터를 제거하게 된다.
이러한 구조를 선입후출(First In Last Out) 또는 후입선출(Last In First Out)구조라고 한다.
다행히도, Python에서 스택을 구현하기 위해서는 별도의 모듈이 필요 없다.
list 자료형의 append() 메소드와 pop() 메소드를 활용하면 자동으로 리스트의 맨 끝에 데이터를 붙였다 뗐다 할 수 있기 때문이다.
stack = []
#별도의 모듈 사용 없이 일반적인 list로서 선언
stack.append(5)
#append 메소드를 사용하여 stack에 데이터를 삽입
stack.append(2)
stack.append(9)
stack.pop()
#pop 메소드를 사용하여 가장 늦게 들어온 데이터를 삭제
stack.append(7)
print(stack)
[5, 2, 7]
큐(Queue)란?
큐는 영단어 Queue에 맞게 대기줄에 비유할 수 있다. 대기줄은 선착순으로 먼저 온 사람이 원하는 것을 제공받고, 나중에 온 사람은 먼저 온 사람들의 볼 일이 끝날 때까지 기다린다. 큐 또한 마찬가지로, 큐에 가장 먼저 삽입되는 데이터는 가장 먼저 삭제되게 된다. 가장 나중에 삽입되는 데이터는 가장 나중에 삭제되며, 따라서 큐는 흔히 '공정한' 자료구조라고 비유된다.
이러한 구조를 선입선출(First In First Out) 구조라고 한다.
Python에서 큐를 구현하기 위해서는 별도의 모듈이 필요한데, list 자료형에는 가장 앞의 원소를 제거해 주는 메서드가 없기 때문이다. 따라서 collections 모듈의 deque 자료형을 활용하여 큐를 구현하는 데 필요한 기능들을 사용하게 된다.
from collections import deque
#collections 모듈의 deque 클래스를 import
queue = deque()
#큐 구현을 위해 queue를 deque 클래스의 인스턴스로서 선언
queue.append(5)
#deque 자료형에는 list와 마찬가지로 append 메소드를 사용할 수 있다.
queue.append(2)
queue.append(9)
queue.popleft()
#선입선출을 구현하기 위해 존재하는 메소드로, list 자료형의 pop과는 달리
#이 메소드는 가장 먼저 추가된 원소를 제거하게 된다.
queue.append(7)
print(queue)
deque([2, 9, 7])
주의점
실제로 스택과 큐를 사용할 때에는 데이터의 삽입과 삭제 외에도 오버플로(Overflow)와 언더플로(Underflow)를 고민해야 한다.
오버플로(Overflow)는 특정한 자료구조가 수용할 수 있는 데이터의 크기를 넘어서서 데이터 삽입을 시도할 때 발생한다.
이 경우, 해당 자료구조에 할당된 메모리 외의 영역에 할당을 시도하게 됨으로써 메모리 상의 다른 값을 덮어씌워버리게 될 위험이 존재한다.
언더플로(Underflow)는 자료구조 안에 데이터가 하나도 없을 때 데이터 삭제를 시도할 때 발생한다.