05. [자바] Stack, Queue 그리고 Deque - 자료구조

다른 컬렉션이나 자료구조에 대해 더 알아보고 싶다면 아래의 링크로 들어오시라🤗

01. [자바] 컬렉션 프레임워크(Collections Framework)

 

스택(Stack)과 큐(Queue)

스택(Stack) : 마지막에 저장한 데이터를 가장 먼저 꺼내는 LIFO구조 (Last In First Out)
큐(Queue) : 처음에 저장한 데이터를 가장 먼저 꺼내게 되는 구조 (First In First Out)

 

예를 들어 스택(Stack)에 0, 1, 2를 순서대로 넣었다면 2, 1, 0 순서로 추출되게 되고 

반대로 큐(Queue)에 0, 1, 2를 순서대로 넣었다면 0, 1, 2 순서로 추출되게 된다.

 

스택과 큐를 구현하기 위해서는

스택(Stack)은 순차적으로 데이터를 추가하고 삭제하기 때문에 배열 기반인 ArrayList와 같은 컬렉션 클래스가 적합하고

큐(Queue)는 데이터를 꺼낼 때 항상 첫 번재 저장된 데이터를 삭제하기 때문에 배열기반의 컬렉션보다

데이터의추가 삭제가 쉬운 LinkendList가 적합하다.

스택(Stack)은 ArrayList로 구현하는게 좋음
큐(Queue)는 LinkedList로 구현하는게 좋음

실제로 자바에서 Queue는 Interface이고 구현체는 LinkedList이다

Stack은 ArrayList의 구버전이라고 할수 있는 Vector클래스를 상속 받아 만들어져 있다.

 

Deque(Double-Ended Queue)

Queue의 변형으로, Deque(덱, 또는 디큐라고 읽음)가 생겨났다.

Deque(덱, 디큐)은 양쪽 끝에 추가/삭제가 가능하며 Deque의 조상은 Queue이다

구현체로는 ArrayDeque와 LinkedList 등이 있다.

 

 

 

스택과 큐의 활용

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

 

Stack st = new Stack();
Queue q = new LinkedList(); // Queue인터페이스의 구현체 LinkedList사용

st.push("0");
st.push("1");
st.push("2");

q.offer("0");
q.offer("1");
q.offer("2");

while(!st.empty()){
	System.out.println(st.pop());
}

while(!q.isEmpty()){
	System.out.println(q.poll());
}

2
1
0
0
1
2

 

 

Stack의 메소드

메소드	설명
boolean empty()	Stack이 비어있는지 알려준다
Object peek()	Stack의 맨 위에 저장된 객체를 반환, pop()과 달리 객체를 반환 후 삭제하지 않음 (비어있을 때는 EmptyStackException발생)
Object pop()	Stack의 맨 위에 저장된 객체를 반환하고 삭제 (비어있을 때는 EmptyStackException발생)
Object push(Object obj)	Stack에 객체(Obj)를 저장한다.
int search(Object obj)	Stack에서 주어진 객체(obj)를 찾아서 그 위치를 반환한다, 못찾으면 -1을 반환 (배열과 달리 위치는 0이 아닌 1에서 시작)

 

 

Queue의 메소드

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