[자바/java] 스택(Stack) 과 큐(Queue)

자바에서 제공하는 Stack과 Queue에 대해 알아보기 이전에 스택(Stack)과 큐(Queue)의 기본 개념과 특징을 먼전 설명하겠습니다.

 

스택은 마지막에 저장한 데이터를 가장 먼저 꺼내게 되는 LIFO(Last In First Out)구조로 되어 있고, 큐는 처음에 저장한 데이터를 가장 먼저 꺼내게 되는 FIFO(First In First Out)구조로 되어 있다.

 

쉽게 얘기하자면 스택은 동전통과 같은 구조로 양 옆과 바닥이 막혀 있어서 한 방향으로만 뺄 수 있는 구조이고, 큐는 양 옆만 막혀 있고 위아래로 뚫려 있어서 한 방향으로는 넣고 한 방향으로는 빼는 파이프와 같은 구조로 되어 있다.

 

 

 

스택 실생활 예제 ( 프링글스 )

 

 

 

큐 실생활 예제 ( 파이프 )

 

 

 

그렇다면 스택과 큐를 구현하기 위해서는 어떤 컬렉션 클래스를 사용하는 것이 좋을까요?

 

순차적으로 데이터를 추가하고 삭제하는 스택에는 ArrayList 와 같은 배열기반의 컬렉션 클래스가 적합하지만, 큐는 데이터를 꺼낼 때 항상 첫 번째 저장된 데이터를 삭제하므로 ArrayList와 같은 배열기반의 컬렉션 클래스를 사용한다면 데이터를 꺼낼 때마다 빈 공간을 채우기 위해 데이터의 복사가 발생하므로 비효율적이다.

그래서 큐는 ArrayList보다 데이터의 추가/삭제가 쉬운 LinkedList로 구현하는 것이 더 적합하다.

 

 

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class StackQueueExample {

    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<Integer>();
        Queue<Integer> queue = new LinkedList<Integer>();

        stack.push(0);
        stack.push(1);
        stack.push(2);

        queue.offer(0);
        queue.offer(1);
        queue.offer(2);

        System.out.println("= Stack =");
        while(!stack.empty()) {
            System.out.println(stack.pop());
        }

        System.out.println("= Queue =");
        while(!queue.isEmpty()) {
            System.out.println(queue.poll());
        }

    }
}

 

 

 

 

 

 

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

큐는 먼저 넣은 것이 먼저 꺼내지는 구조(FIFO) 이기 때문에 같은 순서이고, 스택은 먼저 넣은 것이 나중에 꺼내지는 구조(LIFO)이기 때문에 넣을 때의 순서와 반대로 꺼내진 것을 알 수 있다.

 

자바에서는 스택을 Stack클래스로 구현하여 제공하지만 큐는 Queue 인터페이스로만 정의해 놓았을 뿐 별도의 클래스를 제공하고 있지 않다. 대신 Queue 인터페이스를 구현할 클래스들이 있어서 이 들 중의 하나를 선택해서 사용하면 된다.

 

 

스택은 활용 예로 웹브라우저(크롬, 익스플로러, 파이어폭스) 의 뒤로가기나 앞으로 가기가 스택으로 볼수 있습니다.

 

 

웹브라우저의 뒤로/앞으로

 

 

 

큐의 활용 예제로 방문 기록이 있습니다.

 

 

 

최근 방문 기록

 

 

 

스택과 큐는 실제 프로그래밍에서 빈번하게 사용되는 자료구조라고는 하지만 어디에 사용되었고 막상 어떻게 활용해야할지를 생각해보면 잘 떠오르지 않을 것이다.

 

 

스택을 이용한 웹브라우저 앞으로, 뒤로 버튼의 기능을 만들어보면 다음과 같다.

 

import java.util.Stack;

public class StackExample {

    public static Stack back = new Stack();
    public static Stack forward = new Stack();


    public static void main(String[] args) {

        EnterURL("1. 네이버");
        EnterURL("2. 다음");
        EnterURL("3. 카카오");
        EnterURL("4. 구글");

        ShowStatus();

        ClickBack();
        System.out.println("뒤로가기 버튼 누른 후");
        ShowStatus();

        ClickBack();
        System.out.println("뒤로가기 버튼 누른 후");
        ShowStatus();

        ClickForward();
        System.out.println("앞으로 버튼을 누른 후");
        ShowStatus();

        EnterURL("5. 줌");
        System.out.println("다른 사이트 들어가기");
        ShowStatus();

    }

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

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

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

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

 

 

 

 

 

 

 

 

큐로 리눅스나 유닉스 같은 os에 명령어를 Queue로 이용해서 구현하면 다음과 같다.

 

 

import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Queue;
import java.util.Scanner;

public class QueueExample {

    public static Queue queue = new LinkedList();
    public static final int MAX_SIZE = 5;

    public static void main(String[] args) {

        System.out.println("리눅스 명령어를 입력해주세요");

        while(true) {

            System.out.println(">>");

            try {

                Scanner sc = new Scanner(System.in);
                String input = sc.nextLine().trim();

                if("".equals(input)) continue;

                if(input.equalsIgnoreCase("q")) {
                    System.exit(0);
                } else if(input.equalsIgnoreCase("history")) {
                    int i = 0;

                    save(input);

                    LinkedList result = (LinkedList) queue;
                    ListIterator it = result.listIterator();

                    while(it.hasNext()) {
                        System.out.println(++i + ". " + it.next());
                    }
                } else {
                    save(input);
                }
            } catch (Exception e) {
                System.out.println("입력 오류입니다.");
            }
        }
    }

    public static void save(String input) {

        if(!"".equals(input)) {
            queue.offer(input);
        }

        if(((LinkedList)queue).size() > MAX_SIZE) {
            queue.remove();
        }
    }

}