스택(Stack)
개념
스택(stack)이란 어떠한 자료를 쌓아서 올려놓은 형태의 자료구조입니다.
책상에 쌓여있는 책들이나 싱크대의 접시를 예시로 들 수 있습니다.
특징
스택은 위의 그림과 같이 아래에서 위로 쌓이는 형식이며 가장 최근에 들어온 자료를 top이라고 부릅니다. 뻥튀기를 꺼낼 때 가장 아래쪽의 뻥튀기를 꺼내려면 위에서부터 차례대로 뻥튀기를 꺼내야 하는 것처럼 가장 위쪽(최신)의 데이터부터 꺼낼 수 있으며 이러한 스택의 구조를 후입선출(LIFO, Last In First Out) 의 구조라고 합니다. 즉, 스택의 경우 자료의 삽입과 삭제는 한 곳(top) 에서만 이루어지게 됩니다.
만약 스택이 비어있을 때 자료를 꺼내려고 시도를 하면 스택 언더플로우(Stack Underflow) 가 발생하고 반대로, 스택이 꽉 차있을 때 자료를 넣으려고 하면 스택 오버플로우(Stack Overflow) 가 발생하게 됩니다.
활용 예시
- 웹 브라우저 뒤로가기 : 가장 나중에 열린 페이지부터 뒤로 가기를 실행합니다.
- 문서작업에서 Ctrl+Z : 가장 나중에 수정한 내역부터 되돌립니다.
- 역순 문자열 만들기 : 맨 끝의 문자열부터 차례대로 만들어집니다.
- 후위 표기법 계산
- 재귀적 알고리즘
큐(Queue)
개념
게임을 하시는 분이시라면 “큐가 빨리 안잡히네…” 라는 말의 의미를 아실 겁니다.</br> 큐란 쉽게말해 데이터들이 일렬로 줄 서서 기다리는 것을 뜻하는데,</br> 놀이기구를 기다리는 줄, 음식점 번호표 같은 것을 예시로 들 수 있을 것 같습니다.</br>
특징
정해진 곳(top)에서만 자료의 삽입과 삭제가 이루어지는 스택과는 다르게 큐는 Rear부분에서 자료의 삽입이, Front부분에서 자료의 삭제가 이루어집니다. 비비탄총의 탄창에 비비탄을 넣고 사격 시 가장 먼저 넣었던 비비탄이 먼저 나가는 것처럼 큐는 선입선출(FIFO, First In First Out) 의 자료구조를 가집니다.
활용 예시
- 은행창구 번호표 대기 : 빠른 번호표를 가진 사람이 먼저 업무를 봅니다.
- 프린터 출력 : 가장 먼저 대기열에 오른 프린트가 먼저 출력됩니다.
- 컴퓨터 운영체제의 테스크 스케쥴링 : 가장 간단한 형태의 선입선 처리 스케쥴링 정책
- 너비 우선 탐색(BFS) 알고리즘