스택과 큐

 

스택

---

스택은 배열과 마찬가지로 데이터를 저장하고, 데이터를 꺼내기 위해 사용하는 자료구조 중 하나이다. 스택은 이와 다르게 최근에 저장한 데이터만 꺼내올 수 있다. 스택이라는 이름 뜻 그대로, 데이터를 차곡차곡 쌓아 저장하고, 데이터를 꺼낼 땐 위에 쌓아 넣은 것부터 하나씩 추출하는 자료구조이다. 이러한 스택의 특성을 가리켜 후입선출(Last In, First Out) 특성을 가진다고 한다.

스택의 시간복잡도

push

push 함수는 스택의 맨 위에 데이터를 삽입한다. 즉, 스택 내부에 있는 다른 데이터에 접근하지 않기 때문에, 어떤 데이터가 들어오더라도 시간복잡도는 항상 같다.이 경우, Big-O 표기법에 따라 O(1)로 표기한다.

pop

pop 함수도 push함수와 마찬가지다. 다른 데이터에 접근할 필요 없이 항상 맨 위의 데이터만 받아오면 된다. 따라서, pop 함수도 O(1) 시간복잡도를 가진다.

스택의 응용

여러 프로그램에서 사용되는 Undo(Ctrl + z) 명령어가 대표적인 스택 활용 예시다. 프로그램 내의 변경 점들을 스택에 넣고, Undo 명령어를 실행하면 스택에서 데이터를 하나씩 꺼내오는 것이다.

큐

---

큐는 스택과 반대로, 선입선출(First In, First Out)의 특성을 갖는 자료구조다. 즉, 데이터를 삽입한 순서대로 데이터를 추출 하는 것이다. 큐는 추가, 삭제에 O(1) 시간복잡도를 가지고 탐색에 O(n) 시간복잡도를 가진다.

큐는 최근 삽입된 데이터 위치와 가장 오래된 데이터의 위치 두 가지를 기억해야 한다. 삽입은 최근 삽입된 데이터의 위치가 필요하고, 추출은 가장 오래된 데이터의 위치가 필요하기 때문이다.

 

• head : 가장 오래된 데이터의 위치
• tail : 가장 최근 추가된 데이터의 위치

원형 큐

선형 큐는 tail이 큐의 마지막 공간을 가리키고 있을 때, dequeue 함수로 발생한 배열의 빈 공간을 활용할 수 없다. 이러한 선형 큐의 문제점을 해결하기 위해, 원형 큐라는 변형된 자료구조가 생겼다. 쉽게 말하면 원형 큐는 큐를 원형으로 제작한 자료구조다.

 

 

head, tail이 배열의 마지막 인덱스에 도착하면 다시 배열의 첫 부분으로 돌려주어서 원형 큐를 구현한다. 그러기 위해서 tail이 0부터 4일 땐 그대로 값을 유지하고, 5일 땐 0으로 되돌려 줘야하는데, 이 때 모듈로 연산자 ( % ) 를 사용하면 된다. tail, head를 큐의 크기로 나눈 나머지로 변경해 주는 것이다. 아래 자바 코드를 참고하자.

class Queue {
    private int MAX_QUEUE_SIZE = 5;
    private int queue[];
    private int head;
    private int tail;

    public Queue() {
        head = -1;
        tail = -1;
        queue = new int[MAX_QUEUE_SIZE];
    }

    boolean is_empty() {
        if (head == tail) {
            return true;
        }
        return false;
    }

    boolean is_full() {
        if ((tail + 1) % MAX_QUEUE_SIZE == head) {
            return true;
        }
        return false;
    }

    void enqueue(int item) {
        if (this.is_full()) {
            System.out.println("큐에 더이상 데이터를 넣을 수 없습니다.\n");
            return ;
        }
        tail = (tail + 1) % MAX_QUEUE_SIZE;
        queue[tail] = item;
    }

    int dequeue() {
        if (is_empty()) {
            System.out.println("큐가 비어있습니다. \n");
            return -1;
        }
        head = (head + 1) % MAX_QUEUE_SIZE;
        return queue[head];
    }
}
public class Main {
    public static void main(String[] args) {
        Queue queue = new Queue();

        queue.enqueue(1);
        queue.enqueue(2);
        queue.enqueue(3);
        System.out.println("pop :" + queue.dequeue());
        System.out.println("pop :" + queue.dequeue());
        System.out.println("pop :" + queue.dequeue());

        queue.enqueue(4);
        queue.enqueue(5);
        queue.enqueue(6);
        System.out.println("pop :" + queue.dequeue());
        System.out.println("pop :" + queue.dequeue());
        System.out.println("pop :" + queue.dequeue());
    }
}

큐 사용

인쇄와 같은 우선순위가 필요한 대기열이나, 선입 선출이 필요한 대기열, 윈도우의 스케쥴링 시스템 등에서 사용된다. BFS, 너비 우선 탐색에서 처리할 노드 리스트를 저장하는 용도로 큐를 사용하기도 한다.

참조

---

https://codemate.kr/project/%EC%BD%94%EB%94%A9-%ED%85%8C%EC%8A%A4%ED%8A%B8-Level-1/6-3.-%EC%8A%A4%ED%83%9D

https://codemate.kr/project/%EC%BD%94%EB%94%A9-%ED%85%8C%EC%8A%A4%ED%8A%B8-Level-1/9-2.-%EC%9B%90%ED%98%95-%ED%81%90