[DS] 스택 vs 큐 차이 + 자바 구현 예시(with 배열, ArrayList)

알고리즘 공부 전에 자료구조부터 차근차근 공부해 보기로 했다. 검색해보니 가장 먼저 나오는 단어가 스택, 큐고 둘의 특징을 비교할 수 있을 것 같아 따로 정리하려고 한다.

 

먼저 스택이란 뭘까? 네이버 사전과 지식백과에서 말하는 스택의 정의는 각각 아래와 같다.

네이버 사전) 동적이고 순차적인 자료의 목록. 시스템의 기억 장치에 설치하며 한쪽 끝에서만 저장과 제거를 할 수 있는 특성이 있다. 서브프로그램의 호출과 복귀를 처리할 때 이용한다

지식백과) 스택(stack)은 모든 원소들의 삽입(insert)과 삭제(delete)가 리스트의 한쪽 끝에서만 수행되는 제한 조건을 가지는 선형 자료 구조(linear data structure)로서, 삽입과 삭제가 일어나는 리스트의 끝을 top이라 하고, 다른 한쪽 끝을 bottom이라 한다. 스택은 종종 pushdown stack이라고도 하는데, 스택의 top에 새로운 원소를 삽입하는 것을 push라 하고, 가장 최근에 삽입된 원소를 의미하는 스택의 top으로부터 한 원소를 제거하는 것을 pop이라 한다. 이와 같은 스택 연상은 항상 스택의 top에서 발생하므로 top 포인터의 값을 1씩 증가 또는 감소시킴으로써 수행된다.

 

자료들이 순차적으로 쌓인 목록 같은 것인데 자료의 추가, 삭제는 목록의 한쪽 끝에서만 발생하는 자료구조라고 한다.

젠가 같은 블록 형태의 장난감들을 하나씩 원래 들어있던 박스에 집어넣은 다음 역순으로 하나씩 빼는 그림이 생각난다. 위키백과에서 말하는 스택의 정의는 아래와 같다.

 

https://ko.wikipedia.org/wiki/%EC%8A%A4%ED%83%9D

스택 - 위키백과, 우리 모두의 백과사전

스택은 제한적으로 접근할 수 있는 나열 구조다. 이 접근법은 언제나 목록의 끝에서만 일어난다. 끝먼저내기 목록(Pushdown list)이라고도 한다. 스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO - Last In First Out)으로 되어 있다. 자료를 넣는 것을 '밀어넣는다' 해서 푸쉬(push)라고 하고, 반대로 넣어둔 자료를 꺼내는 것을 팝(pop)이라고 하는데, 이때 꺼내지는 자료는 가장 최근에 푸쉬한 자료부터 나오게 된다. 이처럼 나중에 넣은 값이 먼저 나오는 것을 LIFO 구조라고 한다.

 

쉽게 말해서 가장 마지막에 넣은 게 가장 먼저 나오는 형태의 자료구조란 뜻이다. 선입선출, 후입선출 중에서 후입선출이란 의미다.

 

다음으로 네이버 지식백과에서 큐를 설명하는 내용이다. 네이버 사전에선 그럴싸한 보이지 않아 생략한다.

 

큐는 리스트의 한 쪽 끝에선 자료가 삽입되고 다른 한 쪽에서는 삭제되는 구조를 말한다. 쉽게 말해서 가장 먼저 보관한 자료부터 먼저 꺼내는 구조다. 자료의 삽입이 일어나는 곳을 rear(뒤쪽), 삭제가 일어나는 곳을 front라고 부른다.
정수기 옆 종이컵 디스펜서를 보면, 디스펜서 아래의 버튼을 누르면 밑에 있던 종이컵 하나만 나온다. 이 종이컵 디스펜서에 종이컵을 채울 때는 맨 위의 뚜껑을 열고 채운다. 사용자가 사용할 때는 맨 밑에 있는 종이컵부터 사용하게 된다. 그렇게 되면 가장 먼저 들어간 종이컵이 가장 먼저 나가는 선입선출의 구조다. 큐 구조의 좋은 예시다.
컴퓨터에선 키보드에 자판을 이용하면 두드린 순서대로 문자가 나열된다. 먼저 친 내용이 먼저 표시되는 것 역시 큐 구조라고 할 수 있다. 프린터기를 쓸 때 여러 문서를 출력해도 인쇄 버튼을 누른 문서부터 차례로 출력되는 것 역시 큐 구조다.

 

다음은 위키백과에서 큐를 설명하는 내용이다.

 

https://ko.wikipedia.org/wiki/%ED%81%90_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0) 

큐 (자료 구조) - 위키백과, 우리 모두의 백과사전

큐는 먼저 집어넣은 데이터가 먼저 나오는 FIFO(First In First Out) 구조로 저장되는 형식을 말한다. 영어 단어 queue는 표를 사러 일렬로 늘어선 사람들로 이뤄진 줄을 말하기도 하며, 먼저 줄 선 사람이 먼저 나갈 수 있는 상황을 연상하면 된다. 나중에 집어넣은 데이터가 먼저 나오는 스택과 반대되는 개념이다.

 

정리하면 이렇다.

 

이름	스택	큐
특징	나중에 들어온 놈이 먼저 나간다	먼저 들어온 놈이 먼저 나간다
자료 삽입, 삭제	한 쪽 끝에서만 일어난다	한 쪽에선 삽입, 다른 한 쪽에선 삭제가 발생한다

 

그럼 스택과 큐를 자바로 구현하면 어떤 형태일까? 먼저 스택의 경우 고정된 크기를 갖는 배열, 동적으로 크기가 변하는 ArrayList를 사용해서 만들 수 있겠다.

자바에선 기본적으로 스택을 사용할 수 있게 Stack 클래스를 제공한다. 그러나 자바를 써서 배열로 스택을 직접 구현해 어떤 식으로 동작하는지 확인해보자. 배열을 사용한 형태는 아래와 같다.

 

public class Stack {

    // 스택의 요소를 저장할 int[]
    private int[] arr;
    // 스택의 맨 위
    private int top;
    // 스택의 총 용량
    private int capacity;

    Stack(int size) {
        arr = new int[size];
        capacity = size;
        top = -1;
    }

    // 요소를 스택의 맨 위에 추가
    public void push(int element) {
        if (isFull()) {
            System.out.println("스택이 꽉 찼어요!");
            System.exit(1);
        } else {
            System.out.println("삽입 : " + element);
            System.out.println("push() 호출 후 추가되는 숫자 : " + element);
            // top++로 하면 ArrayIndexOutOfBoundsException 에러가 발생한다
            arr[++top] = element;
        }
    }

    // 스택 안의 맨 마지막 값을 제거하는 메서드
    public int pop() {
        if (isEmpty()) {
            System.out.println("스택이 텅 비었어요!");
            System.exit(1);
        }

        return arr[top--];
    }

    // 스택이 꽉 찬 상태인지 확인해 T/F를 리턴하는 메서드
    public Boolean isFull() {
        return top == capacity - 1;
    }

    // 스택이 비어있는 상태인지 확인해 T/F를 리턴하는 메서드
    public Boolean isEmpty() {
        return top == -1;
    }

    // 스택의 크기를 구하는 메서드
    public int getSize() {
        return top + 1;
    }

    // 마지막 요소를 확인하는 메서드
    public int peek() {
        if (!isEmpty())
            return arr[top];
        else
            System.exit(1);
        return -1;
    }

    // 스택 안의 요소들을 출력하는 메서드
    public void printStack() {
        for (int i = 0; i <= top; i++)
            System.out.print(arr[i] + ", ");
    }

    public static void main(String[] args) {

        Stack stack = new Stack(5);

        stack.push(1);
        stack.push(2);
        stack.push(3);

        System.out.print("마지막에 담긴 요소 : " + stack.peek());
        System.out.println();
        System.out.print("스택 안의 모든 요소 출력 : ");
        stack.printStack();
        System.out.println("\n스택의 크기 : " + stack.getSize());

        System.out.println("============================================================");
        stack.pop();
        System.out.println("\n삭제 후...");
        stack.printStack();
        System.out.println("\n스택의 크기 : " + stack.getSize());
    }

}

 

이 코드를 실행하면 결과는 아래와 같다.

 

메인 메서드 안에서 push()를 3번 호출하기 때문에 그 메서드의 인자로 넘긴 숫자들이 쌓여서 printStack()으로 출력했을 때 스택 안에 담긴 걸 볼 수 있다. 또한 peek()으로 맨 마지막에 담겨진 아이템을 확인할 수 있다.

그리고 가로줄 밑에서 pop()을 호출해 맨 마지막에 넣은 요소를 지워서 3이 없어진 걸 볼 수 있다.

int top 변수를 0이 아니라 -1로 초기화한 이유는 편의를 위해서다. 0으로 초기화해도 저 코드는 작동하지만 1~5까지 push()로 넣을 경우 에러가 발생한다. 그 때 예외처리를 하기 귀찮아서 -1로 초기화했다.

그 외에는 딱히 어려운 코드가 있어서 보면 이런 로직으로 스택을 구성하는구나 하고 파악이 가능하다.

 

다음은 ArrayList를 사용해 스택을 구현한 예제 코드다.

import java.util.ArrayList;

public class ListStack {
    private ArrayList<String> elements = new ArrayList<>();

    @Override
    public String toString() {
        return "elements 안의 요소들 =" + elements;
    }

    public void push(String element) {
        elements.add(element);
    }

    public String pop() {
        if (elements.isEmpty()) {
            System.out.println("스택이 텅 비었어요!");
            System.exit(1);
        }
        String top = elements.get(elements.size() - 1);
        elements.remove(elements.size() - 1);
        return top;
    }

    public String peek() {
        if (elements.isEmpty()) {
            System.out.println("스택이 텅 비었어요!");
            System.exit(1);
        }
        return elements.get(elements.size() - 1);
    }

    public int getSize() {
        return elements.size();
    }

    public Boolean isEmpty() {
        return elements.isEmpty();
    }

    public static void main(String[] args) {
        ListStack stack = new ListStack();
        System.out.println("스택이 비었는가? : " + stack.isEmpty());

        stack.push("A");
        stack.push("B");
        stack.push("C");

        System.out.println("현재 스택의 크기 : " + stack.getSize());
        System.out.println("스택 출력 : " + stack);
        System.out.println("마지막 요소 : " + stack.peek());
        System.out.println("스택이 비었는가? : " + stack.isEmpty());

        System.out.println("============================================================");
        stack.pop();
        System.out.println("현재 스택의 크기 : " + stack.getSize());
        System.out.println("스택 출력 : " + stack);
        System.out.println("마지막 요소 : " + stack.peek());
    }
}

 

ArrayList로 구현했기 때문에 배열로 구현한 것과 비교했을 때 구현 방법에서 다소의 차이는 있지만 큰 틀은 똑같다.

스택을 직접 구현할 때 반드시 구현해야 하는 것은 아래와 같다.

 

• push() : 선언된 스택에 요소를 채워넣는 메서드. 알맞은 매개변수를 인자로 넘겨야 한다
• pop() : 맨 마지막 요소를 제거하는 메서드
• peek() : 스택에 존재하는 요소 중 가장 마지막에 삽입된 요소를 출력하는 메서드

 

isFull(), isEmpty()는 필수 구현이 아니고 확인용 메서드에 가깝다고 생각해서 제외했다.

 

다음은 큐를 배열로 구현하는 예제 코드다.

public interface Queue {
    boolean isEmpty();
    boolean isFull();
    void enqueue(char element);
    void dequeue();
    void peek();
    void clear();
}

public class QueueImpl implements Queue {

    private int front;
    private int rear;
    private final int queueSize;
    private char[] arr;

    public QueueImpl(int size) {
        front = -1;
        rear = -1;
        queueSize = size;
        arr = new char[queueSize];
    }

    @Override
    public boolean isEmpty() {
        if (front == rear) {
            front = -1;
            rear = -1;
        }
        return (front == rear);
    }

    @Override
    public boolean isFull() {
        return rear == (queueSize - 1);
    }

    @Override
    public void enqueue(char element) {
        if (isFull()) {
            System.out.println("큐가 꽉 찼어요!");
        } else {
            arr[++rear] = element;
            System.out.println("삽입된 요소 : " + element);
        }
    }

    @Override
    public void dequeue() {
        if (isEmpty()) {
            System.out.println("큐가 텅 비었어요!");
        } else {
            System.out.println("삭제된 아이템 : " + arr[front + 1]);
            front = (front + 1) % queueSize;
        }
    }

    @Override
    public void peek() {
        if (isEmpty()) {
            System.out.println("큐가 텅 비었어요!");
        } else {
            System.out.println("peek 된 요소 : " + arr[front + 1]);
        }
    }

    @Override
    public void clear() {
        if (isEmpty()) {
            System.out.println("큐가 텅 비었어요!");
        } else {
            front = -1;
            rear = -1;
            arr = new char[queueSize];
            System.out.println("큐가 비워졌어요!");
        }
    }

    public void printQueue() {
        if (isEmpty()) {
            System.out.println("큐가 텅 비었어요!");
        } else {
            System.out.print("큐 안의 요소들 : ");
            for (int i = front + 1; i <= rear; i++) {
                System.out.print(arr[i] + ", ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        QueueImpl queue = new QueueImpl(5);

        queue.enqueue('A');
        queue.printQueue();
        System.out.println();
        queue.enqueue('B');
        queue.printQueue();
        System.out.println();
        queue.enqueue('C');
        queue.printQueue();
        System.out.println();
        queue.enqueue('D');
        queue.printQueue();
        System.out.println();
        queue.enqueue('E');
        queue.printQueue();
        System.out.println();

        queue.dequeue();
        queue.printQueue();
        System.out.println();

        queue.dequeue();
        queue.printQueue();
        System.out.println();

        queue.dequeue();
        queue.printQueue();
        System.out.println();

        queue.dequeue();
        queue.printQueue();
        System.out.println();

        queue.peek();
        queue.printQueue();
        System.out.println();

        queue.clear();
        queue.printQueue();
    }
}

 

다음은 큐를 ArrayList로 구현한 예제 코드다.

public interface ListQueue<E> {
    void enqueue(E element);
    E peek();
    E dequeue();
    void clear();
}

import java.util.ArrayList;
import java.util.List;

public class ListQueueImpl<E> implements ListQueue<E> {

    private List<E> list;
    private int size;

    public ListQueueImpl() {
        list = new ArrayList<>();
    }

    @Override
    public void enqueue(E element) {
        list.add(element);
        size++;
    }

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }

        return list.get(0);
    }

    private boolean isEmpty() {
        return size == 0;
    }

    @Override
    public E dequeue() {
        size--;
        return list.remove(0);
    }

    public int getSize() {
        return size;
    }

    @Override
    public String toString() {
        StringBuilder result = new StringBuilder("(" + list.get(0));
        for (int i = 1; i < size; i++) {
            result.append(", ").append(list.get(i));
        }
        result.append(")");
        return result.toString();
    }

    @Override
    public void clear() {
        size = 0;
    }

    public static void main(String[] args) {
        ListQueueImpl<Integer> queue = new ListQueueImpl<>();
        queue.enqueue(12);
        queue.enqueue(9);
        queue.enqueue(-10);
        queue.enqueue(-19);
        queue.enqueue(21);
        queue.enqueue(81);

        System.out.println(queue);
        System.out.println("큐 안의 1번째 요소 : " + queue.peek());

        System.out.println("큐에서 삭제할 요소 : " + queue.dequeue());
        System.out.println("dequeue() 후 큐 안의 요소들 : " + queue);

        System.out.println("현재 큐의 크기 : " + queue.getSize());
        queue.clear();
        System.out.println("clear() 후 큐의 크기 : " + queue.getSize());
    }
}

 

큐에 사용되는 메서드들은 아래와 같다.

 

• enqueue() : 큐의 마지막 위치에 데이터를 추가하는 메서드
• dequeue() : 큐의 첫 번째 위치에 있는 데이터를 반환하고 삭제하는 메서드
• clear() : 큐에 저장된 데이터들을 삭제하고 초기화하는 메서드
• peek() : 큐의 첫 번째 위치에 있는 데이터를 반환하기만 하는 메서드