Stack과 Queue

Stack

마지막에 넣은 게 먼저 나오는 LIFO(Last In First Out) 구조의 자료구조이다. LIFO가 전부 Stack은 아니고 삽입, 삭제, 조회는 무조건 Top에서만 이루어지고 중간 삭제/임의 접근 없음 제약을 지킬 때 Stack이라고 부른다.

 

배열 혹은 연결 리스트로 구현한다. top을 배열의 끝 혹은 연결리스트의 머리에 두고 push/pop 연산을 실행한다.

연결리스트로 구현한 경우 노드 오버헤드/포인터 추적으로 인한 오버헤드가 생겨 일반적으로 배열을 기반으로 구현한다.

Stack

 

Queue

먼저 넣은 게 먼저 나오는 FIFO(First In First Out) 구조의 자료구조이다. Stack과 마찬가지고 FIFO면 모두 Queue가 아니라 삽입은 rear에, 삭제/조회는 front에서 이루어지고 우선순위/중간 삭제 없음 제약을 지킬 때 Queue라고 부른다.

 

Stack과 마찬가지로 배열 혹은 연결 리스트로 구현한다. Stack처럼 대부분은 배열로 구현된다. 하지만 일반적인 배열이 아닌 원형 배열을 기반으로 head/tail 인덱스만 이동하는 식으로 구현된다.

Queue

 

변형

Deque

양 쪽에서 삽입/삭제 연산이 가능한 Queue의 변형이다.

Deque

 

PriorityQueue

이름에 Queue가 들어갔지만 사실은 먼저 들어오는 데이터가 아닌 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다. 이전에 작성했던 Heap으로 구현된다.

 

참고

https://www.geeksforgeeks.org/dsa/stack-data-structure/

Stack Data Structure - GeeksforGeeks

 

https://www.geeksforgeeks.org/dsa/queue-data-structure/

Queue Data Structure - GeeksforGeeks

https://www.geeksforgeeks.org/dsa/deque-set-1-introduction-applications/

Deque Data Structure - GeeksforGeeks