[선형자료구조] 스택, 큐, 데크

| 스택

종류	구분	내용	언제 쓰는 게 좋을까
Stack	특징	- 후입선출(LIFO) - top / bottom - push, pop, peek	- 데이터가 입력된 순서의 역순으로 처리되어야 할 때 Ex. - 함수 콜스택,역추적,인터럽트 처리 - 재귀, DFS - 괄호 검사, 후위 연산, 문자열 역순출력, 실행취소
	장점	- top을 통한 접근, 삽입, 삭제가 빠르다. (시간복잡도 O(1))
	단점	- top 이외의 데이터에 접근 불가(탐색x)

- 스택은 마치 옷을 겹겹히 쌓듯 데이터를 쌓아 올렸다가 맨 위에서부터 꺼내는 구조이다.

- 스택에 대한 알고리즘 문제를 보면, "괄호 검사", "후위 연산", "문자열의 역순 출력", "실행 취소"와 같이

[ 넣었다가 위에서부터 빼는 행위 ]를 통해 문자열의 특정 문자를 검사하고, 어떤 행위를 역전 시키는 걸 볼 수 있다.

~~- 일상 생활에서 볼 수 있는 또다른 스택의 예시는, 제가 좋아하는 프링글스...위에서부터 뽑아먹는 재미가...~~

문제집: 스택 (kmg8280)

www.acmicpc.net

종류	구분	내용	언제 쓰는 게 좋을까
Queue	특징	- 선입선출(FIFO) - front / rear - enqueue(offer, add), dequeue(poll, remove)	- 데이터를 순차적으로 삽입하고 꺼낼 때 Ex. - 요세푸스 순열, 프로세스 관리, 대기 순서 관리(프린트 대기열) - BFS
	장점	- front/rear를 통한 접근, 삽입, 삭제가 빠르다. (시간복잡도 O(1))
	단점	- 중간 위치의 데이터에 접근 불가

- 큐는 스타벅스 앞에 줄을 서고 있는 사람들처럼 먼저 들어간 데이터가 먼저 빠지는 구조이다.

- 원형 큐는 원형 연결리스트와 구조적으로 동일하다. 앞과 끝은 있으나 그걸 원형으로 벤딩해놓은 형태.

(자바에서는 그러나 원형 큐도 딱히 지원하지 않기 때문에 차라리 데크를 쓰는 편이 수월한 것 같다.)

- 자바에서는 큐는 인터페이스로 제공하고, 큐를 구현하는 객체를 쓸 수 있는데, LinkedList를 쓰면 된다.

- 한 가지 알아두어야 할 점은, 큐에 데이터를 삭제할 때

poll()를 쓰면 데이터가 없어도 null을 반환하지만,

remove()를 쓰면 데이터가 없을 때 예외가 발생하기 때문에, 안전성을 위해서 remove()를 쓰는 게 더 좋다는 것!

문제집: Queue (jhlee1108)

www.acmicpc.net

종류	구분	내용	언제 쓰는 게 좋을까
Deque	특징	= double-ended queue, stack + queue - 양쪽에서 삽입 삭제가 가능 - front / rear - add(offer), remove(poll) - addFirst, addLast, removeFirst, removeLast	- 데이터를 앞, 뒤쪽에서 삽입/삭제 처리 필요할 때 Ex. 팰린드롬 찾기, 카드묶음의 순서 변경하기 등
	장점	- front / rear 양쪽을 통한 삽입, 삭제가 빠르다 (시간복잡도 O(1)) - Stack, Queue와 달리 idx를 통해 임의 원소에 접근 가능 - 새로운 원소 삽입 시 메모리를 재할당하지 않고 메모리 블록을 재할당하여 삽입한다.(chunk 사용)
	단점	- 중간 위치에 데이터를 삽입, 삭제가 어렵다
	Scroll	- 입력제한 데크 - 한 쪽의 입력을 제한한 데크
	Shelf	- 출력제한 데크 - 한 쪽의 출력을 제한한 데크

- 데크는 마치 양 옆이 열린 파이프와 같은 형태라고 생각하면 쉬운 것 같다.

- 양쪽에서 데이터를 삽입하고 삭제할 수 있으며, 필요에 따라 양 옆을 제한 시켜 사용할 수도 있다.

- 데크 또한 큐와 마찬가지로 삭제를 할 때, remove()를 쓰는 것이 안전성의 측면에서 더 좋다.

1. Queue

2. Stack

	push()	peek()	pop()	size()
Stack	O(1)	O(1)	O(1)	O(1)