[자료구조] Stack, Queue, Deque

우선, 글을 작성하기 전 이 글의 모든 내용은 김영한님의 JAVA 강의를 바탕으로 함을 알립니다.

💡Stack, Queue, Deque

이번 포스팅에서는 대표적인 선형 자료구조인 Stack, Queue 그리고 Deque에 대해서 알아보자

Stack

• 후입 선출(LIFO, Last In First Out)의 자료구조
• 즉, 나중에 넣은 것이 가장 먼저 나오는 것을 후입선출 자료구조라고 한다

◻️ 주의!

JAVA에서 제공하는 Stack은 사용하지 않는 것을 지향한다. Stack 클래스 내부에서 Vector라는 자료 구조를 사용하는데, 이 자료구조는 지금은 사용되지 않고 하위 호환을 위해 존재한다. 대신에 Deque를 사용하는 것을 권장한다

◻️ Stack 활용 예제

public class StackMain {

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

        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.println(stack);

        // 다음 꺼낼 요소 확인(꺼내지 않고 단순 조회)
        System.out.println("stack.peek() = " + stack.peek());

        // 스택 요소 뽑기
        // LIFO 후입 선출
        System.out.println("stack.pop() = " + stack.pop());
        System.out.println("stack.pop() = " + stack.pop());
        System.out.println("stack.pop() = " + stack.pop());
        System.out.println(stack);
    }
}

Queue

• 선입 선출(FIFO, Fist In Fist Out)의 자료구조

• Queue에 값을 넣는 것을 offer, 값을 꺼내는 것을 poll이라고 한다

◻️ 컬렉션의 Queue

• java의 Collection은 Queue인터페이스를 구현체로 제공한다.

◻️ Queue 활용 예제

public class QueueMain {

    public static void main(String[] args) {
        Queue<Object> queue = new ArrayDeque<>();
//        Queue<Object> linkedlist = new LinkedList<>();

        //데이터 추가
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        System.out.println(queue);

        //다음 꺼낼 데이터 확인(꺼내지 않고 단순 조회만)
        System.out.println("queue.peek() = " + queue.peek());

        // 데이터 꺼내기
        System.out.println("queue.poll() = " + queue.poll());
        System.out.println("queue.poll() = " + queue.poll());
        System.out.println("queue.poll() = " + queue.poll());
        System.out.println(queue);
    }
}

Deque

Deque는 Double Ended Queue의 약자로, 자료구조의 끝 양쪽에서 데이터를 추가하거나 삭제할 수 있는 자료구조이다. 컬렉션에서는 Queue인터페이스의 구현체로 제공된다

• offerFirst() : 앞에 추가한다.
• offerLast() : 뒤에 추가한다.
• pollFirst() : 앞에서 꺼낸다.
• pollLast() : 뒤에서 꺼낸다.

◻️ Deque 활용 예제

public class DequeMain {

    public static void main(String[] args) {
        Deque<Integer> deque = new ArrayDeque<>();
//        Deque<Integer> deque = new LinkedList<>(); 더 느림

        // 데이터 추가
        deque.offerFirst(1);
        System.out.println(deque);
        deque.offerFirst(2);
        System.out.println(deque);
        deque.offerFirst(3);
        System.out.println(deque);
        deque.offerFirst(4);
        System.out.println(deque);

        // 다음 꺼낼 데이터 확인(단순 조회)
        System.out.println("deque.peekFirst() = " + deque.peekFirst());
        System.out.println("deque.peekLast() = " + deque.peekLast());

        // 데이터 꺼내기
        System.out.println("deque.pollFirst() = " + deque.pollFirst());
        System.out.println("deque.pollFirst() = " + deque.pollFirst());
        System.out.println("deque.pollLast() = " + deque.pollLast());
        System.out.println("deque.pollLast() = " + deque.pollLast());
        System.out.println(deque);
    }
}

◻️ Deque와 Stack, Queue

Deque는 요소를 저장하는 처음과 끝 즉, 양쪽에서의 데이터 추가와 삭제가 가능하다. 이러한 Deque의 성질로 인해 Deque를 통해 Queue와 Stack을 모두 구현할 수 있다. java의 Deque 인터페이스는 이러한 Deque의 성질을 반영해 Stack의 데이터 입력(push()), 데이터 삭제(pop()) 그리고 Queue의 데이터 입력(offer()), 데이터 삭제(poll())을 제공한다.

// Deque-Stack
import java.util.ArrayDeque;
import java.util.Deque;

/**
 *  Deque 자료구조를 stack으로 사용할 수 있음 이때 단순히 Deque의 offer와 poll이 아닌
 *  stack의 push pop을 그대로 사용할 수 있음
 */
public class DequeStackMain {

    public static void main(String[] args) {
        Deque<Object> deque = new ArrayDeque<>();

        // 데이터 추가
        deque.push(1);
        deque.push(2);
        deque.push(3);
        System.out.println(deque);

        // 다음 꺼낼 데이터 확인(꺼내지 않고 단순 조회만)
        System.out.println("deque.peek() = " + deque.peek());

        // 데이터 꺼내기
        System.out.println("deque.pop() = " + deque.pop());
        System.out.println("deque.pop() = " + deque.pop());
        System.out.println("deque.pop() = " + deque.pop());
        System.out.println(deque);
    }
}