[자료구조] 스택 vs 큐

스택(Stack)

 

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

 

스택의 사용 예시

 

1. 웹 브라우저 방문기록(뒤로 가기) : 가장 나중에 열린 페이지부터 다시 보여주는 형식으로 스택 구현
2. 역순 문자열 만들기 : 가장 나중에 실행된 것부터 실행을 취소한다
3. 후위 표기법 계산
4. 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)

 

 

스택(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. 우선순위가 같은 작업 예약 (ex: 프린터의 인쇄 대기열)
2. 은행 업무
3. 콜센터 고객 대기시간
4. 프로세스 관리
5. 너비 우선 탐색(BFS) 구현
6. 캐시 구현

 

큐(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로 삽입/삭제를 구현할 수 있습니다.