자료구조 - 선형구조 - 큐(Queue), 스택(Stack), 덱(Deque)

오늘은 많은 자료구조 중 선형구조 Queue, Stack, Deque에 대해 알아보도록 하겠습니다.

선형구조(Linear Structure)

선형구조란 자료를 구성하는 원소들을 하나씩 순차적으로 나열시킨 형태이다.

• 데이터 간에 순서가 있고 논리적으로 이어져 있는 구조를 의미한다.

1. 큐(Queue)

큐는 선입선출(FIFO, First In First Out) 원칙을 따르는 자료구조. 데이터가 먼저 들어온 순서대로 처리된.

선형 큐(Linear Queue)

• 특징: 일반적인 큐로, 데이터를 한 방향으로만 삽입하고 제거한다.
• 문제점: 삭제된 공간을 재사용할 수 없어 비효율적이다.

원형 큐(Circular Queue)

• 특징: 선형 큐의 문제를 해결하기 위해 고안된 큐로, 마지막 위치와 처음 위치를 연결하여 원형 형태로 만든다.
• 장점: 공간을 효율적으로 활용할 수 있다.
• 사용 사례: 운영체제의 프로세스 스케줄링 등

※ 핵심 원리

• Enqueue: 큐의 뒤쪽 (Rear)에 새로운 데이터를 추가하는 것이다.
• Dequeue: 큐의 앞쪽 (Front)에서 데이터를 제거하는 것이다.

사용할 때 (활용 사례)

- 너비 우선 탐색 (BFS, Breadth-First Search)
- 프린터의 출력 처리
- 우선순위가 같은 작업 예약 (인쇄 대기열)

주의할 점: 큐가 꽉 찼는데 데이터를 넣으려고 하거나, 큐가 비었는데 데이터를 꺼내려고 하면 에러가 발생할 수 있다.

2. 스택(Stack)

스택(Stack)은 LIFO (Last In First Out, 후입선출) 원칙을 따르는 자료구조이다. 가장 늦게 들어온 데이터가 가장 먼저 나가는 구조이다.

※ 핵심 원리

• Push: 스택의 맨 위 (Top)에 새로운 데이터를 추가하는 것이다.
• Pop: 스택의 맨 위 (Top)에 있는 데이터를 제거하는 것이다.
• Peek: 스택의 맨위(Top)에 있는 원소를 반환한다

사용할 때 (활용 사례)

• 함수 호출 스택: 프로그램 실행 시 함수 호출 순서를 관리합니다. 함수가 호출될 때마다 스택에 쌓이고, 실행이 끝나면 스택에서 제거되는 방식으로 동작합니다.
• 웹 브라우저 방문 기록: 뒤로 가기 버튼을 누르면 가장 최근에 방문한 페이지부터 돌아가죠?
• 수식 계산: 괄호 안의 수식을 먼저 계산하는 등 연산자 우선순위를 처리할 때 유용합니다.
• 주의할 점: 스택이 비어있는데 데이터를 꺼내려고 하면 에러가 발생할 수 있다.

3. 덱(Deque)

덱(Deque, Double-Ended Queue)은 큐와 스택의 장점을 합쳐놓은 자료구조이다. 양쪽 끝에서 데이터를 넣고 뺄 수 있기 때문에, 큐와 스택보다 훨씬 더 유연하게 데이터를 관리할 수 있다는 장점이 있다.

※ 핵심 원리

• addFront / removeFront: 덱의 앞 (Front)에서 데이터를 추가/삭제한다.
• addRear / removeRear: 덱의 뒤 (Rear)에서 데이터를 추가/삭제한다.

사용할 때 (활용 사례)

• 스택과 큐의 조합
• 회문 검사
  주의할 점: 덱을 사용할 때는 삽입과 삭제 연산이 양쪽에서 가능하므로, 어느 방향에서 연산이 이루어지는지 명확하게 정의해야 한다. 또한, 덱의 크기가 제한된 경우, 공간이 가득 찼을 때 새로운 데이터를 추가하려고 하면 오류가 발생할 수 있다.

핵심 요약

자료구조	특징	언제 사용할까?
큐(Queue)	FIFO (First In First Out, 선입선출)	너비 우선 탐색 (BFS), 프린터 출력 처리, 우선순위가 같은 작업 예약 (인쇄 대기열)
스택(Stack)	LIFO (Last In First Out, 후입선출)	함수 호출 스택, 웹 브라우저 방문 기록, 수식 계산
덱(Deque)	양쪽 끝에서 삽입/삭제 가능	스택과 큐의 조합이 필요할 때, 회문 검사