오늘의 나보다 성장한 내일의 나를 위해…
스택 Stack
스택(stack)이란 쌓아 올린다는 것을 의미한다.
따라서 스택 자료구조라는 것은 책을 쌓는 것처럼 차곡차곡 쌓아 올린 형태의 자료구조를 말한다.
스택의 특징
스택은 위 사진처럼 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을 수 있고 top으로 정한 곳을 통해서만 접근할 수 있다.
top에는 가장 위에 있는 자료를 가리키고 있으며 삽입되는 새 자료는 top이 가리키는 자료의 위에 쌓이게 된다.
스택에서 자료를 삭제할 때도 top을 통해서만 가능하다.
스택은 시간 순서에 따라 자료가 쌓여서 가장 마지막에 삽입된 자료가 가장 먼저 삭제된다는 구조적 특징을 가지게 된다.
이러한 스택의 구조를 후입선출(LFO, Last-In-First-Out) 구조라고 한다.
비어있는 스택에서 원소를 추출하려고 하면 stack underflow라고 하며 스택이 넘치는 경우 stack overflow라고 한다.
- 스택 오버플로우(stack overflow): 스택이 꽉 차서 더 이상 자료를 push 할 수 없는 경우인데도 push를 하는 경우
- 스택 언더플로우(stack underflow): 스택이 텅 비어있는 경우에 다시 pop을 하여 스택의 값을 빼낼 것을 요구하는 경우
스택 활용 예시
- 웹 브라우저 방문기록 (뒤로 가기): 가장 나중에 열린 페이지부터 다시 보여준다.
- 역순 문자열 만들기: 가장 나중에 입력된 문자부터 취소한다.
- 실행 취소 (undo): 가장 나중에 실해된 것부터 취소한다.
- 후위 표기법 계산
- 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)
큐 Queue
큐는 줄, 혹은 줄을 서서 기다리는 것을 의미한다.
일상생활에서 놀이동산에서 줄을 서서 기다리는 것, 은행에서 먼저 온 사람의 업무를 창구에서 처리하는 것과 같이 선입선출(FIFO, First in First out) 방식의 자료구조를 말한다.
큐의 특징
정해진 한 곳(top)을 통해서 삽입, 삭제가 이루어지는 스택과 달리 큐는 한쪽 끝에서 삽입 작업이, 다른 쪽 끝에서 살제 작업이 양쪽으로 이루어진다.
이때 삭제 연산만 수행되는 곳을 프론트(front), 삽입 연산만 이루어지는 곳을 리어(rear)로 정하여 각각의 연산 작업만 수행된다.
이때 큐의 리어에서 이루어지는 삽입연산을 인큐(enqueue) 프론트에서 이루어지는 삭제연산을 디큐(dequeue)라고 부른다.
큐 활용 예시
- 우선순위가 같은 작업 예약 (프린터의 인쇄 대기열)
- 은행 업무
- 콜센터 고객 대기시간
- 프로세스 관리
- 너비 우선 탐색(BFS) 구현
- 캐시(Cache) 구현
