Stack, Queue에 대해 알아보자.

목차
1. Stack이란?
2. Queue란?
3. Stack과 Queue의 차이점

 

1. Stack이란?

Stack이란 쌓아 올린다는 것을 의미한다. 따라서 책을 쌓는 것처럼 차곡차곡 쌓아 올린 형태의 자료구조를 말한다.

스택은 아래의 사진처럼 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을 수 있고, top으로 정한 곳을 통해서만 접근을 할 수 있다. top에는 가장 위에 있는 자료는 가장 최근에 들어온 자료를 가리키고 있으며, 삽입되는 새 자료는 top이 가리키는 자료의 위에 쌓이게 된다. 스택에서 자료를 삭제할 때도 top을 통해서만 가능하다. 스택에서 top을 통해 삽입하는 연산을 'push', top을 통한 삭제하는 연산을 'pop'이라고 한다.

스택은 시간 순서에 따라 자료가 쌓여서 가장 마지막에 삽입된 자료가 가장 먼저 삭제된다는 구조적 특징을 가지게 된다.

 

이러한 스택의 구조를 후입선출(LIFO, Last In First Out) 구조라고 한다.

 

그리고 비어있는 스택에서 원소를 추출하려고 할 때 stack underflow라고 하며, 스택이 넘치는 경우 stack overflow라고 한다.

 

💡스택의 활용 예시

• 웹 브라우저 방문 기록(뒤로가기) : 가장 나중에 열린 페이지부터 다시 보여준다.
• 실행 취소 : 가장 나중에 실행된 것부터 실행을 취소한다.
• 깊이 우선 탐색(DFS)

2. Queue란?

Queue란 줄을 서서 기다리는 것을 의미한다. 따라서 일상생활에서 놀이동산에서 줄을 서서 기다리는 것, 은행에서 먼저 온 사람의 업무를 창구에서 처리하는 것과 같이 선입선출(FIFO, First In First Out) 방식의 자료구조를 말한다.

정해진 한 곳(top)을 통해서 삽입, 삭제가 이루어지는 스택과는 달리 큐는 한쪽 끝에서 삽입 작업이, 다른 쪽 끝에서 삭제 작업이 양쪽으로 이루어진다.

 

이때 삭제 연산만 수행하는 곳을 'front', 삽입 연산만 이루어지는 것을 'rear'로 정하여 각각의 연산 작업만 수행된다. 이때, 큐의 리어에서 이루어지는 삽입 연산을 enqueue, 프론트에서 이루어지는 삭제 연산을 dequeue라고 부른다.

 

즉, 큐에서 프론트는 가장 먼저 큐에 들어왔던 첫 번째 원소가 되는 것이며, 리어는 가장 늦게 큐에 들어온 마지막 원소가 되는 것이다.

 

 

💡 큐의 활용 예시

• 은행 업무
• 콜센터 고객 대기시간
• 너비 우선 탐색(BFS)

 

3. Stack과 Queue의 차이점

1. 구조적 특징

• Stack : 후입선출(LIFO) 구조를 가짐. 가장 최근에 삽입된 항목이 가장 먼저 삭제됨, 자료를 쌓아 올리듯이 한쪽 끝에서만 삽입, 삭제 작업이 이루어짐.
• Queue : 선입선출(FIFO) 구조를 가짐. 가장 먼저 삽입된 항목이 가장 먼저 삭제됨, 삽입은 한쪽 끝에서 이루어지고, 삭제는 다른 쪽 끝에서 이루어짐.

2. 작업 방향

• Stack : 삽입과 삭제 작업이 같은 방향(top)에서 이루어짐.
• Queue : 삽입은 한쪽 끝에서, 삭제는 다른 쪽 끝에서 이루어짐.

3. 연산 작업

• Stack : push(삽입), pop(삭제) 연산이 주로 사용됨.
• Queue : enqueue(삽), dequeue(삭제) 연산이 주로 사용됨.