Stack과 Queue에 대해

Stack과 Queue

- 단순하면서도 유용한 자료구조(Data Structure)이기 때문에 컴퓨터 시스템 전반에 다양하게 쓰이고 있다.

- 스택과 큐를 구성하는 명령어가 get이나 put등이 아닌 push, pop, offer, pool인 이유는 이 두 자료구조는 자바가 개발되기 이전부터 쓰이던 방식이었기 때문에 다른 프로그래밍 언어에서도 쓰이던 명령어 형식을 따라서이다.

스택

- LIFO(Last In First Out)의 후입 선출 방식 구조를 가지고 있다. 이것은 마지막에 저장된 것을 가장 먼저 꺼낸다는 의미이다.

- 스택은 양 옆이 막혀있는 박스방식이어서 중간에 있는 데이터를 꺼내거나 중간에 데이터를 넣을 수 없고 마지막 데이터만 꺼내거나 넣을 수 있다.

- 수식계산, 수식괄호검사, undo / redo, 뒤로 / 앞으로(웹 브라우저)에 주로 사용되는 자료구조이다.

- 데이터를 넣는 명령은 push, 데이터를 꺼내는 명령은 pop으로 수행한다.

큐

- FIFO(First In First Out)의 선입 선출 방식 구조를 가지고 있다. 이것은 가장 먼저 저장한 것을 가장 먼저 꺼낸다는 의미이다.

- 큐도 양 옆이 막혀있으나, 스택과는 다르게 앞과 뒤가 뚫려있는 파이프방식이어서 FIFO방식이 가능하다.

- 최근 사용문서, 인쇄작업 대기목록, 버퍼(buffer)에 주로 사용되는 자료구조이다.

- 데이터를 넣는 명령은 offer, 데이터를 꺼내는 명령은 poll로 수행한다. 또한 꺼내지 않고 데이터를 확인만 하는 명령은 peek로 수행할 수 있다.

- 큐는 스택과 달리 클래스가 아니라 인터페이스여서 일반적인 new만을 통해 바로 사용이 불가능하고 따로 구현한 클래스의 객체를 생성하여 찾아야 한다. 이는 Java API를 통해 찾거나 스스로 코딩하는 방법이 있다.

Quere의 변형

- 덱(Deque)

양 끝에서 저장(offer)과 삭제(poll)가 가능하다. Stack과 Queue의 결합이라 볼 수 있다.

구현된 클래스로는 ArrayDeque, LinkedList가 있다.

offerLast, pollLast, offerFirst, offerFirst 메소드가 있다.

- 우선순위 큐(Priority Queue)

우선순위가 높은 값(제일 작은 값)부터 꺼낸다.(null은 저장이 불가능하다)

힙 정렬을 이용하여 정렬을 수행한다.(최소값을 찾는 데 유리한 정렬 방법이다.)

ex) 입력 (3, 1, 5, 2, 4) -> 출력 (1, 2, 3, 4, 5)

- 블락킹 큐(Blocking Queue)

큐가 비어있을 때 꺼내는 것을, 가득 찼을 때는 넣는 것을 막아주는 큐이다.

지정된 시간동안 지연(block)시켜주게 된다.

- 우선순위 큐와 블락킹 큐는 주로 멀티 스레드에서 자주 사용된다.