Queue와 Stack

Queue 큐

영어권에서 queue는 대기(줄)을 뜻하기도 한다. "나 한 시간 째 줄 서있어"를 영어로 I've been in the queue for an hour라고 한다. 실제로 영국에 갔을 때 웨이팅 리스트를 queue라고 부르기도 했다. 그러면 자료구조에서 큐는 무엇을 뜻할까?

Queue 정의

• queue는 데이터를 저장하는 자료구조 중 하나로, 먼저 저장한 데이터가 먼저 출력되는 선입선출 FIFO(First In First Out)형식으로 데이터를 관리한다.

• 앞서 얘기한 웨이팅 줄을 떠올리면 먼저 줄 선 사람이 먼저 나가게 된다. queue라는 자료구조에서 데이터도 먼저 들어온 데이터가 먼저 나가는 것이다.

• queue의 rear(뒤쪽)에 데이터를 추가하는 것을 enqueue라고 한다.

• queue의 front(앞쪽)에서 데이터를 꺼내는 것을 dequeue라고 한다.

Queue의 구현

• 파이썬에서는 deque라는 queue 모듈이 이미 정의되어 있어서 모듈을 불러와서 사용 가능하다.

• 파이썬에는 deque외에도 queue 라는 모듈이 있지만 약간의 차이가 존재한다. 차이는 다음의 하이퍼링크를 클릭해서 확인해보자 ---> 파이썬 모듈 deque와 queue 차이

• queue는 시간복잡도 문제때문에 Array list가 아닌 Linked list를 기반으로 구현한다.
  

• Array List로 구현할 경우 pop(0)으로 deque를 구현할 수 있지만, 매번 데이터를 앞으로 옮겨줘야 하므로 시간 복잡도가 증가하기 때문이다.

• 파이썬의 deque(Doubly Ended Queue)은 Linked list로 구현되어 있다.

from collections import deque
queue = deque()

#데이터 삽입하기
queue.append(1)
queue.append(2)
queue.append(3)
queue.append(4)

#데이터 출력하기
queue.popleft()
queue.popleft()
queue.popleft()

Deque의 Method

• append(item) : item을 테크 오른쪽 끝에 삽입
• appendleft(item) : item을 데크의 왼쪽 끝에 삽입
• pop() : 데크의 오른쪽 끝 element를 가져오는 동시에 데크에서 삭제
• popleft() : 데크의 왼쪽 끝 element를 가져오는 동시에 삭제
• extend(array) : 주어진 배열을 순환하면서 데크의 오른쪽에 추가
• extendleft(array) : 주어진 배열을 순환하면서 데크의 왼쪽에 추가
• remove(item) : item을 데크에서 찾아 삭제
• rotate(num) : 데크를 num만큼 회전한다 = shift

Stack

컵 쌓기는 cup stacking이라고 부른다. 흔히 쌓여져 있는 구조를 stack이라고 생각하면 된다.

Stack 정의

• stack은 자료구조의 하나로, 시간 순서상 가장 최근에 추가한 데이터가 가장 먼저 나오는 후입선출 LIFO(Last In First Out) 형식으로 데이터를 저장한다.
• 위의 이미지처럼 쌓인 컵을 생각해보자. 맨 아래의 컵은 가장 먼저 쌓였지만 우리는 컵의 더미 중 가장 늦게 들어온 컵인 가장 위의 컵을 먼저 사용하게 될 것이다.
• Stack의 가장 위인 top에 데이터를 추가하는 것을 push라고 하고 top에서 데이터를 추출 하는 것을 pop이라고 한다.

stack = []
stack.append(1)
stack.append(2)
stack.append(3)
stack.append(4)

stack.pop()
stack.pop()
stack.pop()