큐(Queue)
큐는 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조이다. 이러한 방법을 FIFO라고한다.
ex) 음식점에서 가장 먼저 줄을 선 사람이 제일 먼저 음식점에 입장하는 것)
큐는 스택의 순서와 정반대이다.
큐에서 사용하는 용어
Enqueue: 큐에서 데이터를 넣는 기능
Dequeue: 큐에서 데이터를 꺼내는 기능
Queue()라는 라이브러리
이미 큐의 기능을 하는 Queue라는 라이브러리가 만들어져 있다. 큐를 사용하고자 하면 import queue를 사용하여 라이브러리를 호출하여 하용하면 된다.
import queue
test= queue.Queue() #test변수를 queue형식으로 선언
test.put('first') #test에 'first' 라는 데이터 삽입
test.put('sec') #test에 'sec' 데이터 삽입
test.qsize() # 'first'와 'sec'가 들어가 있음으로 2가 반환
test.get() # 'first' 반환 FIFO에 의해서 먼저 들어간게 호출됨
test.qsize() #'first'가 반환이 되어있어 test에 남아있는 값은 'sec' 따라서 반환되는 값은 1extra)
LifoQueue 마지막에 넣은 값이 가장 먼저 출력되는 큐
import queue
test= queue.LifoQueue() #test변수를 Lifoqueue형식으로 선언
test.put('first') #test에 'first' 라는 데이터 삽입
test.put('sec') #test에 'sec' 데이터 삽입
test.qsize() # 'first'와 'sec'가 들어가 있음으로 2가 반환
test.get() # 'sec' 반환 Lifo에 의해서 늦게 들어간게 가장 먼저 출력(스택과 비슷)
test.qsize() #'sec'가 반환이 되어있어 test에 남아있는 값은 'first' 따라서 반환되는 값은 1extra) 알고리즘이나 운영체제에서 자주 사용됨 !!!
PriorityQueue 우선순위가 정해져 있어 우선순위대로 출력되는 큐
import queue
test= queue.PriorityQueue() #test변수를 PriorityQueue 선언
test.put((10,'first')) #test에 'first' 라는 데이터를 10의 우선순위로 삽입
test.put((3,'sec')) #test에 'sec' 데이터를 3의 우선순위로 삽입
test.put((1,750))#test에 750이라는 값을 1의 우선순위로 삽입
test.qsize() # 'first'와 'sec',750가 들어가 있음으로 3이 반환
test.get() # 우선순위가 가장 낮은 (1,750)이 호출
test.qsize() #(1,750)이 반환이 되어있어 test에 남아있는 값은 'first','sec' 따라서 반환되는 값은 2직접 Queue 구현
queue_list = list() #list 변수 선언
def enqueue(data): #enqueue 함수 만들기
queue_list.append(data) #list에 값 넣어주기
def dequeue(): #dequeue 함수 만들기
data = queue_list[0] #list의 0번째 값을 data에 담기
del queue_list[0] #출력된 데이터 삭제하기
return data #data 반환하기
for index in range(10):
enqueue(index) #list에 [0,1,2,3,4,5,6,7,8,9] 순으로 들어감
len(queue_list) # 10 반환
dequeue() # 0 출력 list안에는 [1,2,3,4,5,6,7,8,9]가 남아있고
len(queue_list) # 9 반환
dequeue() # 1 출력 list안에는 [2,3,4,5,6,,7,8,9]가 남아있다.Queue가 주로 사용되는 곳
멀티 태스킹을 위한 프로세스 스케쥴링 방식을 구현하기 위해서 많이 사용된다.(운영체제)
스택(Stack)
데이터를 제한적으로 접근할 수 있는 구조이다. FILO(First in, Last out),LIFO(Last in, First out) 데이터 관리 방식을 따른다.
ex) 프링글스 과자를 먹을 때 먼저 들어간 감자칩보다 가장 마지막에 들어간 감자칩이 위에있기 때문에 먼저먹는 것과 유사함
스택에서 사용하는 주요 기능
push() : 데이터를 스택에 넣기
pop() : 데이터를 스택에서 꺼내기
대표적인 스택의 활용: 프로세스 구조의 함수 동작 방식
자료구조 스택의 장단점
장점:
- 구조가 단순해서 구현하기 쉽다.
- 데이터 저장/읽기 속도가 빠르다.
단점(일반적인 스택 구현시): - 데이터 최대 갯수를 미리 정해야 한다.
- 저장 공간의 낭비가 발생할 수 있다.
파이썬의 스택 메서드 사용해서 동작원리
test = list() #test 변수 선언
test.append(1) #test에 1 넣기
test.append(2) #test에 2 넣기
test # [1,2]
test.pop() # 2
test # [1]직접 Stack 구현
test = list() #test 변수 선언
def push(data):
test.append(data) #test에 값 넣기
def pop():
data = test[-1] # list 변수의 인덱스에 -1을 넣으면 list의 가장 끝의 값을 반환해준다.
del test[-1] # test의 가장 마지막 값 삭제
return data
for index in range(10):
push(index) #test = [0,1,2,3,4,5,6,7,8,9]
pop() #test의 가장 끝의 값 9 반환
test #test안의 값은 [0,1,2,3,4,5,6,7,8]스택과 큐의 차이
큐는 일반적으로 FIFO(First in, First out) 방식을 사용하지만 스택은 LIFO(Last in, First out) 방식을 사용한다.
