[자료구조]스택(Stack), 큐(Queue)

** 스택(Stack)

스택(stack)이란 데이터를 쌓아서 올려놓은 형태의 자료구조

ex) 책상에 쌓여있는 책, 싱크대의 접시

스택은 위의 그림과 같이 아래에서 위로 쌓는 형식이며 가장 최근에 들어온 자료를 top이라고 부른다. 뻥튀기를 꺼낼 때 가장 아래족의 뻥튀기를 꺼내려면 위에서부터 차례대로 뻥튀기를 꺼내야 하는 것처럼 가장 위쪽(최신)의 데이터부터 꺼낼 수 있으며 이러한 구조를 후입선출(LIFO, Last In First Out)의 구조라고 한다. 스택의 경우 자료의 삽입과 삭제는 한 곳(top)에서만 이루어진다.

만약 스택이 비어있을 때 자료를 꺼내려고 시도하면 스택 언더플로우(Stack Underflow)가 발생하고 반대로, 스택이 꽉 차있을 때 자료를 넣으려고 하면 스택 오버플로우(Stack Overflow)가 발생하게 된다.

스택의 활용 예시

1. 웹 브라우저 뒤로가기 : 가장 나중에 열린 페이지부터 뒤로 가기 실행
2. 문서작업에서 Ctrl + Z : 가장 나중에 수정한 내역부터 되돌림
3. 역순 문자열 만들기 : 맨 끝의 문자열부터 차례대로 만들어짐
4. 후위 표기법 계산
5. 재귀적 알고리즘

 

** 큐(Queue)

큐(Queue)란 데이터들이 일렬로 줄 서서 기다리는 것을 연상하면 된다. 놀이기구를 기다리는 줄, 음식점 번호표 같은 것이 대표적인 예다. 정해진 곳(top)에서만 자료의 삽입과 삭제가 이루어지는 스택과는 다르게 큐는 Rear부분에서 자료의 삽입이, Front부분에서 자료의 삭제가 이루어진다. 비비탄 총의 탄창에 비비탄을 넣고 사격 시 가장 먼저 넣었던 비비탄이 먼저 나가는 것처럼 큐는 선입선출(FIFO, First In First Out)의 자료구조를 가진다.

 

 

큐의 활용 예시

1. 은행창구 번호표 대기 : 빠른 번호표를 가진 사람이 먼저 업무를 본다.
2. 프린터 출력 : 가장 먼저 대기열에 오른 프린트가 먼저 출력된다.
3. 컴퓨터 운영체제의 테스크 스케쥴링 : 가장 간단한 형태의 선입선 처리 스케쥴링 저책
4. 너비 우선 탐색(BFS) 알고리즘