Stack vs Queue

Stack

개요

• 마지막에 저장한 데이터를 가장 먼저 꺼내게 되는 LIFO(Last In First Out) 구조
• 순차적으로 데이터를 추가하고 삭제하는 스택에는 ArrayList와 같은 배열 기반의 컬렉션 클래스가 적합
• ex. 수식계산, 수식괄호검사, undo/redo, 웹 브라우저의 뒤로/앞으로

 

구현

import java.util.*;

class MyStack extends Vector {
	public Object push(Object item){
    	addElement(item);
        return item;
    }
	public Object pop(){
    	Object obj = peek(); //만일 Stack이 비었다면 peek 메서드가 예외 발생
        removeElementAt(size() - 1); //마지막 요소를 삭제
        return obj;
    }
    public Object peek(){
    	int len = size();
        if(len == 0) 
        	throw new EmptyStackException();
        return elementAt(len - 1);
   	}
    public int search(Object o){
    	int i = lastIndexOf(o); //찾는 값의 저장된 위치(배열의 인덱스)를 반환
        if(i >= 0){
        	return size() - i; //맨 위(뒤)에 저장된 객체의 인덱스를 1로 정의하기 때문에 계산
        }
        return -1;
    }
}

 

Queue

개요

• 처음에 저장한 데이터를 가장 먼저 꺼내게 되는 FIFO(First In First Out) 구조
• 데이터를 꺼낼 때 항상 첫번째 데이터를 삭제하므로 ArrayList와 같은 배열 기반의 컬렉션 클래스를 사용한다면 데이터를 꺼낼 때마다 빈 공간을 채우기 위해 데이터의 복사가 발생하므로 비효율적
• ArrayList보다 데이터의 추가/삭제가 쉬운 LinkedList로 구현하는 것이 더 적합
• ex. 최근사용문서, 인쇄 작업 대기목록, 버퍼 등

 

PriorityQueue

• 저장된 순서에 관계없이 우선순위가 높은 것부터 꺼내게 된다는 특징(null은 저장할 수 없음)
• 저장공간으로 배열을 사용하며, 각 요소를 '힙'이라는 자료구조의 형태로 저장

 

Deque(Double-Ended Queue)

• 한쪽 끝으로만 추가/삭제할 수 있는 큐와는 달리, 양쪽 끝에서 추가/삭제가 가능
• 구현체로는 ArrayDeque와 LinkedList 등이 있음