Java 자료구조 - Stack, Queue, Deque 정리

Stack

스택은 마지막에 저장한 데이터를 가장 먼저 꺼내게 되는 구조 특징이 있는데, 이러한 자료의 구조를 LIFO(Last In First Out) 구조라고 말한다. 

또한, 전 게시글에서 봤듯이 자바의 Stack 클래스는 Vector 클래스Visit Website를 상속(extends)받기에 Thread-Safe 하다는 특징을 가지고 있다.

Method	설명
boolean empty()	Stack이 비어있는지 알려준다.
Object peek()	Stack의 맨 위에 저장된 객체를 반환 pop과 달리 Stack에서 객체를 꺼내지는 않는다. 비어있을 경우 EmptyStackException 발생
Object pop()	Stack의 맨 위에 저장된 객체를 꺼낸다. 비어있을 경우 EmptyStackException발생
Object push(Object item)	Stack에 객체(item)을 저장한다.
int search(Object o)	Stack에서 주어진 객체(o)를 찾아서 그 위치를 반환 못 찾을 경우 -1을 반환 배열과 달리 위치는 0이 아닌 1부터 시작

 

Stack클래스는 deprecated되었고 Deque 를 사용하는 것이 바람직하다.

자바의 스택 클래스는 쓰기를 지양하여야 한다. 왜냐하면 Vector 컬렉션을 상속을 받아 구현되었기 때문인데, 이 Vector 클래스 자체가 컬렉션 프레임워크라는 개념이 나오기도 전에 자바 버전1 서부터 있었던 굉장히 오래된 클래스이기 때문에 여러모로 취약점이 많고, 또한 상속으로 인한 부모 메서드 공유 문제 때문에 사용자가 잘못되게 사용될 수 있다는 큰 문제점이 있기 때문이다.

예를 들어 Stack의 대표적인 동작은 push, pop 이지만, 상속한 Vector 클래스의 add 메소드 또한 외부로 노출되게 된다. 그러면서 아래와 같이 개발자가 add 메소드도 스택 클래스에서 사용할수 있는 메소드인줄 알고 사용했다가, 의도치 않은 동작이 실행되면서 오류를 범하게 된다.

Stack<String> stack = new Stack<>();
stack.push("one");
stack.push("two");
stack.push("three");

stack.add(0, "four"); // add 메소드를 호출함으로써 stack의 의미와는 다르게 특정 인덱스의 값이 추가

// 마지막에 넣은 요소는 "four" 인데 스택은 "three"로 뽑혀진다
String str = stack.pop(); // three
System.out.println(str.equals("four")); // false

-> 따라서 자바 공식 문서에 보면 애초부터 상속을 잘못하여 잘못 설계된 Stack 클래스보다 Deque 클래스를 사용하여 구현할 것을 권장하고 있다!!

 

Queue

큐는 처음에 저장한 데이터를 가장 먼저 꺼내게 되는 구조 특징이 있는데, 이를 FIFO(First-In-First-Out) 구조라고 한다.

	비어있을 경우 예외 발생	비어있을 경우 값 리턴
추가(enqueue)	boolean add(Object o) 실패 시 IllegalStateException 발생	boolean offer(Object o) 실패 시 false 리턴
삭제(dequeue)	Object remove() 실패 시 NoSuchElementException 발생	Object poll() 실패 시 null 리턴
검사(peek)	Object element()  실패 시 NoSuchElementException 발생	Object peek()  실패 시 null 리턴

 

Queue 종류

PriorityQueue

일반적인 큐와는 조금 다르게, 원소에 우선 순위(priority)를 부여하여 우선 순위가 높은 순으로 정렬되고 꺼낸다. 따라서, 우선순위 큐에 저장할 객체는 필수적으로 Comparable , Comparator 인터페이스를 구현해야한다. compareTo() 메서드 로직에 따라 자료 객체의 우선순위를 결정하는 식으로 동작되기 때문이다.  저장공간으로 배열을 사용하며, 각 요소를 힙(heap) 형태로 저장한다. null 저장은 불가능하다.

// 우선순위 큐에 저장할 객체는 필수적으로 Comparable를 구현
class Student implements Comparable<Student> {
    String name; // 학생 이름
    int priority; // 우선순위 값

    public Student(String name, int priority) {
        this.name = name;
        this.priority = priority;
    }

    @Override
    public int compareTo(Student user) {
        // 오름차순 정렬
        return this.priority-user.priority;
    }

    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", priority=" + priority +
                '}';
    }
}

public static void main(String[] args) {

    // 오름차순 우선순위 큐
    Queue<Student> priorityQueue = new PriorityQueue<>();

    priorityQueue.add(new Student("주몽", 5));
    priorityQueue.add(new Student("세종", 9));
    priorityQueue.add(new Student("홍길동", 1));
    priorityQueue.add(new Student("임꺽정", 2));

    // 우선순위 대로 정렬되어 있음
    System.out.println(priorityQueue);
    // [Student{name='홍길동', priority=1}, Student{name='임꺽정', priority=2}, Student{name='주몽', priority=5}, Student{name='세종', priority=9}]

    // 우선순위가 가장 높은 값을 참조
    System.out.println(priorityQueue.peek()); // Student{name='홍길동', priority=1}

    // 차례대로 꺼내기
    System.out.println(priorityQueue.poll()); // Student{name='홍길동', priority=1}
    System.out.println(priorityQueue.poll()); // Student{name='임꺽정', priority=2}
    System.out.println(priorityQueue.poll()); // Student{name='주몽', priority=5}
    System.out.println(priorityQueue.poll()); // Student{name='세종', priority=9}
}

 

Comparable 대신 Comparator을 사용할수도 있다.

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

class Student implements Comparator<Student> {
    String name; // 학생 이름
    int priority; // 우선순위 값

    public Student() {
        // 기본 생성자
    }

    public Student(String name, int priority) {
        this.name = name;
        this.priority = priority;
    }

    @Override
    public int compare(Student s1, Student s2) {
        // 오름차순 정렬
        return s1.priority - s2.priority;
    }

    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", priority=" + priority +
                '}';
    }
}

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

        // Student 클래스의 Comparator 구현을 사용하여 우선순위 큐 생성
        Queue<Student> priorityQueue = new PriorityQueue<>(new Student());

        priorityQueue.add(new Student("주몽", 5));
        priorityQueue.add(new Student("세종", 9));
        priorityQueue.add(new Student("홍길동", 1));
        priorityQueue.add(new Student("임꺽정", 2));

        // 우선순위 대로 정렬되어 있음
        System.out.println(priorityQueue);
        // [Student{name='홍길동', priority=1}, Student{name='임꺽정', priority=2}, Student{name='주몽', priority=5}, Student{name='세종', priority=9}]

        // 우선순위가 가장 높은 값을 참조
        System.out.println(priorityQueue.peek()); // Student{name='홍길동', priority=1}

        // 차례대로 꺼내기
        System.out.println(priorityQueue.poll()); // Student{name='홍길동', priority=1}
        System.out.println(priorityQueue.poll()); // Student{name='임꺽정', priority=2}
        System.out.println(priorityQueue.poll()); // Student{name='주몽', priority=5}
        System.out.println(priorityQueue.poll()); // Student{name='세종', priority=9}
    }
}

 

Deque 

Deque(Double-Ended Queue)는 양쪽으로 넣고 빼는 것이 가능한 큐를 말한다. 스택과 큐를 하나로 합쳐놓은 것과 같으며 스택으로 사용할 수도 있고, 큐로 사용할 수도 있다. Deque의 조상은 Queue이며, 구현체로 ArrayDequ와 LinkedList 등이 있다.

 

!! ArrayDeque !!

스택으로 사용할 때 Stack 클래스보다 빠르며, 대기열로 사용할 때는 LinkedList보다 빠르다. 

하지만 스레드에 안전하지 않으므로 멀티스레드 환경에서는 문제가 발생할 수 있다.

Stack 클래스의 단점을 보완한 ArrayDeque

Stack 클래스의 단점 3가지
- 모든 메소드에 synchronized가 있기 때문에 단일 스레스 환경에서는 성능이 떨어진다.
- Vector 클래스를 상속받았기 때문에 LIFO 구조를 유지하는 것이 아니라 중간에서 데이터를 삭제하고 삽입하는 것이 가능
- Stack 클래스를 만들 때 초기 용량을 설정할 수 없다.

-> 이러한 단점을 보완하기 위해서 LIFO 구조를 만들 때 ArrayDeque를 사용하는 것이 바람직하다.

Deque	Queue	Stack
offerLast()	offer()	push()
pollLast()	-	pop()
pollFirst()	poll()	-
peekFirst()	peek()	-
peekLast()	-	peek()

 

addFirst, addLast (삽입), removeFirst, removeLast (삭제), getFirst, getLast(조회)는 실패 시 예외를 발생시키고, offerFirst, offerLast(삽입), pollFirst, pollLast(삭제),peekFirst, peekLast(조회)는 값을 반환한다.

First Element (Head)		Last Element (Tail)
	Throws exception	Special value	Throws exception	Special value
Insert	addFirst(e)	offerFirst(e)	addLast(e)	offerLast(e)
Remove	removeFirst()	pollFirst()	removeLast()	pollLast()
Examine	getFirst()	peekFirst()	getLast()	peekLast()

 

LinkedList

LinkedList는 List 인터페이스와 Queue 인터페이스를 동시에 상속받고 있기 때문에, 스택 / 큐 로서도 응용이 가능하다. 실제로 LinkedList 클래스에 큐 동작과 관련된 메서드를 지원한다. (push, pop, poll, peek, offer ..등)

add​(int index, E element) , remove​(int index) 메서드가 있어 LinkedList는 리스트 내 어느 위치에서나 요소의 삽입 및 삭제가 가능하다.

 

ArrayDeque vs LinkedList

중간에 요소를 삽입, 삭제해야 하는 경우가 있으면 LinkedList를 사용하고 그 외에는 ArrayDeque를 사용한다.

ArrayDeque는 큐의 앞과 뒤에서 빠르게 요소를 추가하고 삭제하는 경우 linkedlist보다 성능이 좋다. 하지만 중간에 요소를 삽입하거나 삭제하는 메소드 제공하지 않는다.
반면에, LinkedList는 ArrayDeque보다 속도는 느리지만 add(int index, E element), remove(int index) 메서드가 있어 중간에 요소를 삽입, 삭제할 수 있다.