Java 자료구조, 컬렉션 프레임웍 - 2, 스택과 큐

Stack과 Queue

 

스택    : 마지막에 저장한 데이터를 가장 먼저 꺼낸다

> 0, 1, 2 순서로 넣었으면 꺼낼 때는 2, 1, 0으로 꺼냄

 

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

큐      : 처음 저장한 데이터를 가장 먼저 꺼낸다

> 0, 1, 2 순서로 넣었으면 꺼낼 때는 0, 1, 2로 꺼냄

활용    : 최근 사용 문서, 인쇄작업 대기목록, 버퍼(buffer)

 

순차적으로 데이터를 추가하고 삭제하는 스택에는 ArrayList,
큐는 ArrayList를 사용하면 첫번째를 꺼낼 때마다 빈공간을 채우기 위해 복사가 발생하므로 비효율적, LinkedList 사용

    

priorityQueue

Queue 인터페이스의 구현체 중 하나
저장한 순서에 관계 없이 우선순위(priority)가 높은 것부터 꺼낸다.
null은 저장할 수 없다.
저장공간으로 배열을 사용한다.
각 요소를 이진 트리의 한 종류로, 가장 큰 값이나 가장 작은 값을 빠르게 찾을 수 있다는 특징을 가진 '힙(heap)'이라는 자료구조의 형태로 저장
        
참고            자료구조의 힙과 JVM의 힙은 이름만 같고 다른 것이다.

    
    

Deque(Double-Ended Queue)

        Queue의 변형으로 한쪽 끝으로만 추가/삭제할 수 있는 Queue와 달리,
        양쪽 끝에 추가/삭제가 가능하다.
        Deque의 조상은 Queue, 구현체로는 ArrayDeque과 LinkedList가 있다

 

 

위 정보를 통해 아래에 예시를 만들어봤다.

웹브라우저 뒤로/앞으로 예시       

import java.util.*;

public class StackEx1 {
    public static Stack back = new Stack();
    public static Stack forward = new Stack();

    public static void main(String args[]){
        goURL("1.네이트");
        goURL("2.야후");
        goURL("3.네이버");
        goURL("4.다음");

        printStatus();

        goBack();
        sysout("='뒤로' 버튼 누른 후 =");
        printStatus();

        goBack();
        sysout("='뒤로' 버튼 누른 후 =");
        printStatus();

        goForward();
        sysout("='앞으로' 버튼 누른 후 =");
        printStatus();

        goURL("codechobo.com");
        sysout("= 새로운 주소로 이동 후");
        printStatus();
    }

    public static void printStatus(){
        sysout("back:"+back);
        sysout("forward:"+forward);
        sysout("현재 화면은 '" + back.peek() + "'입니다.);
                sysout();
    }

    public static void goURL(String url){
        back.push(url);
        if(!forward.empty())
            forward.clear();
    }

    public static void goForward(){
        if(!forward.empty())
            forward.push(forward.pop());
    }

    public static void goBack(){
        if(!back.empty())
            back.push(back.pop());
    }
}

실행 결과
       

back: [1.네이트, 2.야후, 3.네이버, 4.다음]
forward: []
현재화면 '4.다음' 입니다.

= '뒤로' 버튼을 누른 후 =
back: [1.네이트, 2.야후, 3.네이버]
forward: [4.다음]
현재화면 '3.네이버' 입니다.

= '뒤로' 버튼을 누른 후 =
back: [1.네이트, 2.야후]
forward: [3.네이버, 4.다음]
현재화면 '2.야후' 입니다.

= '앞으로' 버튼을 누른 후 =
back: [1.네이트, 2.야후, 3.네이버]
forward: [4.다음]
현재화면 '3.네이버' 입니다.

= 새로운 주소로 이동 후 =
back: [1.네이트, 2.야후, 3.네이버, codechobo.com]
forward: []
현재화면 'codechobo.com' 입니다.