스택과 큐

책 + 학교 강의 + 인터넷 자료
2021.12.30 수정

스택 (Stack)

1. 스택이란
   LIFO (Last In First Out) 방식을 사용하는 자료구조이다. FILO(First In Last Out)으로도 표현된다.

   스택은 한쪽 끝에서만 데이터의 삽입과 삭제가 이루어진다.

   데이터의 삽입과 삭제가 이루어지는 부분을 top이라 하고,
   그 반대 부분을 bottom이라 한다.

   top의 위치는 동적이다. 컴퓨터에서는 스택 포인터를 통해 변화하는 top의 위치를 저장한다.

2. 스택의 동작
   • push : 스택에 데이터를 삽입
   • pop : 스택에서 데이터를 삭제

3. 스택의 오버플로와 언더플로

   • 오버플로 : 스택이 꽉 차있을 때, 새로운 데이터의 삽입이 발생하는 상태
   • 언더플로 : 스택이 비어있을 때, 데이터의 삭제가 발생하는 상태

4. 스택의 시간복잡도

   스택에 데이터를 push할 때의 시간복잡도 : O(1)
   스택에서 데이터를 pop할 때의 시간복잡도 : O(1)

스택은 함수 호출 또는 수식 계산에서 사용될 수 있다.

큐 (Queue)

1. 큐의 정의
   FIFO (First In First Out) 방식을 사용하는 자료구조이다.

   데이터를 삽입하는 쪽을 rear, 데이터를 꺼내는 쪽을 front

2. 큐의 동작
   • enqueue : 큐에 데이터를 집어넣는 작업
   • dequeue : 큐에서 데이터를 꺼내는 작업 (자료구조인 데크와 발음이 비슷하나 헷갈리지 말자)

3. 큐의 언더플로와 오버플로

   • 오버플로 : 큐가 가득 찬 상태에서 데이터를 삽입할 때 발생
   • 언더플로 : 큐가 빈 상태에서 데이터를 삭제할 때 발생
4. 큐의 시간복잡도
   • enqueue : O(1)
   • dequeue
     a. 데이터를 자동으로 옮기지 않는 경우 : O(1)
     b. 데이터를 자동으로 옮기는 경우 : O(n)

우선순위 큐(Priority Queue)

enqueue할 때 데이터의 우선순위를 부여한 후
dequeue할 때 우선순위가 가장 높은 데이터를 꺼낸다

---

원형 큐 (Circular Queue)

큐의 단점을 보완하기 위한 자료 구조. (디큐할 때 남은 데이터들을 하나씩 앞으로 이동시켜야 함)

• front : 맨 앞 원소의 인덱스, dequeue될 원소의 위치
• rear : 맨 끝 원소 다음의 인덱스, enqueue되는 데이터가 저장되는 위치