[Java] 컬렉션 프레임윅 (Stack과 Queue)

스택

: LIFO - 마지막에 저장한 데이터를 가장 먼저 꺼내게 되는 구조

 

큐

: FIFO - 처음에 저장한 데이터를 가장 먼저 꺼내게 되는 구조

 

 

☆ Stack의 메서드

메서드	설명
boolean empty()	Stack이 비어있는지 알려준다.
Object peek()	Stack의 맨 위에 저장된 객체를 반환. pop()과 달리 Stack에서 객체를 꺼내지는 않음
Object pop()	Stack의 맨 위에 저장된 객체를 꺼낸다.
Object push(Object item)	Stack에 객체(item)를 저장한다.
int search(Object o)	Stack에서 주어진 객체(o)를 찾아서 그 위치를 반환. 못찾으면 -1을 반환

 

☆ Queue의 메서드

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

 

import java.util.*;

class StackQueueEx {
	public static void main(String[] args) {
        Stack st = new Stack();
        Queue q = new LinkedList();  // 스택을 Stack클래스로 구현하여 제공하지만 큐는 별도 클래스 X
        
        st.push("0");
        st.push("1");
        st.push("2");
        
        q.offer("0");
        q.offer("1");
        q.offer("2");
        
        System.out.println("=Stack=");
        While(!st.empty()) {
        	System.out.println(st.pop());
        }
        
        System.out.println("=Queue=");
        while(!q.isEmpty()) {
        	System.out.println(q.poll());
        }
    }
}


/*
=Stack=
2
1
0
=Queue=
0
1
2
*/

 

 

스택과 큐의 활용

 

스택의 예 : 수식계산, 수식괄호검사, 웹브라우저의 뒤로/앞으로, 워드프로세서의 undo/redo

큐의 예 : 최근사용문서, 인쇄작업 대기목록, 버퍼

 

 

PriorityQueue

 

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

: null은 저장 불가

: '힙(heap)'이라는 자료구조의 형태로 저장

※ JVM의 힙과 이름만 같을 뿐 다른 것.

 

★ 정수일 경우, 숫자가 작을수록 우선순위가 높다.

★ 객체도 저장가능하지만, 그럴경우 객체의 크기를 비교할 수 있는 방법을 제공해야 함.

 

 

Deque(Double-Ended Queue)

 

: Queue의 변형으로, 한 쪽 끝으로만 추가/삭제할 수 있는 Queue와 달리 양쪽 끝에 추가/삭제 가능

: Deque의 조상은 Queue이며, 구현체로는 ArrayDeque, LinkedList 등이 있음.

 

▶ 덱은 스택과 큐를 하나로 합쳐놓은 것과 같으며 스택으로도, 큐로도 사용할 수 있음.

 

 

★ 덱의 메서드에 대응하는 큐와 스택의 메서드

Deque	Queue	Stack
offerLast()	offer()	push()
pollLast()	-	pop()
pollFirst()	poll()	-
peekFirst()	peek()
peekLast()	-	peek()