(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()