Stack과 Queue

Stack과 Queue

 

Stack

- LIFO 구조 (Last in First Out) : 마지막에 저장된 것을 제일 먼저 꺼내는 것

- 아래가 막힌 상자의 모양으로, 순차적으로 데이터가 쌓이고, 맨 위부터 데이터를 추출하게 된다.

- 배열 구현에 효율적이다.

- Stack은 클래스가 존재하기 때문에, Stack s = new Stack();을 사용해 객체 생성이 가능하다.

 

Stack의 메서드

메서드	설명
boolean empty()	Stack이 비어있는지 알려준다.
Object peek()	Stack의 맨 위에 저장된 객체를 반환, pop()과 달리 Stack에서 객체를 꺼내지는 않는다.  비었을 때는 EmptyStackException이 발생한다.
Object pop()	Stack의 맨 위에 저장된 객체를 꺼낸다. 비었을 때는 EmptyStackException이 발생한다.
Object push(Object item)	Stack에 객체(item)를 저장한다.
int search(Object o)	Stack에서 주어진 객체(o)를 찾아서 그 위치를 반환하며, 못 찾으면 -1을 반환한다. 배열과 달리 index는 0이 아닌 1부터 시작하며, 맨 위의 요소가 1이다.

 

 

Queue

- FIFO 구조 (First in First out) : 제일 먼저 저장한 것을 제일 먼저 꺼내게 된다.

- 위 아래가 뚫려 있어 한 방향으로는 넣고 한 방향으로는 빼는 파이프 구조로 되어 있다.

- 링크드 리스트 구현에 효율적이다.

- Queue는 인터페이스기 때문에, 직접 구현하거나 구현한 클래스를 사용해야 한다.

 

Queue의 메서드

메서드	설명
boolean add(Object o)	지정된 객체를 Queue에 추가한다. 성공하면 true를 반환한다. 저장공간이 부족하면 illegalStateException이 발생한다.
Object remove()	Queue에서 객체를 꺼내 반환한다. 비어있으면 NoSuchElementException이 발생한다.
Object element()	삭제없이 요소를 읽어온다. Queue가 비었을 때 NoSuchElementException이 발생한다.
boolean offer(Object o)	Queue에 객체를 저장한다. 성공하면 true, 실패하면 false를 반환한다.
Object poll()	Queue에서 객체를 꺼내서 반환한다. 비어있으면 null을 반환한다.
Object peek()	삭제없이 요소를 읽어온다. Queue가 비어있으면 null을 반환한다.

 

 

스택과 큐의 활용

스택의 활용 예   -   수식계산, 수식괄호검사, 워드프로세서의 undo/redo,
                               웹브라우저의 뒤로/앞으로
큐의 활용 예       -   최근사용문서, 인쇄작업 대기목록, 버퍼(buffer)