시간복잡도를 유지하면서, 배열로 스택과 큐를 구현할 수 있을까요?

배열로 스택은 쉽게 구현 가능하지만, 큐는 원형 배열(Circular Array) 을 사용해야 O(1)을 유지할 수 있습니다.

배열로 스택 구현 - O(1)

top 포인터만으로 간단하게 구현 가능합니다.

class ArrayStack {
    int[] arr;
    int top = -1;

    ArrayStack(int size) { arr = new int[size]; }

    void push(int data) {   // O(1)
        arr[++top] = data;
    }

    int pop() {             // O(1)
        return arr[top--];
    }

    int peek() {            // O(1)
        return arr[top];
    }
}

배열로 큐 구현 - 문제점

단순 배열로 구현하면 dequeue 시 앞 공간이 낭비됩니다.

enqueue(1,2,3) → dequeue()

[_][2][3][_][_]
    ↑
   front

앞 공간 재사용 불가 → front가 뒤로만 이동 → 공간 낭비

원형 배열로 큐 구현 - O(1)

front와 rear를 나머지 연산(%) 으로 순환시켜 공간을 재사용합니다.

capacity = 5

enqueue(1,2,3) → dequeue() → dequeue() → enqueue(4,5)

[4][5][3][_][_]
       ↑  ↑
      rear front (역전된 것처럼 보이지만 정상)

front = (front + 1) % capacity 로 순환

class CircularQueue {
    int[] arr;
    int front = 0, rear = 0, size = 0;
    int capacity;

    CircularQueue(int capacity) {
        this.capacity = capacity;
        arr = new int[capacity];
    }

    void enqueue(int data) {    // O(1)
        arr[rear] = data;
        rear = (rear + 1) % capacity;  // 순환
        size++;
    }

    int dequeue() {             // O(1)
        int data = arr[front];
        front = (front + 1) % capacity;  // 순환
        size--;
        return data;
    }

    boolean isEmpty() { return size == 0; }
    boolean isFull()  { return size == capacity; }
}

시간복잡도 비교

정리

Java의 ArrayDeque도 내부적으로 원형 배열로 구현되어 있습니다.