[CS] 자바의 정석 독서 #20 - 스택과 큐 in Java

앞으로 스택과 큐에 대해서 다뤄볼 건데,

스택과 큐는 '특정 조건을 만족하기만하면 스택 또는 큐이다.'라는 것이다.

 

큐의 구현체로는 LinkedList가 있는데, LinkedList는 큐의 '가장 처음 저장한 데이터를 가장 먼저 꺼낸다.'라는 조건을 충족하기 때문에 큐의 구현체가 되는 것이지 LinkedList가 인덱싱을 통해 중간에 저장된 값에 도달할 수 있다는 조건은 중요하지 않다. 단지 특정 메서드를 사용하면 가장 처음 저장한 데이터를 꺼낸다는 것이 중요하다. 이건 스택도 마찬가지

 

스택

스택은 LIIFO (Last In First Out) 구조로 이루어진 자료구조다. 즉, 마지막에 저장한 데이터를 가장 먼저 꺼내게된다. 프링글스 통 같이 가장 마지막에 넣은 프링글스부터 먹는 것처럼 생긴 자료구조다.

 

그래서 스택은 마지막에 저장한 것부터 보고싶을때, 예를들면 인터넷 검색기록 같은 부분에서 활용할 수 있다.

 

자바에서 스택을 사용할 때의 메서드는

public E push(E item)		//스택에 객체를 저장한다.

//스택에서 가장 마지막 객체를 반환하고 해당 객체를 스택에서 제거
//스택이 비었다면 에러가 발생한다.
public synchronized E pop()	

//스택에서 가장 마지막 객체를 반환
//pop()처럼 제거하지는 않는다.
//스택이 비었다면 에러가 발생한다.
public synchronized E peek()

//스택이 비었는지 확인한다.
public boolean empty()

//스택에서 객체의 위치를 반환
//스택의 가장 앞쪽 요소의 인덱스는 1이다.
public synchronized int search(Object o)

이정도로 되어있다.

스택은 Vector 클래스를 하위클래스로 되어있어 상속받은 메서드를 자주 이용하는 편이다.

스택은 컬렉션의 등장 이전부터 자바에 존재했기 때문에 Vector 클래스를 상속 중이다.

Stack s =  new Stack();
s.push(1);
s.push(2);
s.push(3);

System.out.println("스택");
while (!s.empty()) {
    System.out.println(s.pop());
}

이렇게 스택에 요소를 넣으면 넣은 순서의 반대로 출력되는 것을 알 수 있다.

 

class MyStack{
    private Object[] elements = new Object[100];
    int size = 0;

    public boolean empty() {
        return elements == null || elements.length == 0;
    }

    public Object peek() {
        return elements[size];
    }

    public Object pop() {
        Object obj = elements[size-1];
        size -= 1;
        return obj;
    }

    public void push(Object e) {
        if (size == elements.length) {
            elements = Arrays.copyOf(elements, elements.length * 2);
        }

        elements[size] = e;
        size++;
    }

    public int search(Object e) {
        for (int idx = 0; idx < size; idx++) {
            if (elements[idx].equals(e)) {
                return idx;
            }
        }
        return -1;
    }


}

사실 Stack는 '구현'만 두고보면 어려운 편이 아니기 때문에 종종 Vector를 상속하지 않고도 연습삼아 Stack을 구현하는 경우가 있다. 나도 해봤는데 나름 그래도 돌아가는듯?

 

큐

큐는 FIFO (First In First Out) 구조로 이루어진 자료구조다. 즉, 처음에 저장한 데이터를 가장 먼저 꺼내게된다. 위아래에 뚫린 프링글스 통 같이 위로는 프링글스를 넣고 아래로 프링글스를 하나씩 빼먹는 것처럼 가장 처음에 넣은 프링글스부터 먹는 것처럼 생긴 자료구조다.

 

그래서 큐는 처음 저장한 데이터부터 보고싶을 때, 대기열 등에 사용된다.

나중에 배우지만 DB풀, 스레드풀 같이 작업을 묶어놓는 경우에는 묶인지 오래된 작업부터 실행되어야하므로 이때도 작업큐를 사용해 오래된 작업부터, 그러니까 큐에 먼저 들어온 작업부터 실행한다. 물론 현재 배우는 큐와 작업큐는 용도니 실행방법이니 상당히 다르지만 기본 개념은 큐

 

//지정된 객체를 큐에 추가
//저장공간이 부족하면 에러가 발생한다.
boolean add(E e)

//큐에 객체를 저장하고 성공/실패여부 반환
boolean offer(E e)

//큐에서 객체를 꺼내서 반환. 큐가 비었으면 에러
E remove();

//큐에서 객체를 꺼내서 반환, 큐가 비었으면 null
E poll();

//큐에서 객체를 읽어오는데 객체를 삭제하지 않음
//큐가 비었으면 에러
//실패 시 false
E element();

//삭제없이 요소를 읽어옴
//큐가 비어있으면 null
E peek();

큐는 스택과 달리 컬렉션을 곧바로 상속 중이기 때문에 컬렉션의 메서드와 함께 큐의 메서드도 포함되어있는 형태다.

 

LinkedList l = new LinkedList();

l.add(1);
l.add(2);
l.add(3);

System.out.println("큐");
while (!l.isEmpty()) {
    System.out.println(l.pop());
}

이렇게 큐를 사용하면 넣은 순서대로 객체를 꺼낸다는 것을 알 수 있다.

LinkedList는 Queue 인터페이스의 구현체다.

---

PriorityQueue

큐의 구현체 중의 하나로, 큐는 pop() 메서드를 사용하면 저장된 순서대로 값을 반환하지만 PriorityQueue는 우선순위가 높은 것부터 반환하게된다. null을 추가하면 NPE가 발생하므로 추가할 수 없다.

 

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Queue<Integer> q = new PriorityQueue<>();
        q.add(3);
        q.add(7);
        q.add(1);
        q.add(2);
        q.add(4);

        while (!q.isEmpty()) {
            System.out.println(q.poll());
        }
    }
}

큐에 3, 7, 1, 2, 4 순서대로 요소를 추가했으나

 

poll()로 출력해보니 정렬된 순서인 1, 2, 3, 4, 7 순서대로 출력되는 것을 볼 수 있다.

 

PriorityQueue는 내부적으로 배열을 사용하며, 힙의 형태로 자료를 저장한다. (JVM 메모리 영역의 힙이 아닌 자료구조의 이름이다.)

힙은 이진트리의 한 종류로 가장 큰 값이나 가장 작은 값을 빠르게 찾을 수 있다. 힙정렬을 통해서 가능하다.

 

Queue<Integer> q = new PriorityQueue<>();
        q.add(3);
        q.add(7);
        q.add(1);
        q.add(2);
        q.add(4);

        System.out.println(q);

막상 q를 출력해보면 저장한 순서도 아니고, 우선순위순서도 아닌 이상한 순서로 값이 출력되는데, 힙 자료구조로 값이 저장되기 때문에 그렇다.

---

Deque (Double-Ended Queue) (읽는 것은 덱 또는 디큐)

Double-Ended Queue 라는 이름에서 볼 수 있듯이, 큐가 한 쪽에서만 저장, 다른 쪽에서만 추출이 가능한 것과 달리 덱은 양쪽에서 모두 저장과 추출이 가능하다.

 

자바에서 LinkedList는 큐의 구현체이지만 양쪽에서 모두 값을 추가하거나 추출할 수 있다. 그래서 덱의 구현체로는 ArrayDeque, LinkedList 등들이 있다. 물론 덱은 큐의 하위클래스이다.

 

덱은 큐를 상속하기 때문에 offer()와 poll(), peek() 메서드를 지원하는데, 덱에서는 앞/뒤 개념이 추가로 필요하기 때문에

offer(), offerLast(), offerFirst()

poll(), pollLast(), pollFirtst() 등의 메서드도 지원한다.

---

이렇게 스택과 큐를 알아봤다.

스택은 가장 마지막에 저장한 데이터를 가장 먼저 추출하는 자료구조의 형태,

큐는 가장 처음에 저장한 데이터를 가장 먼저 추출하는 자료구조의 형태다.

 

사실 이게 핵심의 전부고 나머지는 약간 곁다리 느낌이긴하다

암튼 이렇게 끝