[기본 개념] 6 | (1.4) Stack, Queue

[기본 개념] 6 | (1.4) Stack, Queue

1 컬렉션 프레임웍의 핵심 인터페이스

2 ArrayList

3 LinkedList

4> Stack과 Queue

5 Iterator, Listlterator, Enumeration

6 Arrays

7 Comparator와 Comparable

8 HashSet

9 TreeSet

10 HashMap과 Hashtable

11 TreeMap

12 Properties

13 Collections

14 컬렉션 클래스 정리 & 요약

4. Stack과 Queue

 스택(stack)과 큐(queue)에 대해 먼저 알아보자. 스택은 마지막에 저장한 데이터를 가장 먼저 꺼내는 구조이고, 큐는 처음에 저장한 데이터를 가장먼저 꺼내는 구조이다.

 

 스택에는 순차적으로 데이터를 추가하고 삭제하는 ArrayList와 같은 배열 기반의 컬렉션 클래스가 적합하지만 큐는 데이터의 추가, 삭제가 쉬운 LinkedList로 구현하는 것이 적합하다.

 

예제/StackQueueEx.java

import java.util.*;

public class StackQueueEx {
    public static void main(String[] args) {
        Stack st = new Stack();
        Queue q = new LinkedList();

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

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

        System.out.println("=== Stack ===");
        while (!st.isEmpty()) {
            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

 

스택과 큐에 각각 "0", "1", "2"를 같은 순서로 넣고 꺼냈을 때의 결과가 다른 것을 알 수 있다.

 

 스택을 Stack클래스로 구현해서 제공하고 있지만 큐는 queue인터페이스로만 정의해놓았기 때문에 Queue인터페이스를 구현한 클래스 중에서 하나를 선택해 사용하면 된다.

 

스택과 큐의 활용

스택의 활용 예 - 수식계산, 수식괄호검사, 웹브라우저의 뒤로/앞으로 등

큐의 활용 예 - 최근사용문서, 인쇄 작업 대기목록, 버퍼(buffer) 등

 

예제/StackEx1.java

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("5.다음");

        printStatus();

        goBack();
        System.out.println("=== '뒤로' 버튼을 누른 후 ===");
        printStatus();

        goBack();
        System.out.println("=== '뒤로' 버튼을 누른 후 ===");
        printStatus();

        goForward();
        System.out.println("=== '앞으로' 버튼을 누른 후 ===");
        printStatus();

        goURL("hello.com");
        System.out.println("=== 새로운 주소로 이동 후 ===");
        printStatus();
    }

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

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

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

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

실행결과

back : [1.네이트, 2.구글, 3.네이버, 5.다음]
forward : []
현재화면은 '5.다음' 입니다.

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

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

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

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

 

스택으로 웹브라우저의 '뒤로', '앞으로' 버튼의 기능을 구현한 것이다.

 

예제/QueueEx1.java

import java.util.*;

public class QueueEx1 {
    static Queue q = new LinkedList();
    static final int MAX_SIZE = 5;      // 최대 5개까지만 저장되도록 한다.

    public static void main(String[] args) {
        System.out.println("help를 입력하시면 도움말을 볼 수 있습니다.");
        
        while (true) {
            System.out.println(">>");
            try {
                Scanner s = new Scanner(System.in);
                String input = s.nextLine().trim();
                
                if ("".equals(input)) continue;
                
                if (input.equalsIgnoreCase("q")) {
                    System.exit(0);
                } else if (input.equalsIgnoreCase("help")) {
                    System.out.println(" help - 도움말을 보여줍니다.");
                    System.out.println(" q 또는 Q - 프로그램을 종료합니다.");
                    System.out.println(" history - 최근에 입력한 명령어 " 
                    + MAX_SIZE + "개를 보여줍니다.");
                } else if (input.equalsIgnoreCase("history")) {
                    int i = 0;
                    save(input);
                    
                    // LinkedList의 내용을 보여준다.
                    LinkedList tmp = (LinkedList)q;
                    ListIterator it = tmp.listIterator();
                    
                    while (it.hasNext()) System.out.println(++i + "." + it.next());
                } else {
                    save(input);
                    System.out.println(input);
                }
            } catch (Exception e) {
                System.out.println("입력 오류입니다.");
            }
        }
    }
    
    public static void save(String input) {
        if (!"".equals(input)) q.offer(input);
        
        // queue의 최대크기를 넘으면 제일 처음 입력된 것을 삭제
        if (q.size() > MAX_SIZE) q.remove();
    }
}

실행결과

help를 입력하시면 도움말을 볼 수 있습니다.
>>
HELP
 help - 도움말을 보여줍니다.
 q 또는 Q - 프로그램을 종료합니다.
 history - 최근에 입력한 명령어 5개를 보여줍니다.
>>
HI
HI
>>
dkd
dkd
>>
mff
mff
>>
HistorY
1.HI
2.dkd
3.mff
4.HistorY
>>
Q

 

최근 5개의 명령어만을 보여주는 기능이다.

 

PriorityQueue

 Queue인터페이스의 구현체 중 하나로, 저장한 순서에 관계없이 우선순위(priority)가 높은 것부터 꺼내게 된다.  이때 우선순위는 숫자가 작을수록 높다.

 

PriorityQueue는 저장공간을 배열로 사용하며, 각 요소를 '힙(heap)'이라는 자료구조의 형태로 저장한다.

 

Deque(Double-Ended Queue)

 Queue의 변형으로, 한쪽 끝으로만 추가 / 삭제할 수 있는 Queue와는 달리, Deque(덱, 또는 디큐)은 양쪽 끝에서 추가 / 삭제를 할 수 있다. Deque의 조상은 Queue이다.

 

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

 

 

 

 

 

출처 | Java의 정석 (남궁 성)