[Data Structure / Java] ✒️ Stack, Queue

Stack이란?

Stack이란 쌓아 올린다는 것을 의미.

따라서 Stack 자료구조라는 것은 책을 쌓는 것처럼 차곡차곡 쌓아 올린 형태의 자료구조를 말한다.

 

Stack의 특징

Stack은 위의 사진처럼 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을 수 있고,Top으로 정한 곳을 통해서만 접근할 수 있다.가장 위에 있는 자료는 가장 최근에 들어온 자료를 가리키고 있으며, 삽입되는 새 자료는 top이 가리키는 자료의 위에 쌓이게 된다.Stack에서 자료를 삭제할 때에도 top을 통해서만 가능하다. 

• 데이터 넣기(Stack에서 top을 통해 삽입): push() 
• 데이터 최상위 값 빼기(top을 통한 삭제): pop()
• 비어있는지 확인: isEmpty()
• 꽉 차 있는지 확인: isFull()

따라서 Stack은 가장 마지막에 삽입된 자료가 가장 먼저 삭제된다는 구조적 특징을 갖게 된다. 입력과 출력이 한 곳(방향)으로 제한.이러한 Stack 구조를 후입선출(LIFO, Last-In-First-Out)구조라고 한다.

 

여기서 비어있는 Stack에서 원소를 추출하려고 할 때 stack underflow라고 하며,Stack이 넘치는 경우를 stack overflow라고 한다.

 

Stack 활용 예시

• 역순 문자열 만들기: 가장 나중에 입력된 문자부터 출력.
• 실행 취소(undo): 가장 나중에 실행된 것부터 실행을 취소.
• 후위 표기법 계산
• 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)
• 함수의 콜스텍
• + 스택포인터 (SP, Stack Pointer)
  (push와 pop할 때는 해당 위치를 알고 있어야 하므로 기억하고 있는 '스택 포인터(SP)'가 필요하다.

 

Stack Pointer는 다음 값이 들어갈 위치를 가리키고 있다. (처음 기본값은 -1)

private int sp = -1;

 

push

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

SP가 최대 크기와 같으면 return,

아니면 Stack의 최상위 위치에 값을 넣는다.

 

pop

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

SP가 0이 되면 null로 return,

아니면 Stack의 최상위 위치 값을 꺼내온다.

 

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;
}

SP 값 + 1이 MAX_SIZE와 같으면 true, 아니면 false

 

동적 배열 Stack

위처럼 구현하면 스택에는 MAX_SIZE라는 최대 크기가 존재해야 한다

(스택 포인터와 MAX_SIZE를 비교해서 isFull 메소드로 비교해야 되기 때문!)

 

최대 크기가 없는 Stack 만들기

arraycopy를 활용한 동적 배열 사용

public void push(Object o) {
    
    if(isFull(sp)) {
        
        Object[] arr = new Object[MAX_SIZE * 2];
        System.arraycopy(stack, 0, arr, 0, MAX_SIZE);
        stack = arr;
        MAX_SIZE *= 2; // 2배로 증가
    }
    
    stack[sp++] = o;
}

기존 Stack의 2배 크기만큼 임시 배열(arr)을 만들고,

arraycopy를 통해 stack의 인덱스 0부터 MAX_SIZE만큼을 arr 배열의 0번째부터 복사한다.

복사 후에 arr의 참조값을 stack에 덮어 씌운다.

마지막으로 MAX_SIZE의 값을 2배로 증가시켜주면 된다.

 

이러면, Stack이 가득 찼을 때 자동으로 확장되는 스택을 구현할 수 있다.

---

Queue란?

 

Queue의 사전적 의미는 줄, 혹은 줄을 서서 기다리는 것을 의미.따라서 은행에서 먼저 온 사람의 업무를 창구에서 처리하는 것과 같이 선입선출(FIFO, First In First Out)방식의 자료구조를 말한다.

 

Queue의 특징

정해진 한 곳(top)을 통해 삽입, 삭제가 이루어지는 Stack과는 달리 Queue는 한쪽 끝에서 삽입이, 다른 한쪽 끝에서는 삭제가 양쪽으로 이루어진다.이때 삭제 연산을 하는 곳을 프론트(front), 삽입 연산을 하는 곳을 리어(rear)로 정하여 각각의 연산 작업만 수행된다.좀 더 자세히 알아보면,Queue의 가장 첫 원소를 front, 끝 원소를 rear라고 부른다. 들어올 때는 rear로 들어오지만, 나올 때는 front부터 빠지는 특성을 가진다. Queue의 rear에서 이루어지는 삽입 연산을 인큐(enQueue),Queue의 front에서 이루어지는 삭제 연산을 디큐(deQueue)라고 부른다.

• 데이터 넣기: enQueue()
• 데이터 빼기: deQueue()
• 비어있는지 확인: isEmpty()
• 꽉 차 있는지 확인: isFull()

 

Queue 활용 예시

Queue는 주로 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용한다.

• 우선순위가 같은 작업 예약 (프린터의 인쇄 대기열)
• 은행 업무
• 콜센터 고객 대기시간
• 프로세스 관리
• 너비 우선 탐색(BFS, Breadth-First Search) 구현
• 캐시(Cache) 구현

기본값

private int size = 0; 
private int rear = -1; 
private int front = -1;

Queue(int size) { 
    this.size = size;
    this.queue = new Object[size];
}

 

enQueue

public void enQueue(Object o) {
    
    if(isFull()) {
        return;
    }
    
    queue[++rear] = o;
}

enQueue 시, 가득 찼다면 꽉 차 있는 상태에서 enQueue를 했기 때문에 overflow이고,

아니면 rear에 값 넣고 1 증가한다.

 

deQueue

public Object deQueue(Object o) {
    
    if(isEmpty()) { 
        return null;
    }
    
    Object o = queue[front];
    queue[front++] = null;
    return o;
}

deQueue를 할 때 공백이면 underflow이고

front에 위치한 값을 object에 꺼낸 후, 꺼낸 위치는 null로 채워준다.

 

isEmpty

public boolean isEmpty() {
    return front == rear;
}

front와 rear가 같아지면 비어진 것이다.

 

isFull

public boolean isFull() {
    return (rear == queueSize-1);
}

rear가 사이즈 -1과 같아지면 가득 찬 것이다.

 

일반 Queue의 단점: Queue에 빈 메모리가 남아 있어도, 꽉 차 있는 것으로 판단할 수 있다.

(rear가 끝에 도달했을 때)

이를 개선한 것이 '원형 Queue', 알아볼 것

---

Reference

• 슬기로운 개발생활 - 스택(Stack) & 큐(Queue)
• gyoogle / tech-interview-for-developer / Computer Science / Data Structure / Stack & Queue.md