[Data Structure] Stack(스택)과 Queue(큐) 비교하기!

Stack

LIFO (Last In First Output) : 가장 나중에 들어온 것이 가장 먼저 나간다.

더미처럼 쌓여있는 구조를 생각하면 된다. 그릇이 쌓여있으면 가장 나중에 쌓은 맨 위에 있는 그릇을 가장 먼저 빼는 것은 당연하게 생각할 수 있다.

• pop() : 스택에서 가장 위에 있는 항목을 제거한다.
• push(item) : item 하나를 스택의 가장 윗 부분에 추가한다.

 

Stack 자료 구조의 사용 사례

• 웹 브라우저 뒤로 가기
• 실행 취소 (undo)
• 역순 문자열 만들기
• 후위 표기법 계산 (연산자가 피연산자 뒤쪽에 위치하는 것)

 

큐 (Queue)

FIFO (First In First Out) : 먼저 들어온 것이 먼저 나가는 방법 (선입선출)

카페에 줄서있는 손님들을 생각하면 된다. 긴 줄을 서있는 손님은 먼저 온 손님부터 음료를 받고 나간다.

 

삭제 연산이 수행되는 곳을 프론트 front, 삽입 연산이 이루어지는 곳을 rear라고 한다.

stack에서는 삽입과 삭제가 한 곳에서 이루어졌지만, 큐의 자료구조의 경우 삭제와 삽입이 각각 다른 곳에서 이루어진다.

rear에서 이루어지는 삽입 연산을 Enqueue라고 부르며, front에서 이루어지는 삭제 연산을 Dequeue라고 부른다.

• pop(0) : 왼쪽부터 삭제가 이뤄진다. (디폴트는 오른쪽부터 삭제)
• popleft() : list가 아닌 deque 구조에서 사용가능 (가장 왼쪽 요소 삭제)

 

큐 자료구조의 사용 사례

• 일반적인 가게의 업무 (손님 혹은 물건 진열)
• 대기열 순서와 같은 우선순위의 작업 예약
• 서비스 센터의 대기 시간
• 프로세스 관리

 

 

Ref

---

[자료구조] 스택과 큐에 대해서 알아보자!