자료구조 - Stack & Queue

강현구·2022년 3월 17일
0

스택(Stack) 과 큐(Queue)

자료를 표현하고 처리하는 방법 중 하나로 스택과 큐가 있다.

  • 스택 : LIFO(Last-In First-Out)으로 물건을 쌓고 내리는 일과 동일하다
    아래서부터 순서대로 쌓아올린 뒤, 내리는 것은 위에서부터 내려야한다.
  • 큐 : FIFO(First-In First-Out)으로 선입선출, 터널과 같은 곳을 지난다고 생각하면 된다.
    먼저 들어온 데이터가 먼저 빠져나가게 되는 자료구조이다.

Stack

나중에 들어간 데이터가 먼저 나오게 되는 구조

Reference
https://youtu.be/whVUYv0Leg0


Queue

먼저 들어가 데이터가 먼저 나오게 되는 구조

Reference
https://youtu.be/W3jNbNGyjMs


우선순위 큐(Priority Queue)

  • 우선순위 큐 :
    우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조.
    데이터를 우선순위에 따라 처리하고 싶을 때 사용하게된다.
    ex) 제품의 데이터를 저장했다가 가치가 높은 물건부터 꺼내야 하는 경우.

우선순위 큐를 구현하는 방법은 다양하지만 리스트와 힙(heap)을 사용하는 경우를 알아보면 다음과 같다.

  • N개의 data를 처리하는 시간복잡도
우선순위 큐 구현 방식삽입 시간삭제 시간
리스트O(1)O(N)
힙(Heap)O(logN)O(logN)

단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일하다(힙 정렬)

  • 이 경우에는 시간 복잡도는 O(NlogN)이다.

힙(heap)

  • 힙은 완전 이진트리 자료구조의 일종이다.

  • python에서 heapq 라이브러리를 사용해서 힙 자료구조를 활용할 수 있다.
    Default = Min-heap -> Max-heap을 쓰기위해서는 마이너스(-)부호를 사용해서 바꿔주면 된다.

  • 힙에서는 항상 루트 노드(root node)를 제거한다.

  • 최소힙(min heap)

    • 루트 노드가 가장 작은 값을 갖는다.
    • 값이 가장 작은 데이터가 우선적으로 제거된다.
  • 최대힙(max heap)

    • 루트 노드가 가장 큰 값을 갖는다.
    • 값이 가장 큰 데이터가 우선적으로 제거된다.

    완전 이진 트리(Complete Binary Tree)
    루트(root) 노드부터 시작 하여 왼쪽 자식 노드, 오른쪽 자식 노드 순서대로 데이터가 차례되로 삽입되는 트리(Tree)

최소 힙 구성 함수 : Min-Heapify()

  • (상향싱) 부모 노드로 거슬러 올라가며, 부모보다 자신의 값이 더 작은 경우에 위치를 교체한다.

힙에 새로운 원소가 삽입될 때:

  • O(logN)의 시간 복잡도로 힙 성질을 유지하도록 할 수 있다.

    힙에서 원소가 제거될 때:
  • 원소가 제거되었을 때 O(logN)의 시간복잡도로 힙 성질을 유지하도록 할 수 있다.
    • 원소를 제거할 때는 가장 마지막 노드가 루트 노드의 위치에 오도록한다.
    • 이후 루트 노드에서부터 하향식으로(더 작은 자식 노드로) Heapify()를 진행한다.

Deque

  • 데크(Deque)는 선입선출로 단방향으로 작동하는 큐(Queue)와 달리 양방향으로 작동할 수 있다.
  • 즉, 구조의 양 끝단에 데이터를 추가하거나 제거할 수 있다. 끝단의 데이터 추가/제거가 압도적으로 빨라진다.
    -> 양 끝단 데이터에 대한 접근이 O(1)이다.

데크(deque)

다시말해 데크는 스택처럼 사용할 수도 있고, 큐처럼 사용할 수도 있다.
대부분의 경우에 python에서 list보다 효율적인 데이터 조작이 가능하다.
특히나 data의 입출입이 빈번한 알고리즘에서는 그 효과가 더욱 크다.

  • python에서 collections 라이브러리를 사용하여 deque를 사용할 수 있다.
  • 데크(deque)에 사용할 수 있는 메서드(method)는 다음과 같다.
deque.append(item): item을 데크의 오른쪽 끝에 삽입
deque.appendleft(item): item을 데크의 왼쪽 끝에 삽입
deque.pop(): 데크의 오른쪽 끝 엘리먼트를 가져오는 동시에 데크에서 삭제
deque.popleft(): 데크의 왼쪽 끝 엘리먼트를 가져오는 동시에 데크에서 삭제
deque.extend(array): 주어진 배열(array)을 순환하면서 데크의 오른쪽에 추가
deque.extendleft(array): 주어진 배열(array)을 순환하면서 데크의 왼쪽에 추가
deque.remove(item): item을 데크에서 찾아 삭제
deque.rotate(num): 데크를 num만큼 회전(양수면 오른쪽, 음수면 왼쪽).

Reference
유튜브 나동빈
윤자이 기술블로그
블로그 Leon

profile
한걸음씩

0개의 댓글