🚀 들어가기
수학의 정석은 집합만 보고 덮었다는 말을 종종 들은 적이 있습니다. 과거 집합 단원이 수학의 정석 가장 앞에 있어 책을 조금만 읽고 말았다는 말이죠.
저에게는 자료구조에서 스택과 큐가 집합 같은 존재입니다. 전공 과목에서도 가장 먼저 배워 열정을 가지고 수업에 임했는데 끝나고 나니 스택과 큐만 머리에 남아있더라구요...😓
그럼 스택과 큐가 빠삭하냐? 그것도 아닙니다. 스택과 큐의 개념은 남아있지만 어떤 문제에 스택과 큐를 적용해야 할 지 경험이 많지 않습니다. 응용을 못한다는 거죠! 이번 기회에 스택과 큐를 정확히 알고 더 나아가 다양한 자료구조를 구현해보면서 익히고자 합니다. 응용할 수 있는 실력까지 높여볼 생각입니다!
✨ 스택
💡 개념
스택(stack)은 말그대로 데이터를 쌓는 자료구조입니다.
책을 눕혀서 쌓아두면 맨 아래에 있는 책을 바로 뽑을 수 없습니다. 반드시 맨 위에 있는 책부터 차례대로 뽑아야 하죠.
스택 자료구조도 마찬가지입니다. 스택에 데이터들을 하나씩 입력하고 맨 처음에 입력한 데이터를 빼기 위해선 가장 나중에
입력한 데이터부터 차례대로 빼내야 합니다.
스택 구조는 프로세스 실행 구조의 가장 기본입니다.
이러한 스택의 입출력 방식을 FILO(First In Last Out) 또는 LIFO(Last In First Out)이라고 합니다.
또한 스택에 데이터를 넣는 것을 push, 데이터를 빼는 것은 pop이라고 합니다.
직접 그린 그림으로 설명해보겠습니다.
📗 설명
push의 동작입니다. 먼저 들어간 데이터 위에 그 다음 데이터가 쌓이는 동작이라고 이해하면 쉽습니다.
다음은 pop의 동작입니다. 가장 최근에 들어간 데이터가 가장 먼저 나오는 것을 확인할 수 있습니다.
다음은 push와 pop의 동작 시 주의해야 할 사항입니다.
스택에는 top이라고 하는 스택 저장 한도가 있습니다. top보다 데이터를 더 넣으려고 하면 에러가 발생합니다. 또한 스택에 아무 데이터도 없는 상황에서 데이터를 빼려고 하면 에러가 발생합니다.
📝 파이썬으로 구현
파이썬으로 스택을 구현할 때 list를 사용합니다.
list의 메소드인 append로 push를 구현하고 pop을 사용합니다.
data_stack = list()
data_list = [1, 2, 3, 4, 5]
for data in data_list:
data_stack.append(data)
print(data_stack) # [1, 2, 3, 4, 5]
data_stack.pop()
data_stack.pop()
print(data_stack) # [1, 2, 3]
파이썬에서 스택은 list로 간단하게 구현할 수 있습니다.
list의 메소드를 직접 사용하지 않고 스택을 구현해보겠습니다.
class Stack:
def __init__(self, top):
self.stack = list()
self.top = top
def isFull(self):
if len(self.stack) == self.top:
return True
else:
return False
def isEmpty(self):
if len(self.stack) == 0:
return True
else:
return False
def stackPush(self, data):
if self.isFull():
print("스택이 찼습니다.")
else:
self.stack.append(data)
def stackPop(self):
if self.isEmpty():
print("스택이 비었습니다.")
else:
self.stack.pop()
def showStack(self):
for data in self.stack:
print(data, end=" ")
print()
stack = Stack(4)
data_list = [1, 2, 3, 4, 5]
for data in data_list:
stack.stackPush(data) # 스택이 찼습니다.
stack.showStack() # 1 2 3 4
for _ in range(2):
stack.stackPop()
stack.showStack() # 1 2
for _ in range(3):
stack.stackPop() # 스택이 비었습니다.
🎁 관련 문제
✨ 큐
💡 개념
큐(queue)는 줄 세우기와 유사합니다. 데이터의 입출력이 한쪽에서 행해지는 스택과는 달리 큐는 양쪽에서 행해집니다.
데이터가 들어오는 곳과 나가는 곳이 다르기 때문에 가장 먼저 입력된 데이터가 가장 먼저 출력되는 FIFO(First In First Out) 방식이 적용됩니다.
큐는 멀티 태스킹을 위한 프로세스 스케쥴링 방식을 구현하기 위해 많이 사용됩니다.
스택과 마찬가지로 큐에 데이터 입출력에 관한 용어가 있는데요, 입력은 enqueue, 출력은 dequeue라고 합니다.
직접 그린 그림으로 설명해보겠습니다.
📗 설명
enqueue의 동작입니다. 큐의 입구로 들어와 출구 쪽으로 차례대로 데이터가 저장됩니다. 가게 앞에 줄을 서는 것과 유사합니다.
다음은 dequeue의 동작입니다. 가장 먼저 들어간 데이터가 가장 먼저 나오는 것을 확인할 수 있습니다.
📝 파이썬으로 구현
파이썬으로 스택을 구현할 때 list를 사용할 수 있습니다.
list의 메소드인 append로 enqueue를 구현하고 pop의 매개변수로 0을 사용하여 인덱스가 0인 데이터, 즉 가장 앞에 있는 데이터를 제거하는 dequeue를 구현할 수 있습니다.
queue = list()
data_list = [1, 2, 3, 4, 5]
for data in data_list:
queue.append(data)
print(queue) # [1, 2, 3, 4, 5]
queue.pop(0)
queue.pop(0)
print(queue) # [3, 4, 5]list의 메소드를 직접 사용하지 않고 큐를 구현해보겠습니다.
class Queue:
def __init__(self):
self.queue = list()
def enqueue(self, data):
self.queue.append(data)
def dequeue(self):
if len(self.queue) != 0:
self.queue.pop(0)
else:
print("큐가 비었습니다.")
def showQueue(self):
for data in self.queue:
print(data, end=" ")
print()
queue = Queue()
data_list = [1, 2, 3, 4, 5]
for data in data_list:
queue.enqueue(data)
queue.showQueue() # [1, 2, 3, 4, 5]
queue.dequeue()
queue.dequeue()
queue.showQueue() # [3, 4, 5]큐의 경우 위와 같은 일반적인 경우가 아닌 다양한 종류의 큐가 있습니다.
예를 들어 데크(deque)는 Doubly-ended Queue라고 하는데요, 한쪽이 입력을, 다른 한쪽이 출력을 담당하는 일반적인 큐와는 다르게 양쪽에서 입출력이 이루어집니다.
이는 파이썬 라이브러리를 통해 사용할 수 있습니다.
from collections import deque위와 같은 방법으로 데크를 사용하면 append, appendleft, pop, popleft 등의 메소드들을 사용할 수 있습니다.
특히 popleft의 경우, 일반적인 큐에서 사용하는 pop(0)과는 동작 시간이 차이가 나기 때문에 dequeue 동작을 많이 사용할 경우에 데크를 사용하는 것이 좋습니다.
from collections import deque
my_deque = deque([1,2,3,4,5])
my_deque.append(6) # [1, 2, 3, 4, 5, 6]
my_deque.appendleft(0) # [0, 1, 2, 3, 4, 5, 6]
my_deque.pop() # [0, 1, 2, 3, 4, 5]
my_deque.popleft() # [1, 2, 3, 4, 5]🎁 관련 문제
- 기능 개발 [✅]
- 카드 뭉치 [✅]
- 다리를 지나는 트럭 []
