[자료구조] Stack & Queue

Stack

• 후입선출 (LIFO) 구조
• 입력(push), 출력(pop또는 poll), top 원소 확인(peek), 해당 값이 스택에서 몇 번째에 있는지(search) 등
• Random Access(비순차적 접근) 불가
• 삽입/숙제의 시간복잡도는 O(1)
• 재귀 알고리즘 사용 시 유용
• 사용 : 함수의 콜스택, 문자열 역순 출력, 연산자 후위표기법 등

---

Queue

• 선입선출 (FIFO) 구조
• 큐의 가장 첫 원소를 front, 끝 원소를 rear라고 부름
• 들어올 때 rear로 들어오지만(enQueue), 나갈 때는 front부터 빠지는(deQueue) 특성을 지님
• 사용 : BFS, Buffer, 캐시 구현 등
• Java Collection에서 Queue는 인터페이스이다. 이를 구현하고 있는 Priority Queue 등 사용 가능
• 원형 큐, 우선순위 큐, 데크(Deque) 등이 있음

Java Collection 시간복잡도

---

Circular Queue

• 선형 큐에서 배열의 앞 부분이 비게되는 한계점을 해결하기 위해 구조화한 자료구조
• 큐의 마지막 인덱스에서 다음 인덱스로 넘어갈 때 (rear+1)%MAX_QUEUE_SIZE가 되며 첫 인덱스부터 다시 데이터 삽입이 가능
• 포화상태일 경우, front == (rear+1)%MAX_QUEUE_SIZE

---

Priority Queue

• 원소들에 우선순위를 매겨서 큐에 집어넣음
• 삽입 순서와 관계없이 우선순위가 높은 원소부터 출력된다.
• 배열, 연결리스트, 힙으로 구현 가능 -> 힙으로 구현하는 것이 가장 효율적!

자료구조	정렬된 배열 / 순서 없는 배열	정렬된 연결 리스트 / 순서 없는 연결리스트	힙
삽입	O(n)/O(1)	O(n)/O(n)	O(logn)
삭제	O(1)/O(n)	O(1)/O(n)	O(logn)

---

Deque

• 양쪽에서 모두 삽입/인출이 가능한 큐
• 스택과 큐의 장점을 가지고 만들어짐
• 입력이 한 쪽에서만 가능하고 출력은 양쪽 다 가능한 경우 Scroll
• 출력이 한 쪽에서만 가능하고 입력이 양쪽에서 다 가능한 경우 Shelf