[자료구조] 스택 vs 큐

스택(Stack)

 

입력과 출력이 방향이 한 곳으로 제한이 되며, 후입선출(LIFO, Last In First Out) 원칙을 가지고 있습니다.

 

스택의 사용 예시로는

 

1. 함수의 콜스택,

2. 문자열 역순 출력,

3. 연산자 후위 표기법

 

등이 있습니다.

 

 

스택(Stack) 코드 예시

 

데이터 넣을 때는 push()

데이터 최상위 값을 뺄 때는 pop()

비어있는 지 확인하고자 한다면 isEmpty()

꽉차있는 지 확인하고자 한다면 isFull()

 

 

push와 pop할 때는 해당 위치를 알고 있어야 하므로 기억하고 있는 '스택 포인터(SP)'가 필요함

스택 포인터는 다음 값이 들어갈 위치를 가리키고 있습니다. 처음 기본값은 -1입니다.

 

push

public void push(Object o) {
    if(isFull(o)) {
        return;
    }
    
    stack[++sp] = o;
}

 

스택 포인터가 최대 크기와 같으면 return 하고 아니면 스택의 최상위 위치에 값을 넣습니다.

 

pop

public Object pop() {
    
    if(isEmpty(sp)) {
        return null;
    }
    
    Object o = stack[sp--];
    return o;
    
}

 

스택 포인터가 0이 되면 null로 return 합니다.

아니면 스택의 최상위 위치 값을 꺼내옵니다.

 

isEmpty

private boolean isEmpty(int cnt) {
    return sp == -1 ? true : false;
}

 

입력 값이 최초 값과 같다면 true를, 아니면 false를 반환합니다.

 

isFull

private boolean isFull(int cnt) {
    return sp + 1 == MAX_SIZE ? true : false;
}

 

스택 포인터 값 + 1이 MAX_SIZE와 같으면 true, 아니면 false를 반환합니다.

 

---

 

큐(Queue)

 

입력과 출력을 한 쪽 끝(front, rear)로 제한하며, 선입선출(FIFO, First In First Out) 원칙을 가지고 있습니다.

 

큐의 사용 예시로는

 

1. 버퍼

2. 입력된 것을 처리하지 못하고 있는 상황

3. BFS

 

등이 있습니다.

 

큐(Queue) 코드 예시

 

큐의 가장 첫 원소를 front, 끝 원소를 rear라고 부릅니다.

큐는 들어올 때 rear로 들어오지만, 나올 때는 front부터 빠지는 특성을 가집니다.

접근방법은 가장 첫 원소와 끝 원소로만 가능합니다.

 

데이터 넣을 때는 enQueue()

데이터 뺄 때는 deQueue()

비어있는 지 확인할 때는 isEmpty()

꽉차있는 지 확인할 때는 isFull()

 

데이터를 넣고 뺄 때 해당 값의 위치를 기억해야 하며, 이 위치를 기억하고 있는 게 front와 rear입니다.

front는 deQueue 할 위치 기억하고, rear는 enQueue 할 위치 기억합니다.

 

enqueue

 

public void enqueue(E item) {
    Node oldlast = tail; // 기존의 tail 임시 저장
    tail = new Node; // 새로운 tail 생성
    tail.item = item;
    tail.next = null;
    if(isEmpty()) head = tail; // 큐가 비어있으면 head와 tail 모두 같은 노드 가리킴
    else oldlast.next = tail; // 비어있지 않으면 기존 tail의 next = 새로운 tail로 설정
}

 

데이터 추가는 끝 부분인 tail에 합니다.

기존의 tail은 보관하고, 새로운 tail을 생성합니다.

큐가 비었으면 head = tail을 통해서 head와 tail이 같은 노드를 가리키도록 합니다.

큐가 비어있지 않으면, 기존 tail의 next에 새로 만든 tail를 설정해줍니다.

 

dequeue

public T dequeue() {
    // 비어있으면
    if(isEmpty()) {
        tail = head;
        return null;
    }
    // 비어있지 않으면
    else {
        T item = head.item; // 빼낼 현재 front 값 저장
        head = head.next; // front를 다음 노드로 설정
        return item;
    }
}

 

데이터는 가장 먼저 들어온 것부터 빼야 하기 때문에 head로부터 꺼냅니다.

head의 데이터를 미리 저장해둡니다.

기존의 head를 그 다음 노드의 head로 설정합니다.

저장해둔 데이터를 return 해서 값을 빼옵니다.

 

이처럼 삽입은 tail, 제거는 head로 삽입/삭제를 구현할 수 있습니다.