2월4일, DSA

 

 

 

Stack implementation : LinkedList 

 

    push <-  constant (tail에서 넣으면 됨)

    pop <- linear.  (tail 을 찾을 수는 있지만, 마지막 노드를 찾으려면 n번 이동해야됨)

 

그래서 stack의 top을 head에 넣으면은, pop도 constant time 필요 

 

 

 

 

Queue

    -enqueue  :  constant time 

    -deque  : constant time

 

Queue with array

    -잘 모르겟음.. 

(gpt)

📌 배열 기반 Queue에서 나머지를 사용하는 이유 (Circular Queue)

배열(Array)로 Queue를 구현할 때, 나머지 연산 (%)을 사용하여 원형 큐 (Circular Queue)를 만드는 이유를 설명할게.

---

✅ 1. 기본적인 배열 기반 큐 (문제점)

배열을 사용해서 큐를 구현할 때, front와 rear라는 두 개의 인덱스를 사용해 요소를 추가/삭제하는 방식이야.

기본적인 enqueue() / dequeue() 구현

class ArrayQueue {
    private int[] data;
    private int front, rear, size;
    private int capacity;

    public ArrayQueue(int capacity) {
        this.capacity = capacity;
        this.data = new int[capacity];
        this.front = 0;
        this.rear = 0;
        this.size = 0;
    }

    public void enqueue(int elem) {
        if (size == capacity) {
            System.out.println("Queue is full");
            return;
        }
        data[rear] = elem;
        rear++;  // rear를 증가
        size++;
    }

    public int dequeue() {
        if (size == 0) {
            System.out.println("Queue is empty");
            return -1;
        }
        int value = data[front];
        front++;  // front를 증가
        size--;
        return value;
    }
}

---

❌ 문제 발생: 빈 공간 낭비

위 코드에서는 rear와 front를 계속 증가시키면서 큐를 구현하지만, 큐가 꽉 찬 것처럼 보이지만 실제로는 비어있는 공간이 존재할 수 있음.

예제: 큐 크기 5

1. enqueue(1), enqueue(2), enqueue(3), enqueue(4), enqueue(5) → rear = 5
2. dequeue(), dequeue(), dequeue() → front = 3
3. enqueue(6) 시도 → 공간이 남았는데도 rear == 5라서 큐가 꽉 찼다고 나옴!

   [ _, _, _, 4, 5 ]  (front=3, rear=5, size=2)
   

💡 문제점: rear가 끝까지 가면 다시 앞쪽 공간을 활용하지 못함 → 비효율적!

---

✅ 2. 원형 큐 (Circular Queue)로 해결

이 문제를 해결하려면 나머지 연산 (%)을 사용하여 rear와 front가 배열의 시작으로 돌아오도록 하면 돼.

rear = (rear + 1) % capacity;
front = (front + 1) % capacity;

이렇게 하면 배열을 원형(Circular)처럼 사용하여 공간을 낭비하지 않음.

🔹 원형 큐 적용 코드

class CircularQueue {
    private int[] data;
    private int front, rear, size;
    private int capacity;

    public CircularQueue(int capacity) {
        this.capacity = capacity;
        this.data = new int[capacity];
        this.front = 0;
        this.rear = 0;
        this.size = 0;
    }

    public void enqueue(int elem) {
        if (size == capacity) {
            System.out.println("Queue is full");
            return;
        }
        data[rear] = elem;
        rear = (rear + 1) % capacity;  // 원형으로 이동
        size++;
    }

    public int dequeue() {
        if (size == 0) {
            System.out.println("Queue is empty");
            return -1;
        }
        int value = data[front];
        front = (front + 1) % capacity;  // 원형으로 이동
        size--;
        return value;
    }
}

---

✅ 3. 원형 큐의 동작 원리

배열 크기가 5일 때 enqueue()와 dequeue() 연산을 수행해 보자.

(1) 초기 상태

front = 0, rear = 0, size = 0

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

data = [1, 2, 3, 4, 5]
front = 0, rear = 5 (rear = 5 % 5 = 0)

(3) dequeue(), dequeue(), dequeue() 실행

data = [_, _, _, 4, 5]
front = 3, rear = 0

(4) enqueue(6), enqueue(7), enqueue(8)

data = [6, 7, 8, 4, 5]
front = 3, rear = 3 (rear = 3 % 5 = 3)

✅ rear가 배열의 처음으로 돌아가면서 빈 공간을 재사용할 수 있음!

---

✅ 4. 왜 나머지 연산 (%)을 사용해야 할까?

1. 배열이 끝까지 차도 다시 앞에서부터 사용할 수 있도록 함.
2. 항상 rear와 front를 배열 크기 안에서 유지할 수 있음.
3. O(1) 연산을 유지하면서, 추가적인 공간 낭비 없이 큐를 사용할 수 있음.

💡 결론: 원형 큐(Circular Queue)는 나머지 연산을 사용해서 공간을 재활용하고, 큐가 가득 차는 문제를 해결할 수 있도록 한다! 🚀