[자료구조]스택, 큐 개념&예시

스택과 큐는 어떠한 정보를 저장하기위한 방식으로 서로 상반된 구조를 가지고 있다.

 

1. 스택(stack)

영어단어에서 유추할 수 있듯이 데이터를 쌓아 올리는 것을 의미한다. 

사진과 같이 데이터를 저장하고 꺼내는 작업이 한쪽에서만 이루어지기 때문에 가장 먼저 저장된 데이터가 가장 마지막에 나오게된다.

이와같은 방식을 후입선출, 즉 LIFO(Last In First Out) 방식이라고 부른다.

 

스택의 바닥을 bottom, 데이터 이동이 일어나는 윗 부분을 top이라 한다.

top에서 이루어지는 데이터를 저장하는 작업은 push, 꺼내는 작업은 pop으로 부른다.

 

활용 예시)

함수 호출 : 기본적으로 함수를 호출하면 스택 구조로 실행된다.

깊이 우선 탐색 : 인접한 노드들을 스택에 저장하면서 탐색한다.

후위 표기법 계산 : 연산자를 만나면 스택에서 피연산자를 꺼내 계산하는 방식으로 사용한다.

 

 

 

2. 큐(queue)

스택과 반대로 데이터가 들어오는 반대 방향에서만 삭제가 일어난다.

은행 창구에서 사람들이 차례를 기다리는 것과 같은 구조로 이루어져있다.

따라서 선입선출, 즉 FIFO(First in First out)의 방식이다.

 

데이터가 삭제되는 곳을 front, 삽입되는 부분을 rear라고 부르며, 각각 수행되는 작업을 dequeue, enqueue라고 부른다.

 

활용 예시)

너비 우선 탐색 : 인접한 노드를 큐에 저장하여 먼저 방문한다.

콜센터 대기열 : 먼저 전화를 건 고객 먼저 전화연결이 되도록 한다.

프린터 대기열 : 여러 문서를 한대의 프린터로 인쇄하는 경우 순서대로 출력된다.

 

 

 

스택과 큐를 사용한 알고리즘  ▶  그래프 탐색 방법, 예시(DFS, BFS)