Stack / Queue

Stack

• LIFO(Last In First Out, 후입선출) 구조로 마지막에 저장(push)된 것을 가장 먼저 추출(pop)
• 순차적으로 추가하고 삭제하기 때문에 ArrayList로 구현하는 것이 좋음
• 단방향 입출력
• 데이터는 하나씩만 넣고 빼는 것이 가능

Stack 참조변수명 = new Stack();

장점

• 스택에 저장된 데이터를 가져오는 속도가 매우 빠름
• 자바에서 기본적으로 스택 클래스를 제공

단점

• 크기의 제한이 없으므로 불필요한 메모리 사용량 증가가 발생할 수 있음
• Vector 클래스를 상속 받아 구현되어 크기를 동적으로 조정하지 않음
• 자바에서의 스택 클래스는 다른 언어의 스택과는 다르게 Vector 클래스를 상속 받아 중간에서 데이터를 삽입 및 삭제가능

Stack의 메소드

empty()

Stack이 비어있는지 알려줌

peek()

Stack의 맨 위에 저장된 객체를 꺼내지 않고 반환

Stack이 비었을 경우에는 예외 발생

pop()

Stack의 맨 위에 저장된 객체를 꺼냄

Stack이 비었을 경우에는 예외 발생

push()

Stack에 객체를 저장

search()

Stack에서 주어진 객체를 찾아 그 위치를 반환하고, 못찾으면 -1을 반환

배열과는 다르게 위치는 0이 아닌 1부터 시작

get()

특정 인덱스의 요소를 찾음

set()

특정 인덱스에 요소를 넣음

remove()

특정 인덱스의 요소를 제거

Stack의 활용

수식계산, 수식괄호검사, 워드프로세서의 되돌리기/다시실행, 웹브라우저의 전후 페이지 이동

Queue

FIFO(First In First Out) 구조로 가장 먼저 저장(offer)한 것을 가장 먼저 추출(poll)

요소를 바로바로 삭제할 수 있는 Linked List를 통해 구현하는 것이 유리함

// Queue는 클래스가 아니라 인터페이스로 정의되어 있기 때문에
// 생성자를 사용할 수 없음

// 1. 큐를 직접 구현
// 2. 혹은 큐를 구현한 클래스를 사용 (LinkedList)
Queue q = new LinkedList();
q.offer("0");

Queue의 메소드

add()

지정된 객체를 Queue에 추가하고, 성공하면 true를 반환

저장공간 부족시 예외 발생

remove()

Queue에서 객체를 꺼내 반환하고 비어 있으면 예외 발생

element()

삭제없이 요소를 읽어 오지만, peek과 다르게 Queue가 비었을 때 예외 발생

offer()

객체를 저장하고, 성공하면 true, 실패하면 false 반환

poll()

Queue에서 객체를 꺼내서 반환하고, 비어있으면 null을 반환하고 예외는 발생하지 않음

peek()

삭제없이 요소를 읽어 오지만, element와는 다르게 Queue가 비어있어도 예외가 발생하지 않고 null을 반환

Queue의 활용

최근에 사용한 문서, 인쇄작업 대기목록, 버퍼