[자료구조] 스택(STACK), 큐(QUEUE) 비교/정리 하기!

스택(STACK)

1. 스택이란?

스택은 "쌓다", "쌓이다"라는 의미로, 데이터를 차곡차곡 쌓아서 후입선출 형태 즉, LIFO(List In First Out) 의 자료구조 입니다.
위의 이미지와 같이 데이터가 아래에서 부터 순서대로 쌓이며 가장 마지막에 쌓아둔 데이터부터 삭제해나가는 구조를 가졌습니다.

2. 스택의 특징

• 스택 내부에는 top을 통해서만 접근이 가능합니다. top은 제일 최상위에 위치한 데이터를 반환합니다.
• 스택에 데이터를 삽입할 때는 push를 이용하여 top 위에 쌓게 됩니다.
• 스택에서 데이터를 삭제할 때는 pop으로 top에 위치한 데이터를 삭제하게 됩니다.

3. 스택의 장단점

• top을 통해 데이터에 접근하기 때문에 접근, 삽입, 삭제가 빠르다.
• top을 통해서만 접근이 가능하기 때문에 데이터를 찾으려면, 모든 데이터를 꺼내면서 탐색해야한다.

4. 스택의 활용 예시

• 웹 브라우저 방문기록(뒤로가기)
• 실행 취소(되돌리기)
• 역순의 문자열 만들기
• 후위 표기법 계산
• 등등

큐(QUEUE)

1. 큐란?

큐는 "줄", "대기 행렬"이라는 뜻으로 스택과는 다르게 먼저 들어온 데이터가 가장 먼저 나가는 선입선출 형태 즉, FIFO(First In First Out) 의 자료 구조입니다.
테이크아웃 카페를 예시로 들어보면 가장 먼저 주문한 손님이 가장 먼저 음료를 받고 나가는 것이 바로 큐의 형태라고 할 수 있습니다.

2. 큐의 특징

• 큐는 삽입, 삭제가 다른 방향에서 이루어집니다.
• 삭제 연산만 수행되는 곳을 프론트(front)
• 삽입 연산만 수행되는 곳을 리어(rear)
• 프론트(front)에서 이루어지는 삭제 연산을 디큐(dnQueue)라고 합니다.
• 리어(rear)에서 이루어지는 삽입 연산을 인큐(enQueue) 라고 합니다.

3. 큐의 장단점

• 큐 역시 스택과 마찬가지로 데이터 접근, 삽입, 삭제가 빠르다
• 또한 마찬가지로 중간에 위치한 데이터에 접근하기가 불가능하다.

4. 큐의 활용 예시

• 데이터를 순서대로 처리해야 할 때
• 너비 우선 탐색(BFS, Breadth-First Search) 구현
• 프로세스 관리
• 대기 순서 관리