먹고 기도하고 코딩하라

파이썬과 자료구조 (2) - 스택, 큐, 데크 본문

자료구조&알고리즘/이론

파이썬과 자료구조 (2) - 스택, 큐, 데크

2G Dev 2021. 8. 19. 18:52
728x90
728x90

 

저번 포스팅에 이어 이번에는 스택과 큐, 데크 자료구조에 대해 알아보자.

 

 

 

3. 스택

스택은 LIFO, Last In First Out, 후입선출 자료구조이다. 설거지하기, 돈돈 초코볼 등 다양한 비유가 있다.

설거지할 때를 생각해보면, 다 먹고 난 접시를 아래서부터 위로 차곡차곡 쌓는다. 그리고 접시를 닦을 때는 맨 위에 있는 접시부터 꺼내서 닦는다. 이것이 바로 후입선출, 가장 마지막에 들어간 데이터가 가장 처음 나오는 자료구조다.

 

스택의 연산에는 다음과 같은 것들이 있다.

  • push : 스택의 맨 위(뒤)에 데이터를 삽입하는 연산. 시간복잡도 O(1)
  • pop : 스택의 맨 위(뒤)에서 데이터를 꺼내는 연산. 시간복잡도 O(1)
  • peek : 스택의 맨 위의 데이터를 보는 연산. 꺼내지 않는다. 시간복잡도 O(1)
  • size : 스택에 들어간 데이터의 개수를 확인하는 연산
  • isEmpty : 스택이 비었는지 확인하는 연산.

 

그럼 위의 구현 필요 연산을 가지고 스택을 실제로 구현해 보자. 이번에는 노드를 쓰지 않고 간단히 해보자.

# 스택
class Stack:
  def __init__(self):
    self.stack = []
  
  def push(self, value):
    self.stack.append(value)

  def pop(self):
    if self.isEmpty():
      return '스택이 비었습니다.'
    return self.stack.pop()
  
  def peek(self):
    if self.isEmpty():
      return '스택이 비었습니다.'
    return self.stack[-1]

  def isEmpty(self):
    return not bool(self.stack)
  
  def size(self):
    return len(self.stack)

  def __repr__(self):
    return repr(self.stack)

연결 리스트에 비해 아주 간결한 구현이다. 이 스택에는 굳이 length 관리가 필요하지 않은데, 이유는 한 리스트 안에 요소들이 모두 모여 있기 때문이다. 만약 연결 리스트에서 length를 관리하지 않는다면, Node의 next 포인터로 타고타고 끝까지 가야 개수를 확인할 수 있을 것이다.

사용례는 다음과 같다.

 

if __name__ == '__main__':
  stack = Stack()
  print('스택이 비었나요? {}'.format(stack.isEmpty()))
  for i in range(5):
    stack.push(i)
  print(stack)
  print(stack.size())
  print(stack.peek())
  for i in range(1, 5):
    print(stack.pop())
  print(stack.pop())
  
'''
스택이 비었나요? True
[0, 1, 2, 3, 4]
5
4
4
3
2
1
0
'''

정상적으로 작동하는 모습이다.

그런데 문제풀이할 때는 스택을 구현하시오 하지 않는 이상 그냥 기본 리스트로 append, pop 해서 많이들 쓰는 것 같다. 참고로 위의 기능들 다 기본 리스트로 구현 가능하다.

 

stack = []
# push
stack.append(x)
# pop
stack.pop()
# peek(top)
print(stack[-1])
# isEmpty
print(not bool(stack))
# size
print(len(stack))

이 자료구조에 어떤 기능들이 있고 어떻게 작동하는지 이해하는 수준에서 문제풀이를 많이 하면 도움이 될 것 같다.

 

 

 

4. 큐

스택이 나중에 들어간 것이 먼저 나오는 자료구조라면 큐는 먼저 들어간 것이 먼저 나오는(선입선출, FIFO) 자료구조이다. 줄 서기를 생각해 보면 쉽다(새치기는 고려하지 말자). 가장 앞에 서서 기다리고 있던 사람이 먼저 나간다. 이것이 큐의 대표적 예이다.

 

스택처럼 큐에도 핵심 연산이 있다. 스택과 비슷한 연산을 하지만 이름이 조금 다르다.

  • enqueue : 큐의 뒤에 데이터를 삽입한다. 삽입 연산. 시간복잡도 O(1)
  • dequeue : 큐의 맨 앞에서 데이터를 꺼내온다. 삭제 연산. 시간복잡도 O(1)이지만, 파이썬에서는 pop(0)을 하면서 모든 리스트 요소를 1씩 앞으로 당기기 때문에 노드를 사용하지 않는 경우 실질적으로는 O(n)이 된다.
  • peek : 큐의 맨 뒤 데이터를 본다. 삭제 연산과 달리 삭제하지 않는다. 시간복잡도 O(1)
  • isEmpty : 큐가 비었는지 확인한다.
  • size : 큐에 데이터가 얼마나 들었는지 확인한다.

 

이번에는 Node 클래스를 사용해 큐를 구현해 보자. Node를 사용하지 않고 구현하기는 쉽기 때문에 포스팅에서는 넘어가겠다.

 

# 노드를 사용한 큐
from node import Node

class Queue:
  def __init__(self):
    self.length = 0
    self.head = None
    self.tail = None

  def enqueue(self, value):
    new_node = Node(value)
    if not self.head:
      self.head = new_node
    else:
      self.tail.setNext(new_node)
    self.tail = new_node
    self.length += 1

  def dequeue(self):
    if self.isEmpty():
      return '큐가 비었습니다.'
    return_node = self.head
    self.head = self.head.getNext()
    self.length -= 1
    return return_node.getData()

  def isEmpty(self):
    return not bool(self.length)

  def peek(self):
    if self.isEmpty():
      return '큐가 비었습니다.'
    return self.head.getData()

  def size(self):
    return self.length

  def traverse(self):
    if self.isEmpty():
      return '큐가 비었습니다.'
    node = self.head
    while node:
      print(node.getData(), end=' ')
      node = node.getNext()
    print('순회 끝')

Node를 사용할 경우, 연결 리스트에서도 그랬지만 리스트를 전혀 사용하지 않는다는 사실에 주목하기 바란다. 배열처럼 사용하지 않는 것이 핵심이다! 

이번에도 역시 사용례를 보자.

 

if __name__ == '__main__':
  queue = Queue()
  print('Is Queue Empty? {}'.format(queue.isEmpty()))
  for i in range(1, 10):
    queue.enqueue(i)
  queue.traverse()
  print(queue.size())
  print(queue.dequeue())
  queue.enqueue(10)  
  queue.traverse()
  
'''
Is Queue Empty? True
1 2 3 4 5 6 7 8 9 순회 끝
9
1
2 3 4 5 6 7 8 9 10 순회 끝
'''

잘 동작하는 모습이다.

스택과 마찬가지로 큐 역시 문제풀이할 때 큐 클래스를 임의로 만들어서 쓴다기보다는, 리스트를 사용하거나 collections의 deque를 import해와서 사용하는 경우가 많은 것 같다. deque에는 popleft()와 appendleft(x)라는 유용한 메소드가 있고, rotate도 가능해서 큐를 써야 할 때 편하게 쓰기 좋다.

이것도 기본 리스트로 구현 가능하다.

qu = []
# enqueue
qu.append(x)
# dequeue
qu.pop(0)
# peek(top)
print(qu[0])
# isEmpty
print(not bool(qu))
# size
print(len(qu))

주의할 점이 있는데, 기본 리스트에서 dequeue, 즉 0번 요소를 빼는 pop(0) 연산을 하면 이 때 시간복잡도가 O(n)이라는 점이다. 그래서 큐를 써야 하는 문제에서 이것 때문에 시간 초과가 나기도 한다. 

 

 

 

5. 덱(deque)

덱은 데크라고도 불리는데 둘 다 똑같은 말이고 발음 차이만 존재하는 것 같다. 스택이 LIFO, 큐가 FIFO라면 덱은 앞과 뒤 모두에서 삽입, 삭제가 가능한 자료구조이다. 덱은 따로 구현할 거 없이 그냥 collections의 deque을 어떻게 쓰는지 소개하겠다.

 

from collections import deque

# 초기화. 빈 채로 할 수도 있고 이터러블 객체를 넣을 수도 있다
q = deque([1, 2, 3, 4, 5])

# 뒤에 삽입
q.append(6)

# 앞에서 꺼내기
print(q.popleft())	# 1
print(q)	# deque([2, 3, 4, 5, 6])

# 앞에 삽입
q.appendleft(1)

# 뒤에서 꺼내기
print(q.pop())	# 6
print(q)	# deque([1, 2, 3, 4, 5])

# 오른쪽으로 밀어내기
q.rotate(3)  
print(q)	# deque([3, 4, 5, 1, 2])

# 왼쪽으로 밀어내기
q.rotate(-2)
print(q)	# deque([5, 1, 2, 3, 4])

append-appendleft와 pop-popleft를 잘 알아두면 큐와 스택 모두를 구현할 수 있어서 편리하다.

rotate가 좀 독특한데, rotate 안에 양수 n이 들어가면 오른쪽으로 n만큼 회전한 결과가 된다. [1, 2, 3, 4, 5]에서 오른쪽으로 3칸만큼 회전하면 맨 뒤에 있던 5가 앞으로 와서 [5, 1, 2, 3, 4] -> [4, 5, 1, 2, 3] -> [3, 4, 5, 1, 2] 이런 결과가 된다. 반대로 음수 n이 들어가면 왼쪽으로 n만큼 회전한다. [4, 5, 1, 2, 3] -> [5, 1, 2, 3, 4] 이런 식이다.

 

다음에는 우선순위 큐와 힙, 해시 테이블에 대해 알아보겠다.

 

 

 

References

  • 미아 스타인, <파이썬 자료구조와 알고리즘>

 

728x90
반응형
0 Comments
댓글쓰기 폼