스택과 (원형) 큐 Stack & Queue 만들기

1. 소개

 

스택과 큐는 쉽고 간단하지만, 운영체제의 시스템 스택이나 스케줄링 등 다방면으로 활용되는 중요한 자료구조입니다.

스택과 큐는 모두 원소를 하나씩 저장하고 저장된 원소를 순서대로 출력 및 삭제하는 방식으로 동작합니다.

차이점으로는,

스택은 가장 나중에 입력된 원소가 가장 먼저 출력되는 후입선출(Last In First Out, LIFO) 방식인 반면,

큐는 가장 먼저 입력된 원소가 가장 먼저 출력되는 선입선출(First In First Out, FIFO) 방식입니다.

 

2. 구성

 

스택과 큐는 기본적으로

원소들을 저장할 저장소와

현재 위치를 기억하는 포인터,

그리고 현재 상태를 체크할 2가지 메서드,

핵심 기능인 삽입과 삭제를 위한 메서드 2개가 필요합니다.

 

3. 구현 with Java

 

(1) 스택

public class MyStack {
    private static final int MAX_SIZE = 100;
    private int[] stack = new int[MAX_SIZE];
    private int top = -1;

    public boolean isEmpty() {
        if(top == -1) return true;
        else return false;
    }

    public boolean isFull() {
        if(top >= MAX_SIZE) return true;
        else return false;
    }

    public boolean push(int val) {
        if(this.isFull()) return false;
        else stack[++top] = val;
        return true;
    }

    public int pop() {
        if(this.isEmpty()) return -1;
        else return stack[top--];
    }
}

편의상 int[]로 저장소 stack을 선언했습니다.

포인터인 top이 -1을 가리키고 있으면 스택은 비어있는 상태입니다. 원소 하나가 추가되면 0을 가리키게 됩니다.

isEmpty()와 isFull()은 top의 상태를 체크하여 스택이 비어있는지 가득 찼는지를 확인합니다.

push()는 스택이 비어있지 않다면 top을 이동시킨 뒤 top이 가리키는 위치에 입력값을 삽입합니다.

pop()은 스택이 비어있지 않다면 top이 가리키는 위치의 원소를 반환한 뒤, top을 후퇴시킴으로써 원소가 삭제된 것처럼 만들어줍니다.

 

(2) 큐

public class MyQueue {
    private static final int MAX_SIZE = 100;
    private int[] queue = new int[MAX_SIZE];
    private int front = -1, rear = -1;

    public boolean isEmpty() {
        if(front == rear) return true;
        else return false;
    }

    public boolean isFull() {
        if(rear == MAX_SIZE - 1) // 원형 큐 if((rear + 1) % MAX_SIZE == front)
        	return true;
        else return false;
    }

    public boolean enqueue(int val) {
        if(this.isFull()) return false;
        else {
            rear++; // 원형 큐 rear = (rear + 1) % MAX_SIZE;
            queue[rear] = val;
            return true;
        }
    }

    public int dequeue() {
        if(this.isEmpty()) return -1;
        else {
            front++; // 원형 큐 front = (front + 1) % MAX_SIZE;
            return queue[front];
        }
    }

}

큐의 경우는 양쪽에서 삽입과 삭제가 발생하기 때문에 삭제할 값을 가리키는 front와 삽입할 위치를 가리키는 rear 포인터가 필요합니다.

 

                                                                                 <초기 상태>

   front

-1

-

-

-

-

-

   rear

-----------------------------------------------------------------------------------------------------------------------------------

   front

-1

a

-

-

-

-

                                          rear

rear가 한 칸 전진하여 a를 삽입하고 (enqueue)

----------------------------------------------------------------------------------------------------------------------------------

삭제할 때는 front가 한 칸 전진하여 a를 삭제합니다. (dequeue)

                                          front

-1

-

-

-

-

-

                                          rear

---------------------------------------------------------------------------------------------------------------------------------

front와 rear가 같은 위치에 있으면 큐는 빈 상태입니다. (isEmpty)

rear가 최대 용량보다 하나 작은 위치에 있으면 큐는 가득 찬 상태입니다. (isFull)

위와 같이 구현할 경우 발생하는 문제점은,

front와 rear가 리스트의 끝에 도달하면 큐가 비어있음에도 불구하고 가득 찬 것처럼 보이기 때문에 공간을 제대로 활용할 수 없다는 것입니다.

최대 크기를 충분히 크게 만들고 매번 사용할 때마다 front, rear를 초기화해주면 그럭저럭 잘 사용할 수 있겠지만, 보다 효율적인 방법은 front와 rear가 리스트의 끝에 도달하더라도 계속 회전하도록 만드는 것입니다. 그걸 원형 큐, Circular Queue 라고 부릅니다.

원형 큐를 만드는 방법은 간단합니다. 위의 소스에서 주석처리된 부분과 같이 모듈러 연산을 이용해, 포인터를 한 칸씩 전진시키되 최대 크기를 넘어서면 다시 처음으로 돌아가도록 회전시키는 겁니다.

또 rear가 front보다 한 칸 뒤에 있으면 큐가 가득 찬 것이라고 볼 수 있습니다. 삽입이 이루어지지 않았는데 삭제가 있을수는 없기 때문에 front는 항상 rear보다 뒤에 있게 됩니다. 만약 rear가 한 바퀴를 돌아 front를 따라잡았다면, 그 사이의 모든 빈 공간에 원소를 채워넣었기 때문이라고 볼 수 있죠.

 

(3) 테스트

public class Main {
    public static void main(String[] args) {
        //stack test
        MyStack stk = new MyStack();

        for(int i = 0; i < 10; i++) {
            stk.push(i);
        }
        for(int i = 0; i < 10; i++) {
            System.out.print(stk.pop() + " ");
        }

        //queue test
        MyQueue q = new MyQueue();

        for(int i = 0; i < 10; i++) {
            q.enqueue(i);
        }
        for(int i = 0; i < 10; i++) {
            System.out.print(q.dequeue() + " ");
        }
    }
}