자바 튜토리얼 12 - 3 | Stack and Queue | 컬렉션 프레임워크 | 자바 자료형

스택과 큐 자료형을 알아본다.

 

스택은 접시를 쌓을 때 사용하는 방법이다. 접시를 밑에서 부터 위로 쌓는다. 꺼낼때는 위에서 부터 꺼낸다. 이것이 스택의 기본이다. First In Last Out / Last in First Out 제일 먼저 들어간 사람이 마지막에 나온다는 개념이 스택이다. 메모리 중에 스택 메모리가 있다. 스택 메모리도 함수를 호출할 때 접시 처럼 쌓는 구조를 가진다.

 

한편 큐의 경우 먼저 들어간 쪽을 먼저 꺼낸다. 스택이 세로로 쌓았다면 큐는 회전하는 것이라 생각할 수 있다. First In First Out / Last In Last Out먼저 들어간 자료가 먼저 나온다. 끓임없이 뒤에 추가되고 계속해서 앞에서 부터 가져온다. 식당에서 표를 받아서 기다리는 것이 대표적인 큐 구조이다. 번호표가 빠른 사람에게 먼저 제공한다. 그 번호는 어디까지고 계속된다.

 

식당에서 스택형으로 음식을 제공한다면 문제가 된다. 새로운 사람들이 오는 경우 먼저 온 사람은 계속 기다리게 된다. 먼저 온 사람들에게 우선권이 있어야 한다. 그것이 큐이다. 자료를 계속 순환시켜야 하는 경우 큐가 필요하다. 몇명이 올지 정해지지 않은 경우도 큐를 사용하는 것이 유리하다. 뒤에 숫자를 계속 추가해야 하니까. 뒷쪽이 무한이 열려있는 공간이다. 큐가 대박집을 설명하는데 적당하다. 이론 상으로 손님을 무한히 받을 수 있다. (재료나 시간상 한계가 없다면)

 

반면 스택은 예약제 레스토랑이다. 오늘 점심에 오는 손님의 숫자가 100명이면 메인디쉬에 나가는 접시는 딱 100개가 있으면 된다. 맨 밑에 있는 마지막 한개의 접시까지 사용하게 된다. 큐에 대한 이점은 확실하다. 접시를 100개만 가지고 있으면 된다. 즉 공간과 자원활용이 좋다. 어떤날은 1000명이 오고 어떤날은 100명이 오는 큐 형태의 식당은 어쨋든 1000개의 접시가 필요하다. 접시 뿐 아니라 테이블과 식기, 직원도 더 많이 필요하다. 즉 100명이 오늘 날에는 900명에게 음식을 제공하기 위한 자원이 낭비가 된다. 스택은 접시가 100개만 필요하니까 좁은 공간에도 식당을 운영할 수가 있다. 가성비가 좋기 때문에 수익률이 좋을 것이다.

 

자료구조를 배우면 이런 이유로 현재까지도 프로그램이 구동할 때 스택메모리를 사용하고 있다. 더 자세히는 컴파일러가 지역 변수들을 스택메모리에 배치한다.

 

*자료 구조를 이해했다면 직접 코드를 작성하여 스택과 큐 구조를 만들수가 있을 것이다. 그러나 수레바퀴를 다시 만들 필요는 없다. 자바의 컬렉션 프레임워크에 이미 구현되어 있다. 각종 필요한 메서드들이 구현되어 있으므로 편리하게 사용할 수 있다. 게다가 오랫동안 사용되서 안정적인 성능을 보여준다.

 

* 다음 예제는 스택과 큐이다. 스택은 클래스가 정의되서 사용가능하지만 큐의 경우 인터페이스로 제공되기 때문에 다른 자료형(여기서는 링크드 리스트)으로 사용하면 된다.

package com.kay;

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

public class Test01 {
    public static void main(String[] args) {

        Stack stack1 = new Stack();
        Queue queue1 = new LinkedList();

        int rnumber = 0;

        System.out.println(stack1.empty());

        for (int i = 0; i < 10; i++) {
            rnumber = (int)(Math.random()*100);
            stack1.push(rnumber);
        }
       for (int i = 0; i < 10; i++) {
            rnumber = (int)(Math.random()*100);
           queue1.offer(rnumber);
        }

        System.out.println(stack1);

        for (int i = 0; i < 3; i++) {
            System.out.print(stack1.pop()+" ");
        }
        System.out.println();

        System.out.println(queue1);
        for (int i = 0; i < 3; i++) {
            System.out.print(queue1.poll()+" ");
        }
    }
}

1에서 100까지 랜덤하게 숫자를 뽑은 후 스택과 큐에 10개를 집어넣었다. 스택의 pop 메서드와 큐의 poll 메서드는 각각 뒤쪽과 앞쪽에서 순서대로 자료를 가져온다.

 

자료를 가져오는 것은 곧 꺼내오는 것을 뜻한다. 꺼낸 후에 남아있는 자료들을 보면 스택은 앞부분이 큐는 뒷부분이 남아있다.

 

이러한 구조 때문에 스택과 큐를 함께 설명하는 것이다.

 

자바에서는 컬렉션 프레임워크에서 이런 유용한 클래스를 지원하니까 사용법을 잘 알고 사용하면 된다. 스택과 큐는 메서드가 몇개 되지 않으니까 쉽게 정리할 수 있을 것이다.

 

 

docs.oracle.com/javase/7/docs/api/java/util/Stack.html

Stack (Java Platform SE 7 )

docs.oracle.com/javase/7/docs/api/java/util/Queue.html

Queue (Java Platform SE 7 )

큐는 인터페이스기 때문에 직접 생성은 불가하나 큐 인터페이스를 구현한 클래스를 사용하면 된다. 각자 클래스에 따라 약간씩 내용이 다를 수 있지만 거의 기능은 같다.

 

큐의 API 에 들어가보면 구현된 클래스의 리스트를 볼 수 있다.

 

 

* 다음은 스택활용 예제이다. 문자열에 루프하면서 특정 문자를 찾을 때 마다 스택에 기록한다.

package com.kay;

import java.util.EmptyStackException;
import java.util.Stack;

public class Test01 {
    public static void main(String[] args) {

        Stack stack = new Stack();

        String Hello[] = { "Hello (World!)", "WE HAVE MET BEFORE"};

        String expression = Hello[0];

        System.out.println("Hello[0] : "+  Hello[0]);
        System.out.println("Hello : "+  Hello);
        System.out.println("expression : "+  expression);
        try{
            for (int i = 0; i < expression.length(); i++) {
                char ch = expression.charAt(i);
                if (ch == '(') {
                    stack.push(ch + "");
                } else if (ch == ')') {
                    stack.pop();
                }
            }
            if (stack.isEmpty()){
                System.out.println("괄호가 일치합니다");
            } else{
                System.out.println("괄호가 일치하지 않습니다");
            }
        } catch (EmptyStackException e){
                System.out.println("괄호가 일치하지 않습니다");
        }

        System.out.println(expression);
    }
}