[Backend 개발자 면접 준비] 자료구조 - 스택(Stack) 과 큐(Queue)

스택 (Stack) 이란?

스택은 쌓다라는 의미로, 데이터를 차곡차곡 쌓아 올린 형태의 자료구조이다.

데이터가 순서대로 쌓이며, 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 구조를 가지고 있다.

가장 대표적인 예시로는 프링글스 과자를 생각하면 된다.

 

 

스택은 정해진 방향으로만 쌓을 수 있으며, top으로 정한 곳을 통해서만 접근 할 수 있다.

새로 삽입 되는 자료는 top이 가리키는 가장 맨 위에 쌓이게 되며, 자료를 삭제할 때도 top을 통해서 삭제가 가능하다.

 

여기서 삽입연산을 Push, 삭제 연산을 Pop 라고 하며 이러한 스택 구조를 후입 선출(LIFO - Last In First Out) 구조라고 한다.

 

스택(stack)의 사용 사례

- 웹 브라우저 방문 기록(뒤로가기)

- 실행 취소(undo)

- 역순 문자열 만들기

- 후위 표기법 계산

 

큐 (Queue) 란?

큐는 스택과 다르게 먼저 들어온 것이 먼저 나가는 선입선출(FIFO - First In First Out)의 구조를 가지고 있다.

예시로 카페에서 먼저와 주문한 손님이 음료를 먼저 받고 나가는 것을 생각하면 된다.

 

 

삭제 연산이 수행되는 곳을 프론트(front), 삽입 연산이 이루어지는 곳은 리어(rear)로 FIFO 구조를 위해 스택과 다르게 큐의 한쪽 끝에는 삽입작업이, 다른 한쪽 끝에서는 삭제 작업이 나뉘어서 이루어진다.

 

이때 리어(rear) 에서 이루어지는 삽입 연산을 인큐(Enqueue)라고 하며, 프론트(front)에서 이루어지는 삭제 연산을 디큐(Dequeue) 라고 한다.

 

큐(Queue)의 사용 사례

- 은행 업무

- 대기열 순서와 같은 우선순위의 작업 예약

- 서비스 센터의 대기시간

- 프로세스 관리

 

 

 

 

Reference Link

https://jud00.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%8A%A4%ED%83%9DStack%EA%B3%BC-%ED%81%90Queue%EC%97%90-%EB%8C%80%ED%95%B4%EC%84%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EC%9E%90