알고리즘을 공부하다보면 자주 접하는 용어,
스택(Stack)과 큐(Queue)에 대하여 공부하고 정리한 글입니다.
1. 스택이란(Stack)
"스택을 쌓다", 게임을 좋아하는 사람들이라면 한번쯤 들어봤을 문장이다.
자료구조에서의 스택은 데이터를 차곡차곡 쌓아 올린 형태를 의미한다.
데이터가 쌓이다보니 가장 마지막에 삽입된(쌓인)자료가 가장 먼저 삭제되는 구조를 가지고있다.
조금 더 전문적인 용어로 적어보면 LIFO(Last In First Out)방식으로 동작한다고 한다.
이러한 구조를 가지고 있다보니 스택으로 삽입된 자료의 위치는 자연스럽게 top이 된다.
스택에서 top을 통해 삽입하는 연산을 "push", top을 통해 삭제하는 연산을 "pop"이라고 한다.
스택에 관해서 아래와 같은 용어를 들어본적이 있을 것이다.
모르는게 있으면 스택오버플로우에 검색해봐
stack underflow? stack overflow?
스택이 비어있을 때 자료를 빼려고(pop)하면 stack underflow가 발생하고,
반대로 스택이 꽉 차있을 때 자료를 넣으려고(push)하면 stack overflow가 발생하게된다.
그러면 이제 이 스택을 활용 할 수 있는 곳이 어디에 있을까?
사실 스택은 이미 우리 생활에서 자주 사용 중이다.
제일 대표적으로는 아래 2가지이며,
- 웹 브라우저 방문기록(뒤로가기) : 가장 나중에 열린 페이지부터 다시 보여준다.
- 실행 취소(undo) : 가장 나중에 실행된 것부터 실행을 취소한다.
알고리즘 관련해서는 다음과 같이 3가지가 더 있다.
- 역순 문자열 만들기
- 후위 표기법 계산
- 재귀적 알고리즘
2. 큐란(Queue)
"큐가 안잡히네", 이또한 게임을 좋아하는 사람들이라면 익숙한 문장일 것이다.
큐(Queue)는 스택(Stack)과 다르게 먼저 들어온 것이 먼저 나가는 구조를 가지고 있다.
스택이 LIFO(Last In First Out)였다면 큐는 FIFO(First In First Out)이다.
간단한 예시를 들어보자면
- 은행에 먼저 온 사람이 창구에서 먼저 업무를 처리하는 경우
- 놀이동산에서 줄을 서서 기다리는 경우
- 탄알집에 넣은 순서대로 탄이 발사되는 경우
이러다보니 한 쪽(top)에서만 이루어지는 스택과 달리,
큐는 한쪽 끝에서는 삽입 작업이, 반대쪽 끝에서는 삭제 작업이 이루어진다.
삽입 작업이 이루어지는 곳을 리어(rear), 삭제 작업이 이루어지는 곳을 프론트(front)라고 부르기도한다.
프론트? 백? 그 프론트 아닙니다.
또한 리어(rear)에서 이루어지는 삽입 연산을 인큐(Enqueue)라고 부르며, 프론트(front)에서 이루어지는 삭제 연산을 디큐(Dequeue)라고 부른다.
정리를 하면 큐에서 프론트 원소는 가장 먼저 큐에 들어왔던 첫 번째 원소이며,
리어 원소는 가장 늦게 큐에 들어온 마지막 원소이다.
큐의 활용처는 다음과 같다.
- 데이터를 입력된 순서대로 처리해야 할 때
- BFS 알고리즘
- 프로세스 관리
- 대기 순서 관리
마지막으로 다시 한번 정리하면 다음과 같다.
스택이란 LIFO(Last In First Out) 구조를 가지고 있으며,
한 쪽(top)에서 자료를 넣고(push), 뺄(pop) 수 있다.
대표적인 예시로는
- 웹 브라우저 방문기록
- 실행 취소(undo)이다.
큐는 FIFO(First In First Out) 구조를 가지고 있으며,
자료를 넣는 연산을 인큐(Enqueue)라고 부르며 리어(rear)에서 이루어진다.
자료를 빼는 연산을 디큐(Dequeue)라고 부르며 프론트(front)에서 이루어진다.
대표적인 예시로는
- 은행업무
- 서비스 센터의 대기이다.
