(4) Stack과 Queue

1. Stack과 Queue

- Stack은 LIFO(Last In First Out)이고, Queue는 FIFO(First In First Out)이다.

 

- Stack은 ArrayList로, Queue는 LinkedList로 구현하는 것이 좋다. Queue 또한 ArrayList로 구현해도 되지만

데이터 삭제를 할 때 공간을 다시 채워주어야 하기 때문에, LinkedList가 유리하다.

 

 

- Stack의 메서드는 아래와 같다.

( 중요한 부분만 적었다. 상세한 내용은 자바의 정석 604p를 참고하자. )

 

(1) Object peek()

: Stack의 맨 위에 있는 저장된 객체를 반환한다. pop()과 달리 객체를 꺼내지는 않음

( 만약 비어있다면, EmptyStackException 발생 )

 

(2) Object push(Object item)

 

 

- Queue의 메서드는 아래와 같다.

( 중요한 부분만 적었다. 상세한 내용은 자바의 정석 605p를 참고하자. )

 

(1) boolean add(Object o)

 

(2) boolean offer(Object o)

: Queue에 객체를 저장한다.

 

(3) Object poll()

: Queue에서 객체 꺼내서 반환한다.

 

(4) Object element()

: 삭제없이 요소를 읽어온다.

 

 

- 스택은 수식계산, 수식괄호검사, 워드프로세서의 undo/redo, 웹브라우저의 뒤로 앞으로의 기능 구현을 활용한다.

 

- 큐는 최근 사용문서, 인쇄작업 대기목록, 버퍼의 기능 구현을 활용한다.

 

 

 

 

2. Stack을 이해하기 위한 예제(1)

: Stack을 활용하여 웹 브라우저의 '앞으로', '뒤로'의 기능을 구현하는 예제이다.

 

 

 

 

 

3. Queue을 이해하기 위한 예제(1)

: LinkedList를 이용하여 Unix의 history 명령어 구현하는 예제이다.

 

( 여기서 중요하게 봐야할 것은 LinkedList tmp = (LinkedList) q 와 ListIterator it = tmp.listIterator() 문장이다. )

 

 

 

 

4. PriorityQueue

- Queue 인터페이스의 구현체 중의 하나로, 저장한 순서에 관계없이 우선순위가 높은 것부터 꺼내게 된다는 특징이다.

 

- null은 저장될 수 없으며, 저장할 시 NullPointerException이 발생하게 된다.

 

- 저장공간으로는 배열을 사용하며, heap의 형태로 저장한다.

( 힙은 이진 트리의 한 종류로 가장 큰 값이나 가장 작은 값을 빠르게 찾을 수 있다는 특징이 있다. )

 

 

 

- 아래의 코드를 보고 이해하자.

 

( 내부 배열은 힙 형태로 저장되어 있어서 12534로 출력된다. )

 

( 31524 순서로 저장하였지만 poll() 꺼내서 보니 출력 값은 12534로 출력된다. 이것은 우선 순위가

작은 숫자를 높은 우선순위로 두었기 때문이다. )

 

( 위의 숫자들은 이미 Integer와 같은 Number 자손들은 자체적으로 숫자 비교하는 방법이 정의되어

있기 때문에 따로 구현할 필요 없다. )

 

( 또한 객체도 저장할 수 있는 우선순위는 프로그래머가 직접 비교할 수 있는 방법을 넣어서 구현할 수 있다. )

 

 

 

 

5. Deque

- Queue의 변형으로, 한 쪽 끝으로만 추가/삭제할 수 있는 큐와 달리 Deque는 양쪽 끝에 추가/삭제할 수 있다.

 

- 덱은 스택과 큐를 합쳐놓은 것과 같으며 스택 또는 큐로도 사용할 수 있다.

(1) offerLast()

: Stack -> push()

: Queue -> offer()

 

 

(2) pollLast()

: Stack -> pop()

 

 

(3) pollFirst()

: Queue -> poll()

 

 

(4) peekFirst()

: Queue -> peek()

 

 

(5) peekLast()

: Stack -> peek()