최근 자바를 활용한 알고리즘 공부를 하며 스택과 큐를 자주 접하게 되었다.
그러다보니 여러 알고리즘 패턴에 사용되는 자료구조에 대해 공부해야할 필요성을 느꼈다.

이번에는 그중 스택과 큐에 대해서 알아보려 한다.

Stack(스택)이란?

Stack(스택)
데이터를 일시적으로 저장하기 위한 자료구조이며, 가장 나중에 넣은 데이터를 가장 먼저 꺼내는 후입선출(LIFO) 구조를 지닌다.

Stack 특징

• java.util 패키지에서 Stack 클래스를 제공한다.
• 마지막에 추가된 데이터가 가장 먼저 나오는 특성을 가진다.
• 데이터를 추가하는 동작을 push, 빼내는 동작을 pop이라고 한다.

Stack 메서드

메서드	설명
empty()	Stack이 비어있는지 알려줌 비어있으면 true, 아니라면 false를 반환
peek()	Stack의 맨 위에 저장된 객체를 반환 Stack에서 객체를 꺼내지는 않음, Stack이 비었다면 null을 반환
pop()	Stack의 맨 위에 저장된 객체를 꺼냄
push()	Stack에 지정한 객체를 저장
search()	Stack에서 주어진 객체를 찾아 위치를 반환 (배열과 다르게 0이 아닌 1부터 시작)

Stack 사용법

Stack은 클래스로 구현하여 제공되기에 아래와 같이 클래스로서 선언이 가능하다.

Stack st = new Stack(); // 사용 가능

간단하게 Stack에 데이터를 넣고 꺼내보는 코드를 작성해보자.

import java.util.*;

class Study {
    public static void main(String[] args) {
       Stack st = new Stack<>();
       
       st.push("item-0");
       st.push("item-1");
       st.push("item-2");
       
       System.out.println("top: " + st.peek());
       
       while(!st.empty()) {
            System.out.println(st.pop());        
       }
    }
}

코드를 보면 item-0부터 item-1, item-2 순서로 스택에 집어넣었고,
맨 위에 저장된 객체를 출력하고 반복문을 돌며 스택이 비어있지 않다면 맨 위 객체를 꺼내도록 하였다.

먼저 peek()를 통해 맨위에 저장된 item-2을, 그리고 pop()을 통해 꺼낸 객체들을 출력했다.
LIFO 구조이기에 제일 나중에 넣은 item-2에서 item-0 순으로 출력이 된다.

top: item-2
item-2
item-1
item-0

Stack 활용처

• 재귀 알고리즘
• 웹 브라우저 방문기록 (뒤로가기)
• 실행 취소 (undo)
• 역순 문자열 만들기
• 수식의 괄호 검사
• 후위 표기법 계산

Queue(큐)란?

Queue(큐)
데이터를 일시적으로 저장하기 위한 자료구조이며, 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO) 구조를 지닌다.

Queue 특징

• 큐에 데이터를 집어넣는 동작을 enqueue, 꺼내는 동작을 dequeue라고 한다.
  enqueue 연산은 항상 데이터를 큐의 맨 뒤에만 추가하고 dequeue 연산은 큐의 맨 앞에에 있는 데이터만 추출한다.
• 별도의 클래스로 구현되지 않고 인터페이스로만 정의되어 있다.

Queue 메서드

메서드	설명
add()	지정된 객체를 Queue에 추가 성공하면 true 반환, 저장공간이 부족하면 IllegalStateException 발생
remove()	Queue에서 객체를 꺼내 반환 Queue가 비어있다면 NoSuchElementException 발생
element()	삭제없이 저장된 요소를 읽어옴 Queue가 비어있다면 NoSuchElementException 발생
offer()	Queue에 지정한 객체를 저장 성공하면 true, 실패하면 false 반환
poll()	Queue에서 객체를 꺼내 반환 Queue가 비어있다면 null 반환
peek()	삭제없이 요소를 읽어옴 Queue가 비어있다면 null 반환

Queue 사용법

Stack은 클래스로 구현하여 제공되지만, Queue는 인터페이스만 정의되어 있어 별도의 클래스로 제공되지 않기에 아래와 같이 클래스로 사용할 수 없다.

Queue qu = new Queue(); // 사용 불가

큐는 인터페이스이기에 직접 구현하거나 큐를 활용해 구현한 클래스를 사용해야 한다.
이미 구현된 클래스들을 사용해보기 위해 Java API 공식문서에서 큐를 직접 구현한 클래스를 찾아보았다.

많은 Queue의 구현클래스 중 LinkedList가 배열로 구현한 Queue보다 쉽기 때문에 가장 대중적으로 쓰인다고 한다.

LinkedList로 구현한 Queue를 활용해 데이터 삽입,삭제 코드를 작성해보자.

import java.util.*;

class Study {
    public static void main(String[] args) {
       Queue qu = new LinkedList<>();

       qu.offer("item-0");
       qu.offer("item-1");
       qu.offer("item-2");

       System.out.println("top: " + qu.peek());
       
       while(!qu.isEmpty()) {
            System.out.println(qu.poll());
       }
    }
}

코드를 보면 Stack과 동일하게 item-0부터 item-1, item-2 순서로 삽입하였고 반복문을 돌며 데이터를 꺼내도록 하였다.

peek()를 통해 제일 먼저 저장된 item-0을, 그리고 poll()을 통해 꺼낸 객체들을 출력했다.
FIFO 구조이기에 가장 먼저 넣은 item-0부터 item-2 순으로 출력됨을 알 수 있었다.

top: item-0
item-0
item-1
item-2

왜 LinkedList인가?

ArrayList는 '조회'할 때 LinkedList는 '삽입/삭제'할 때 좋은 성능을 발휘한다.

ArrayList는 단순 조회시 속도는 빠르지만, 삽입/삭제 시에는 배열의 크기를 고려해야 하기에 느리다. 반면에 LinkedList는 노드간 연결된 List이기에 삽입/삭제시 빠른 속도를 보여주지만, 내부 원소를 조회할 때는 각 노드들에 일일히 접근하기에 느리다.

Queue의 구조는 선입선출(FIFO)이기 때문에 맨 처음에는 삽입, 맨 뒤에서는 삭제가 발생한다. 이를 통해 중간에서 삽입, 삭제되는 경우가 없어 조회보단 삽입/삭제에 초점을 두고 접근해야함을 알 수 있다.

그러므로 ArrayList보다는 삽입/삭제를 다루기에 적절한 LinkedList로 구현하는 것이 적절하다.

Queue 활용처

• 너비 우선 탐색(BFS) 구현
• 캐시(Cache) 구현
• 우선순위가 같은 작업 예약(인쇄 대기열)
• 선입선출이 필요한 대기열(티켓 카운터)
• 콜센터 고객 대기시간
• 프린터의 출력 처리
• 윈도 시스템의 메시지 처리기
• 프로세스 관리

Stack 활용 예제

Stack을 활용하여 예제를 만들어보려 한다.
수식 내에서 괄호의 짝을 맞출 경우와 웹 브라우저에서 undo/redo 기능을 예제로 작성해보자.

수식의 괄호 갯수 검증

수식에서 괄호의 짝을 맞출 때 Stack을 활용하여 쉽게 풀 수 있다.

import java.util.*;

class Study {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        
        Stack st = new Stack<>();
        
        try {
            for(int i=0; i<str.length(); i++) {
                if(str.charAt(i) == '(') st.push(str.charAt(i));
                else if(str.charAt(i) == ')') st.pop();
            }
            if(st.isEmpty()) System.out.println("괄호 짝이 맞습니다.");
            else System.out.println("괄호 짝이 맞지 않습니다.");
        } catch(EmptyStackException e) {
            System.out.println("괄호 짝이 맞지 않습니다.(EmptyStackException)");
        }
        
    }
}

위 코드를 정리하면 아래와 같다.

1. 주어진 수식(문자열)에서 여는 괄호 '(' 가 있다면 '('를 Stack에 저장한다.
2. 닫는 괄호 ')'가 있다면 Stack 맨 위 데이터를 꺼낸다.
3. Stack이 비어있다면 괄호 짝이 맞으므로 "괄호 짝이 맞습니다."를 출력한다.
4. Stack이 비어있지 않다면 괄호 짝이 맞지 않기에 "괄호 짝이 맞지 않습니다."를 출력한다.
5. Stack이 비어있는데 pop()으로 꺼내려하면 EmptyStackException 예외가 발생하기 때문에 예외 발생시 "괄호 짝이 맞지 않습니다.(EmptyStackException)"를 출력한다.

// str = "(2+3)+(3*2)/2"
괄호 짝이 맞습니다.

// str = "((2+3))/2
괄호 짝이 맞지 않습니다.

// str = "(2+3)))/2"
괄호 짝이 맞지 않습니다.(EmptyStackException)

작성한 코드 내용대로 위와 같은 출력을 확인할 수 있다.

뒤로가기/앞으로가기 기능(undo/redo)

import java.util.*;

class Study {
    private static String now = "";
    private static Stack<String> back = new Stack<>();
    private static Stack<String> forward = new Stack<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        String site = sc.nextLine(); //naver
        go(site); 
        history();
        
        site = sc.nextLine(); // google
        go(site); 
        history();  
        
        site = sc.nextLine(); // daum
        go(site); 
        history();  

        System.out.println("\n---> 뒤로가기");
        undo();
        history();

        System.out.println("\n---> 앞으로가기");
        redo();
        history();

        site = sc.nextLine(); // kakao
        go(site); 
        history(); 
    }
    
    public static void go(String site) {
        System.out.println("다음 사이트로 접속합니다. " + site);
        if(!"".equals(now) && now != null) back.push(now);
        now = site;
    }

    public static void undo() { // 뒤로가기
        if(!back.isEmpty()) {
            forward.push(now);
            now = back.pop();
        }
    }

    public static void redo() { // 앞으로가기
        if(!forward.isEmpty()) {
            back.push(now);
            now = forward.pop();
        }
    }

    public static void history() {
        System.out.println("back : " + back);
        System.out.println("now : " + now);
        System.out.println("forward : " + forward);
    }
}

위 코드도 한 번 뜯어보자.

go(접속사이트) : 브라우저 접속 함수
함수가 실행될 때 최초 접속이라면 now(현재사이트)에 site(접속사이트)를 저장한다. 이미 사이트에 접속중이라면 추가로 back Stack에 now를 저장한다.

undo() : 뒤로가기 함수
2개 이상의 사이트에 접속했다면(back Stack이 비어있지 않다면) foward Stack에 now를 저장하고, now에 back Stack의 이전 접속사이트(맨 위 데이터)를 꺼내온다.

redo() : 앞으로가기 함수
1번 이상 뒤로가기가 실행되었다면(forward Stack이 비어있지 않다면) back Stack에 now를 저장하고, now에 forward Stack의 이전 접속사이트(맨 위 데이터)를 꺼내온다.

main 메서드에서 실행되는 함수들을 순서대로 보면 아래와 같은 순서로 호출되고 있다. 그에 따른 출력을 확인하면 아래와 같다.

1. go("naver")
2. go("google")
3. go("daum")
4. undo()
5. redo()
6. go("kakao")

// naver 접속
다음 사이트로 접속합니다. naver
back : []
now : naver
forward : []

// google 접속
다음 사이트로 접속합니다. google
back : [naver]
now : google
forward : []

// daum 접속
다음 사이트로 접속합니다. daum
back : [naver, google]
now : daum
forward : []

// daum -> google
---> 뒤로가기
back : [naver]
now : google
forward : [daum]

// google -> daum
---> 앞으로가기
back : [naver, google]
now : daum
forward : []

// kakao 접속
다음 사이트로 접속합니다. kakao
back : [naver, google, daum]
now : kakao
forward : []

Queue 활용 예제

Stack에 이어 Queue를 활용하여 최근 접속한 사이트를 5개 목록으로 유지하는 기능을 예제로 작성해보자.

최근문서 기능

import java.util.*;

class Study {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Queue q = new LinkedList<>();
        int max_size = 5;

        while(true) {
            String str = sc.nextLine();
            
            q.offer(str);
            if(q.size() > max_size) q.poll();
            
            LinkedList list = (LinkedList)q;
            int size = list.size();
            for(int i=0; i<size; i++) {
                System.out.println(i+1 + ". " + list.get(i));
            }
        }    
    }    
}

위 코드를 정리한 내용은 아래와 같다.

1. 무한 반복문을 돌며 접속할 사이트(문자열)을 입력받는다.
2. 접속 사이트를 Queue에 저장한다.
3. 5개 이상의 사이트를 접속하면(크기가 5보다 커짐) Queue에서 데이터를 추출한다.
4. Queue를 LinkedList로 변환한 후 모든 원소를 출력한다.

큐의 크기가 5개 이상이 되면 poll()을 통해 맨 처음 데이터부터 꺼내짐을 확인할 수 있었다.

// naver 접속
1. naver

// google 접속
1. naver
2. google

// daum 접속
1. naver
2. google
3. daum

// kakao 접속
1. naver
2. google
3. daum
4. kakao

// yahoo 접속
1. naver
2. google
3. daum
4. kakao
5. yahoo

// okky 접속
1. google
2. daum
3. kakao
4. yahoo
5. okky

// wanted 접속
1. daum
2. kakao
3. yahoo
4. okky
5. wanted

final..

Stack은 클래스로 정의되어 있으니 단순하게 사용하면 되지만 Queue의 경우 왜 LinkedList를 일반적으로 사용하는지 궁금했었고, 삽입과 삭제의 비중을 두기 위해 사용함을 알게되었다.

다만, 왜 Stack과 Queue를 써야하는지, 더 나은 방법은 없는지 더 알아보고 공부해야 할 것 같다.

특히 Stack과 Queue를 합쳐놓은 Deque라는 녀석이 있음을 알게되었고, Deque까지 공부하고 함께 작성하려 했으나, 글이 글어지기도 하고 본 목적이었던 Stack과 Queue에 대해서 제대로 알고 넘어가자라는 생각이 들어 줄이게 되었다.

Deque에 대해서도 찾아 공부하고 기록할 예정이다.

참고문서
https://docs.oracle.com/javase/8/docs/api/java/util/Queue.html
https://devlog-wjdrbs96.tistory.com/246
http://javaqueue2010.blogspot.com/
https://chucoding.tistory.com/52
https://hbase.tistory.com/120?category=929719
https://deftkang.tistory.com/218
https://pridiot.tistory.com/68
https://velog.io/@roro/Java-Stack-Queue