🔗 참고 링크
개발자라면 무조건 알아야하는 자료구조! 5분컷
https://gyoogle.dev/blog/computer-science/data-structure/Stack & Queue.html
참고 링크의 강의 자료와 예시를 일부 가져와서 재 정리했습니다!

스택, 큐는 일종의 규칙이다.

자료구조의 방법이 코드로 정의 된 것이 아니라 구조의 행동 양식만 정의 된 것을 뜻한다.
즉 규칙들만 이해하면 직접 스택 또는 큐라는 자료구조를 만들 수 있다.

스택(Stack)

입력과 출력이 한 곳(방향)으로 제한된다.
팬케이크를 생각하면 편하다.

쌓을때 위에서부터 쌓고, 없앨 때도 위에서 부터 없앤다
즉, 스택은 배열이 수직으로 쌓여있는 것이다.

이런 방식을 LIFO(Last In First Out)이라고 한다.
Last in → 마지막으로 쌓아올린 팬케이크가
First Out → 가장 먼저 나간다.

스택은 언제 쓸까?

브라우저 뒤로가기

웹 페이지 히스토리 스택의 맨 위에서 한 페이지를 가져가는 것이다.

Ctrl+Z 되돌리기

• 유저의 행동을 차곡차곡 쌓다가 되돌리기를 누르는 순간 스택으로 가서 과거를 되돌릴 수 있는 것

함수의 콜스텍, 문자열 역순 출력, 연산자 후위표기법

스택의 사용예시

push와 pop할 때는 해당 위치를 알고 있어야 하므로 기억하고 있는 '스택 포인터(SP)'가 필요하다.
스택 포인터는 다음 값이 들어갈 위치를 가리키고 있다. (처음 기본값은 -1)

private int 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, 선입선출)이라고 한다.
가장 먼저 들어온 것이 가장 먼저 나온다.
새로운 요소는 마지막에 가고 맨 앞의 요소만 읽거나 삭제된다.
큐의 가장 첫 원소를 front, 끝 원소를 rear라고 부른다.
큐는 들어올 때 rear로 들어오지만, 나올때는 front부터 빠지는 특성을 가진다.

큐은 언제 쓸까?

• 이메일 되돌리기
• 푸쉬 알림 기능
• 쇼핑몰에서 주문을 처리하는 방식 (선착순)
• 콜센터의 백엔드 : 전화 온 순서대로 상담을 처리하는
• 버퍼
  • 마구 입력된 것을 처리하지 못하는 상황 (BFS)

큐의 사용 예시

데이터를 넣고 뺄 때 해당 값의 위치를 기억해야한다.
스택에서 스택 포인터와 같은 역할이다.
이 위치를 기억하고 있는게 front와 rear이다.

front : deQueue 할 위치 기억
rear : enQueue 할 위치 기억

기본값

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() : 데이터 뺌

ublic 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과 같아지면 가득찬 것이다.