[Concept] 배열 - 큐와 스택

#자료구조_배열

 

[파이썬의 배열]

• 리스트 활용
• 1차원, 2차원까지는 알고 있으면 좋다.
• 같은 종류의 데이터를 순차적으로 저장한다.

 

Q. 왜 필요한가?

A. 같은 종류의 데이터를 효율적으로 관리하기 위해 사용하기 위해!

 

[단점]

• 데이터 추가/삭제의 어려움
• 미리 최대 길이를 지정해야 하는 점
  • Q. Why?
    A. 삭제 시, 뒤에 있던 데이터를 앞당겨야하기 때문이다.

 

[장점]

• 인덱스를 통해 빠른 접근 가능하다.
• 첫 데이터의 위치에서 상대적인 위치로 데이터에 접근(인덱스 번호로 접근)한다.

---

# 자료구조_큐(Queue)

[큐]

• 줄을 서는 행위와 유사
• FIFO(First-In, First-Out) 또는 LILO(Last-in, Last-Out) 방식. <--> 스택
  • Q.큐에 값을 넣은 상태에서, 데이터를 꺼내라는 명령을 내리면?
    A. 가장 먼저 들어온 데이터를 자동으로 꺼내는 것!

 

[큐의 기능]

• 큐에 데이터를 넣는 기능 "Enqueue"
• 큐에서 데이터를 꺼내는 기능 "Dequeue"
• test 사이트 : https://visualgo.net/en/list

 

[파이썬 queue 라이브러리]

 

1. Queue() : 일반적인 큐. FIFO

 # put()과 get() 
 import queue 
 data_queue = queue.Queue() 
 data_queue.put("coding") 
 data_queue.put(1) 
 
 data_queue   # <queue.Queue at 0x22d266a0588>
 data_queue.qsize() # 2 
 
 data_queue.get() # 먼저 들어간 "coding"을 꺼낸다.

 

2. LifoQueue() : LIFO(Last-In, First-Out)

• 마지막에 넣은 것이 먼저 꺼내진다.

import queue 
data_queue = queue.LifoQueue() 

data_queue.put("coding") 
data_queue.put(1) 

data_queue.qsize() # 2

data_queue.get() # 마지막에 들어간 1을 꺼낸다

 

 

3. PriorityQueue()

• 데이터를 추가할 때 우선순위 번호를 함께 지정하여, 해당 배열에서 데이터 추출할 때 우선순위에 따라 추출한다. 

import queue 
data_queue = queue.PriorityQueue() 

data_queue.put((10, "korea")) # 튜플로 입력해줘야함 
data_queue.put((5,1)) # 우선순위 5번째, 데이터 1 
data_queue.put((15,"china")) 

data_queue.qsize() # 3 

# 우선순위가 높은 1이 먼저 출력됨 
data_queue.get() # (5,1) 출력

Q. 어디에 큐가 많이 쓰일까?

A. 운영체제에서는 프로세스를 스케쥴링하는 방식이 매우 중요함.

멀티 태스킹을 위한 프로세스 스케쥴링 방식을 구현하기위해 많이 사용됨 -> 더 알아봐야 할듯!

 

 

[리스트 변수로 큐를 다루는 enqueue, dequeue 기능 구현]

queue_list = list()

def enqueue(data):
    queue_list.append(data)
    
def dequeue():
    data = queue_list[0] # 가장 먼저 들어가있는 데이터.
    del queue_list[0]
    return data
    
for data in range(10):
	enqueue(data)

queue_list	# [0,1,2,3,4,5,6,7,8,9]
dequeue()	# 0

 

[정리]

• queue의 기본 구조는 FIFO.
• 변형된 구조는 우선순위 큐, LIFO 큐
• enqueue(), dequeue()도 알아두자.
• enqueue()엔 append() 를,
  dequeue()엔 첫번째 데이터를 인덱스로 접근해서 삭제(del)하고 해당 data를 return

---

# 자료구조_스택(Stack)

[스택 구조]

• 데이터에 제한적으로 접근할 수 있는 구조
  • 한 쪽 끝에서만 자료를 추가/제거 가능
  • 가장 나중에 쌓은 데이터를 가장 먼저 빼내는 LIFO(Last In, First Out) , FILO 데이터 관리방식
    -> 책 쌓는 것으로 이해하기
• 주요 기능은 push(), pop()

 

[대표적인 스택의 활용]

컴퓨터 내부의 프로세스 구조의 함수 동작 방식 -> 즉, 실행되고있는 프로그램 내부에는 다양한 함수들이 있다. 이 함수들이 동작하는 방식을 처리할 때 자료구조 "스택"이 쓰이고 있다. 쉽게 말해, 프로세스 함수들이 호출되면서 그 함수가 쌓이는 동작 방식이 스택 구조라는 것! - 현재 설명한 프로세스 스택의 구조는 운영체제 과목에서 더 깊게 배울 것이다.

 

[장점]

- 구조가 단순해서, 구현이 쉽다. - 데이터 저장/읽기 속도가 빠르다.

 

[단점] (일반적인 스택 구현시)

•  데이터 최대 갯수를 미리 정해야 한다. (파이썬의 경우 재귀 함수는 1000번까지만 호출이 가능함)
  • 저장 공간의 낭비가 발생할 수 있음

Q. WHY?

A. 미리 최대 갯수만큼 저장 공간을 확보해야하므로, 평소에는 적은 공간만 쓰더라도 미리 공간확보 차원에서 크게 정함.

 

 

[스택 구현]

data_stack = list() 
data_stack.append(1) 
data_stack.append(2) 

data_stack # [1,2] 

data_stack.pop() # 2 -> 마지막에 넣은 값을 먼저 꺼낸다.

[리스트 변수로 스택을 다루는 pop, push 기능 구현해보기]

(pop, push 함수 사용하지 않고 직접 구현해보기) 

stack_list = list() 
def push(data): 
	stack_list.append(data) 
    
def pop(): 
	data = stack_list[-1] 
    del stack_list[-1] 
    return data 
    
for index in range(10): 
	push(index) 

stack_list #[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 
pop() # 9