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

스택(Stack)과 큐(Queue)는 컴퓨터 과학에서 가장 기본적인 자료구조 중 하나로 프로그래밍에서 가장 많이 사용됩니다. 스택과 큐는 각각의 구조와 연산이 다르기 때문에, 효율적인 사용을 위해서는 자료구조를 잘 이해하고 활용하는 것이 중요합니다. 이 글에서는 스택과 큐의 개념과 특징, 활용 예시에 대해 알아보겠습니다.

---

스택(Stack)이란

1. 스택의 개념

스택은 쌓아 올리는 것을 의미합니다.

따라서 스택 자료구조는 데이터를 쌓아 올리는 형태의 자료구조입니다.

 

2. 스택의 특징

• 후입선출(LIFO, Last In First Out) 구조를 가집니다.
• 데이터의 삽입과 삭제가 한쪽(Top)에서만 이루어집니다.
• 가장 먼저 삽입된 데이터가 가장 나중에 삭제됩니다.
• 일반적으로 스택에 데이터를 삽입하는 것을 푸시(Push), 스택에서 데이터를 꺼내는 것을 팝(Pop)이라고 합니다. 

 

3. 스택의 활용 예시

• 웹 브라우저 방문기록 (뒤로 가기) : 사용자가 방문한 페이지를 스택에 저장하여 뒤로 가기 버튼을 누를 때 스택에서 이전 페이지를 꺼내어 보여줍니다.
• 역순 문자열 만들기 : 문자열을 스택에 삽입한 뒤, 스택에서 원소를 꺼내면 역순으로 된 문자열을 얻을 수 있습니다.
• 실행 취소 (undo) : 사용자가 수행한 작업을 스택에 저장하여 실행 취소를 수행할 때 스택에서 이전 상태를 꺼내어 복구합니다.
• 깊이 우선 탐색(DFS, Deep-First Search) 구현

 

---

큐(Queue)란

1. 큐의 개념

큐는 줄을 서서 기다리는, 대기 줄을 의미합니다.

즉, 큐 자료구조는 데이터가 입력된 순서대로 처리하는 형태의 자료구조입니다.

 

2. 큐의 특징

• 선입선출(FIFO, First In First Out) 구조를 가집니다.
• 스택과는 다르게 입구와 출구가 나뉘어져 있습니다.
• 리어(Rear)에서 데이터의 삽입이, 프론트(Front)에서 데이터의 삭제가 이루어집니다.
• 가장 나중에 들어온 데이터가 가장 나중에 삭제됩니다.
• 일반적으로 큐에 데이터를 삽입하는 것을 인큐(Enqueue), 큐에서 데이터를 삭제하는 것을 디큐(Dequeue)라고 합니다.

 

3. 큐의 활용 예시

• 인쇄 대기열
• 은행 업무
• 프로세스 관리
• 너비 우선 탐색(BFS, Breadth-First Search) 구현

 

---

정리

요약

 

---

함께 보면 좋은 글

[자료구조] 자료구조(Data Structure)란?