Stack, Queue, Deque(양면큐), PriorityQueue(우선순위큐)

Stack

스택(stack)이란 어떠한 자료를 쌓아서 올려놓은 형태의 자료구조입니다.

가장 최신의 데이터부터 꺼낼수 있음. 후입선출

자료의 삽입과 삭제는 한곳에서만(top) 이루어지게 됨

• 선입후출 First-In-Last-Out( 마지막데이터가 제일 첫번째로 나감)
• 후입선출 Last-In-First-Out
• Python에서는 리스트로 구현한다.
• 파이썬의 리스트는 스택의 연산을 포함하고 있다.
• 상단값은 top 혹은 head라고 부름
• top이 아닌 안쪽 데이터는 꺼낼 수 없음
• push(v) = 맨 위에 v 값을 넣기 : $O(1)$
• pop() : 맨 위에 있는 값을 뽑기 : $O(1)$
• top() : 맨 위에 있는 값을 조회 : $O(1)$

 

스택이 비어있을 때 자료를 꺼내려고 시도를 하면 스택 언더플로우(Stack Underflow)가 발생하고

반대로, 스택이 꽉 차있을 때 자료를 넣으려고 하면 스택 오버플로우(Stack Overflow)가 발생하게 됩니다.

스택의 활용예시

• 웹브라우저의 뒤로가기 : 가장 나중에 열린페이지 부터 뒤로가기
• ctrl +Z
• 역순문자열 만들기
• 후위표기법 계산

---

Queue ↔️ Stack

큐는 선입선출(FIFO, First In First Out)으로 데이터가 쌓이며, 

데이터를 삽입하는 enqueue과 데이터를 추출하는 dequeue라는 키워드로 데이터를 관리

 

큐는 보편적으로 순서대로 처리해야하는 작업을 임시로 저장해두는 버퍼로서 사용됨

대부분의 버퍼타입이 큐의 형태를 가지고 있음

• 선입선출 First-In-First-Out( 마지막에 들어온 데이터가 가장 마지막에 나감 )
• 후입후출 Last-In-Last-Out
• 스택과 반대되는 특성이 있음
• Python에서는 deque을 사용
• 덱은 큐의 상위 호환 자료구조! 양면큐 
• push(v) = 맨 뒤에 v 값을 넣기 : $O(1)$
• pop() = 멘 앞의 값을 뽑기 : $O(1)$
• front() = 맨 앞의 값을 조회 : $O(1)$

---

Deque( 양면큐 )

덱은 큐,스택의 연산을 포한하고 있다. 양면 큐

 

데크(deque)에 존재하는 메서드(method)는 대략 다음과 같다. https://leonkong.cc/posts/python-deque.html

• 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만큼 회전한다(양수면 오른쪽, 음수면 왼쪽)

---

Priority Queue (큐의 진화형) - 우선순위 큐

노드에 어떤 것이든 담을 수 있다. 단, 노드간에 우선순위가 정해져야한다.(정렬이 가능해야함)

내부적으로 힙이라는 자료구조를 써서 구현됨

힙은 완전이진트리로 이뤄짐

- 트리에서 최상단 노드는 루트노드 

힙의 종류
최대힙 max - heap	최소힙 min - heap
루트 노드 값이 최대	루트 노드값이 최소
클수록 우선순위가 높다.	작을 수록 우선순위가 높다.
	파이썬에서 기본적으로 최소힙 사용 파이썬에선 최대힙 지원안하므로, 사용하려면 -를 붙여주고, -1곱해서 +1로 바꿔줌
	Python에서는 heapq 모듈 사용
	최소 힙으로 최대 힙 구현하기 (Python)

• Python에서는 heapq 모듈 사용
  • 배열 첫번째 인덱스에 루트 위치

  import heapq as hq
  
  min_heap = []
  hq.heappush(min_heap, 456)
  hq.heappush(min_heap, 123)
  hq.heappush(min_heap, 789)
  print("size:", len(min_heap))
  while min_heap:
      print(hq.heappop(min_heap))
  

• 힙을 사용한 정렬이 힙정렬 (Heap Sort) 이다.
• push(v) = v 값을 넣기 : $O(logN)$
• pop() = 가장 우선순위가 높은 값을 뽑기 : $O(logN)$
• top() = 가장 우선순위가 높은 값을 조회 : $O(1)$

 

https://www.youtube.com/watch?v=AjFlp951nz0&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=11&t=62s

https://docs.python.org/3/tutorial/introduction.html#lists

3. An Informal Introduction to Python — Python 3.10.5 documentation