만들면서 알아보는 컬렉션 프레임워크 - Stack, Queue

팽귄브렌디·2025년 5월 18일
Java

Java

목록 보기
4/7
post-thumbnail

Stack이란

위 그림과 같이 아래는 막혀 있고 위쪽만 열려 있는 구조이다. 값은 위쪽에서만 추가하거나 제거할 수 있다. 이렇게 나중에 넣은 값이 먼저 나오는 구조를 후입선출(LIFO, Last In First Out)이라 하며, 이러한 자료 구조를 스택(Stack)이라고 한다.

구현

public class MyStack<E> {

    private static final int DEFAULT_CAPACITY = 16;

    private Object[] stack;
    private int capacity;
    private int top;

    public MyStack() {
        capacity = DEFAULT_CAPACITY;
        stack = new Object[capacity];
        top = -1;
    }

    public MyStack(int capacity) {
        this.capacity = capacity;
        stack = new Object[capacity];
        top = -1;
    }

    public void push(E item) {
        if (isFull()) {
            throw new IllegalStateException("Stack is Full");
        }
        stack[++top] = item;
    }

    public E pop() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is Empty");
        }
        Object item = stack[top];
        stack[top] = null;
        top--;
        return (E) item;
    }
    
    public E peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is Empty");
        }
        return (E) stack[top];
    }

    public int size() {
        return top + 1;
    }
    
    public boolean isEmpty() {
        return top == -1;
    }

    private boolean isFull() {
        return top == capacity - 1;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (int i = 0; i <= top; i++) {
            sb.append(stack[i]);
            if (i != top) {
                sb.append(", ");
            }
        }
        sb.append("]");

        return sb.toString();
    }
}

  • 배열을 사용하여 스택을 구현하였다.

  • capacity는 저장할 배열의 크기를 의미하며 MyStack 생성 시 값을 지정하지 않으면 DEFAULT_CAPACITY가 사용된다.

  • MyStack은 생성 시 고정된 크기를 갖도록 구현하였다. 크기를 유동적으로 늘리고 싶다면, resize와 같은 메서드를 추가하여 리팩토링하는 것이 좋을 것 같다.

  • top은 배열의 마지막 위치를 가리킨다.

  • 생성자에서는 제네릭 타입을 직접 사용할 수 없기 때문에 Object 배열을 생성하였고, 저장할 값의 타입은 제네릭으로 제한하였다.

push()

  • top의 값을 하나 증가시키고, 스택의 마지막 위치에 값을 저장한다.
  • 만약 스택이 가득 차 있다면 값을 저장하지않고, 예외를 터트린다.

pop()

  • 스택의 마지막 값을 반환하며, 해당 값을 제거한다.
  • 만약 배열에 값이 없는 경우 예외를 터트린다.

peek()

  • 가장 마지막에 들어온 데이터를 조회만 하고, 제거하지는 않는다.
  • 만약 배열에 값이 없는 경우 예외를 터트린다.

isEmpty()

  • 스택이 비어있는지를 확인한다.
  • 값이 비여있다면 true를 비여있지 않다면 false를 반환한다.

isFull()

  • 스택이 가득 찼는지 확인한다.
  • 가득 찼다면 true를 가득 차지 않았다면 false를 반환한다.
  • isFull()의 경우 내부에서만 사용하기 때문에 private 메서드로 선언했다.

테스트 코드

MyStack<Integer> stack = new MyStack<>();
System.out.println("stack.size() = " + stack.size());

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

System.out.println("stack.peek() = " + stack.peek());

System.out.println("stack.pop() = " + stack.pop());
System.out.println("stack.pop() = " + stack.pop());
System.out.println(stack);
System.out.println("stack.size() = " + stack.size());

ArrayDeque<Object> objects = new ArrayDeque<>();

결과

stack.size() = 0
[1, 2, 3, 4]
stack.peek() = 4
stack.pop() = 4
stack.pop() = 3
[1, 2]
stack.size() = 2
  • push()를 통해 스택의 마지막에 값이 저장되는 것을 확인할 수 있다.
  • peek() 메서드를 통해 스택의 마지막 값을 반환하는 것을 확인할 수 있다.
  • pop() 메서드를 통해 스택의 마지막 값을 반환하고 제거되는 것을 확인할 수 있다.

자바에서 제공하는 Stack의 한계

자바에는 Stack 자료 구조를 구현한 Stack 클래스가 존재하지만 사용은 권장되지 않는다. 그 이유로 Stack 클래스가 Vector를 상속받아 구현되어 있기 때문이다.
Vector는 동기화(synchronized) 되어 있어, 단일 스레드 환경에서는 불필요한 성능 저하를 초래할 수 있다. 따라서 Stack 자료 구조를 사용하고자 할 경우 이후에 설명할 Deque 사용을 권장한다.

Queue란

Stack과 달리 위 아래가 다 뚫려있는 구조이다. 추가는 위쪽에서 진행되고, 제거는 아래쪽에서 진행된다. 이렇게 먼저 넣은 값이 먼저 나오는 구조를 선입 선출(FIFO, First In First Out)이라 하며, 이러한 자료 구조를 큐(Queue)라고 한다.

구현

public class MyQueue<E> {

    private static final int DEFAULT_CAPACITY = 16;

    private Object[] queue;
    private int front = 0;
    private int rear = 0;
    private int size = 0;
    private int capacity;

    public MyQueue() {
        capacity = DEFAULT_CAPACITY;
        queue = new Object[capacity];
    }

    public MyQueue(int capacity) {
        this.capacity = capacity;
        queue = new Object[capacity];
    }

    public void offer(E item) {
        if (isFull()) {
            throw new IllegalStateException("Queue is Full");
        }
        queue[rear] = item;
        rear = (rear + 1) % capacity;
        size++;
    }

    public E poll() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }

        E item = (E) queue[front];
        front = (front + 1) % capacity;
        size--;
        return item;
    }

    public E peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }

        return (E) queue[front];
    }

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

    private boolean isFull() {
        return size == capacity;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (int i = 0; i < size; i++) {
            sb.append(queue[i]);
            if (i != size - 1) {
                sb.append(", ");
            }
        }
        sb.append("]");
        return sb.toString();
    }
}

  • 배열을 사용하여 큐를 구현하였고, 원형 큐 방식으로 구현되었다.

  • capacity는 큐에 저장할 수 있는 크기를 의미하며 생성자에서 값을 지정하지 않으면 DEFAULT_CAPACITY이 사용된다.

  • MyQueue은 생성 시 고정된 크기를 갖도록 구현하였다. 크기를 유동적으로 늘리고 싶다면, resize와 같은 메서드를 추가하여 리팩토링하는 것이 좋을 것 같다.

  • front는 가장 먼저 들어온 데이터의 위치를 가리키며 poll()이나 peek() 시 사용된다.

  • rear는 새로운 데이터를 넣을 위치를 가리키며 offer() 시 사용된다.

  • 생성자에서는 제네릭 타입을 직접 사용할 수 없기 때문에 Object 배열을 생성하였고, 저장할 값의 타입은 제네릭으로 제한하였다.

offer()

  • 새로운 데이터를 큐에 추가하며 size의 값을 증가 시킨다.
  • 큐가 가득 차 있는 경우 예외를 터트린다.
  • 데이터를 rear 위치에 저장한 후 rear를 한 칸 이동시킨다.
    • 원형 큐 방식이기 때문에 (rear + 1) % capacity 연산을 사용해 배열의 맨 끝에 도달하면 다시 처음으로 되돌아 온다.

poll()

  • 큐에서 가장 먼저 들어온 데이터를 제거하고 반환한다.
  • 큐가 비어있으면 예외를 발생시킨다.
  • 데이터를 front 위치에서 꺼내고, front를 다음 위치로 이동시킵니다.
    • front도 rear와 마찬가지로 나머지연산을 활용하여 배열의 맨 끝에 도달하면 처음으로 되돌아 온다.
  • size를 감소시킨다.

peek()

  • 가장 먼저 들어온 데이터를 조회만 하고, 제거하지는 않는다.
  • 비어 있는 경우 예외를 터트린다.

isEmpty()

  • 큐가 비어있는지를 확인한다.
  • 값이 비어있다면 true를 비여있지 않다면 false를 반환한다.

isFull()

  • 큐가 가득 찼는지를 확인한다.
  • isFull()의 경우 내부에서만 사용하기 때문에 private 메서드로 선언했다.

테스트 코드

MyQueue<Integer> queue = new MyQueue<>(5);
queue.offer(1);
queue.offer(2);
queue.offer(3);
queue.offer(4);
queue.offer(5);
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());

queue.offer(6);
queue.offer(7);
queue.offer(8);
System.out.println(queue);

결과

[1, 2, 3, 4, 5]
queue.peek() = 1
queue.poll() = 1
queue.poll() = 2
queue.poll() = 3
[6, 7, 8, 4, 5]
  • offer() 메서드를 통해 큐의 마지막에 값이 저장되는 것을 확인할 수 있다.
  • peek() 메서드를 통해 큐의 첫 번째 값이 조회되는 것을 확인할 수 있다.
  • poll() 메서드를 통해 큐의 첫 번째 값이 반환되고 제거되는 것을 확인할 수 있다.
  • MyQueue의 경우 원형 큐 구조이기 때문에 0 ~ 2번 인덱스에 6, 7, 8이 저장되어 있는 것을 확인할 수 있다.

선형큐와 원형큐

선형큐

말 그대로 선형적인 구조를 가진 큐이다. 큐의 앞(front)과 뒤(rear)가 일직선으로 움직이며 한 방향으로만 데이터를 추가/삭제한다.

선형큐를 그림으로 표현하면 위 그림과 같다. 해당 그림은 큐가 가득 차 있는 상태이다. 만약 이 상태에서 데이터를 꺼낸다면 아래 그림과 같다.

0번과 1번 인덱스는 이미 데이터를 꺼낸 후라 비어 있지만 큐는 새로운 요소를 추가할수없다. 이는 rear가 배열의 끝까지 도달했기 때문이다. 이렇게 배열이 한쪽 방향으로만 사용되는 구조를 선형 큐(Linear Queue)라고 하며 사용하지 못하는 빈 공간이 생기는 공간 낭비의 문제가 있다.

원형큐

앞서 본 선형 큐는 앞부분에 빈 공간이 생겨도 rear가 끝까지 도달하면 더 이상 데이터를 넣을 수 없는 공간 낭비 문제가 있다. 이 문제를 해결한 구조가 바로 원형 큐(Circular Queue) 이다.

원형 큐는 마치 배열의 양 끝이 이어져 있는 것처럼, rear가 마지막 인덱스에 도달하면 다시 처음 인덱스로 돌아가는 구조이다. 아래 그림을 보며 구조를 살펴보자.

  • 왼쪽 그림: 원형 큐에 데이터를 순차적으로 추가한 상태이다.
    front는 가장 먼저 들어온 1을 가리키고 있고, rear는 마지막에 들어온 8을 가리키고있다.

  • 오른쪽 그림: 데이터를 일부 꺼낸 후 새로운 데이터를 추가한 상태입니다.
    front는 3을 가리키고 있으며, rear는 배열의 끝을 지나 다시 처음으로 돌아와 9를 삽입했다.

이처럼 원형 큐는 배열의 시작과 끝이 연결된 구조이기 때문에 비어 있는 공간을 재활용할 수 있어 공간 낭비를 줄일 수 있다.

Deque란

Deque는 Double Ended Queue의 약자로 이름에서 알 수 있듯이 양쪽 끝에서 요소를 추가하거나 제거할 수 있는 자료 구조다.
Deque는 일반적인 큐(Queue)와 스택(Stack)의 기능을 모두 포함하고 있어 매우 유연한 자료 구조로 활용된다.

대표적인 메서드는 다음과 같다

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

Deque의 대표적인 구현체로는 ArrayDeque와 inkedList가 있다. 또한 offerFirst()와 pollFirst() 메서드를 활용하면, 자바의 Stack 클래스를 사용하지 않고도 스택 자료 구조처럼 사용할 수 있다.

정리

  • 스택 자료 구조란 나중에 들어온 값이 먼저 나오는 후입 선출 구조이다.

  • 자바에서 제공하는 stack은 불필요한 동기화를 사용하기 때문에 Deque 자료구조를 가지고 스택을 구현하는게 권장된다.

  • 큐 자료 구조란 먼저 들어온 값이 먼저 나가는 선입 선출 구조이다.

  • 선형큐란 한방향으로만 값을 추가하고 제거할 수 있는 구조이다. 이 구조로 인해 앞 부분에 값이 비어있어도 값을 추가할 수 없는 단점이 있다.

  • 원형큐란 양 끝이 이어져 있는 것처럼, rear가 마지막 인덱스에 도달하면 다시 처음 인덱스로 돌아가는 구조이다. 이 구조로 선형큐의 단점을 해결할 수 있다.

제가 공부한 내용을 정리한 것이라 틀린 내용이 있을 수 있습니다. 보시고 틀린 내용을 알려주시면 감사하겠습니다

참고자료
김영한의 실전 자바 - 중급 2편

profile
팽귄브렌디
나만의 개발 일기장
이전 포스트

만들면서 알아보는 컬렉션 프레임워크 - HashMap, HashSet

다음 포스트

Lambda & Stream

0개의 댓글