[자료구조/알고리즘] 배열(Array)/큐(Queue)/스택(Stack)

배열 (Array)
* 데이터를 나열하고, 각 데이터를 인덱스에 대응하도록 구성한 데이터 구조
* 파이썬에서는 리스트 타입이 배열 기능을 제공함

 

[배열은 왜 필요할까?]

• 같은 종류의 데이터를 효율적으로 관리하기 위해 사용
• 같은 종류의 데이터를 순차적으로 저장
• 장점
  • 빠른 접근 가능
  • 첫 데이터의 위치에서 상대적인 위치로 데이터 접근(인덱스 번호로 접근)
• 단점
  • 데이터 추가/삭제의 어려움
  • 미리 최대 길이를 지정해야 함

---

큐 (Queue)

[큐 구조]
* 줄을 서는 행위와 유사
* 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조
  - 음식점에서 가장 먼저 줄을 선 사람이 제일 먼저 음식점에 입장하는 것과 동일
  - FIFO(First-In, First-Out) 또는 LILO(Last-In, Last-Out) 방식으로 스택과 꺼내는 순서가 반대

 

[알아둘 용어]
* Enqueue: 큐에 데이터를 넣는 기능
* Dequeue: 큐에서 데이터를 꺼내는 기능

 

[파이썬 queue 라이브러리 활용해서 큐 자료 구조 사용하기]
* 프로그램을 작성할 때 프로그램에 따라 적합한 자료 구조를 사용
  - Queue(): 가장 일반적인 큐 자료 구조
  - LifoQueue(): 나중에 입력된 데이터가 먼저 출력되는 구조 (스택 구조라고 보면 됨)
  - PriorityQueue(): 데이터마다 우선순위를 넣어서, 우선순위가 높은 순으로 데이터 출력
* 일반적인 큐 외에 다양한 정책이 적용된 큐들이 있음

 

[어디에 큐가 많이 쓰일까?]
- 멀티 태스킹을 위한 프로세스 스케쥴링 방식을 구현하기 위해 많이 사용됨 (운영체제 참조)
- 큐의 경우에는 장단점 보다는 (특별히 언급되는 장단점이 없음), 큐의 활용 예로 프로세스 스케쥴링 방식을 함께 이해해두는 것이 좋음

 

import queue

data_queue = queue.Queue()
data_queue = queue.LifoQueue()
data_queue = queue.PriorityQueue()

data_queue.put("xxx")				#Queue, LifoQueue
data_queue.put((우선순위N, "xxx"))		#PriorityQueue
data_queue.qsize()
data_queue.get()

list_queue = []   	#프린터
list_queue.pop(0)   	#제일 첫번째꺼 삭제

from collections import deque   #리스트보다 효율적임
deque_queue = deque()
deque_queue.popleft()
deque_queue.reverse()
list(deque_queue)

---

스택 (Stack)
* 데이터를 제한적으로 접근할 수 있는 구조
  - 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조
* 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 데이터 구조
  - 큐: FIFO 정책
  - 스택: LIFO 정책

 

[스택 구조]
* 스택은 LIFO(Last In, Fisrt Out) 또는 FILO(First In, Last Out) 데이터 관리 방식을 따름
  - LIFO: 마지막에 넣은 데이터를 가장 먼저 추출하는 데이터 관리 정책
  - FILO: 처음에 넣은 데이터를 가장 마지막에 추출하는 데이터 관리 정책

* 대표적인 스택의 활용
  - 컴퓨터 내부의 프로세스 구조의 함수 동작 방식

* 주요 기능
  - push(): 데이터를 스택에 넣기
  - pop(): 데이터를 스택에서 꺼내기
  

[스택 구조와 프로세스 스택]
- 스택 구조는 프로세스 실행 구조의 가장 기본
  - 함수 호출시 프로세스 실행 구조를 스택과 비교해서 이해 필요

 

[자료 구조 스택의 장단점]

• 장점
  • 구조가 단순해서, 구현이 쉽다.
  • 데이터 저장/읽기 속도가 빠르다.
• 단점 (일반적인 스택 구현시) 
  
  • 데이터 최대 갯수를 미리 정해야 한다. 
    
    • 파이썬의 경우 재귀 함수는 1000번까지만 호출이 가능함
  • 저장 공간의 낭비가 발생할 수 있음
    
    • 미리 최대 갯수만큼 저장 공간을 확보해야 함
• 스택은 단순하고 빠른 성능을 위해 사용되므로, 보통 배열 구조를 활용해서 구현하는 것이 일반적임. 이 경우, 위에서 열거한 단점이 있을 수 있음

stack = [] 
#또는
stack = list()

stack.append("xxx")		#push와 같은 역할
stack.pop()   			#제일 마지막꺼 삭제
stack[-1]   			#제일 마지막꺼 확인