Stack

선형 자료구조의 일종으로 LIFO(Last In Last Out, 후입선출)의 방식을 가지고 있다.

특징

• LIFO
  나중에 넣은 것이 가장 먼저 나온다.
  박스에 책을 차곡차곡 쌓는 것과 비슷하다. 아래부터 한 권씩 쌓다보면 맨 위의 책만 보이기 때문에 아래의 책을 꺼내려면 윗쪽의 책부터 한권씩 다시 꺼내야 한다.

• 맨 위의 요소를 top으로 가리킨다.
  삽입(push)을 할 때에는 top 위에 데이터를 넣고,
  제거(pop)를 할 때에는 top이 가리키는 데이터를 제거한다.

활용 예시

• 웹 브라우저 방문기록: 뒤로가기를 누르면 가장 최근 페이지부터 다시 보여준다.
• 문자열 역순 출력: 가장 나중에 입력된 문자부터 출력한다.
• 실행 취소 (undo): 가장 나중에 실행된 것부터 실행을 취소한다.
• 후위 표기법 계산
• 깊이 우선 탐색(DFS): 나중에 시작된 함수가 먼저 끝난다.

한계

스택에 계속 데이터를 넣어야 할 때, 스택에 데이터를 저장할 수 있는 공간이 모두 차서 더이상 데이터를 넣을 수 없는 경우가 생긴다.
이런 경우에 2가지의 방법으로 해결할 수 있다.

• 동적 배열 스택
• 연결 리스트(Linked List)

1. 동적 배열 스택
push 함수를 수정하여 스택이 모두 찬 경우에 스택의 크기를 2배만큼 늘려주는 방법이다.

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

기존 스택의 2배 크기(MAX_SIZE * 2)의 임시 배열(arr)을 만들고 arraycopy를 통해 임시 배열에 기존 스택의 데이터를 복사한다.
그 후 arr의 참조값(주소)를 stack에 덮어씌우고 MAX_SIZE를 2배로 증가시킨다.
이런 방법을 사용하게 된다면, 스택이 모두 찬 경우에 자동으로 스택의 크기를 늘릴 수 있다.

2. 연결 리스트(Linked List)
스택 자체를 연결리스트 형태로 만드는 것이다. 그럼 데이터의 크기 제한이 사라진다.
하지만 연결리스트는 단점이 존재하기에 단점을 잘 인지하고 사용해야 한다.

Queue

Stack과 마찬가지로 선형 자료구조의 일종이지만 FIFO(Last In Last Out, 선입선출)의 방식을 가지고 있다.

특징

• FIFO
  흔히 식당 웨이팅이나 놀이기구 대기줄에 많이 비유한다. 먼저 온 사람이 먼저 들어가고 나중에 온 사람이 나중에 들어간다.

• 가장 먼저 들어간 데이터를 front, 가장 나중에 들어간 데이터를 rear이라고 한다.
  데이터를 삽입할 때에는 항상 rear 뒤에 넣고, 제거할 때에는 항상 front가 가리키는 데이터를 제거한다.

활용 예시

• Buffer
• BFS 구현
• 프로세스 관리
• 우선순위가 같은 작업 예약
• 캐시(Cache) 구현

한계

큐를 계속 삽입(enQueue)하다 보면 rear == size - 1이 되는 경우가 있다. 하지만 front에서 삭제 연산을 하는 것 때문에 큐가 꽉 차있지 않은 경우가 있다. 이를 해결하기 위해 순차 큐, 원형 큐, 연결 리스트(Linked List) 방법을 사용할 수 있다.

• 순차 큐
  배열을 큐로 구현한 것으로 크기가 제한되어 있고, 빈 공간을 사용하려면 모든 자료를 꺼내거나 한 칸씩 옮겨야 한다는 매우 비효율적인 단점이 있다.
  
• 원형 큐
  rear가 큐의 맨 뒤에 닿으면(rear == size - 1) 맨 앞으로 보내 다시 앞부터 데이터를 저장하여 원형으로 연결하는 방식이다.
  
• 연결 리스트(Linked List)
  큐의 단점을 극복하기 위해 가장 많이 사용하는 방식으로, 큐 자체를 연결리스트로 만드는 방법이다. 연결 리스트로 만들기 때문에 큐의 길이를 자유자재로 변경할 수 있어 오버플로우가 발생하지 않는다.

참고
한재엽님 Github Interview_Question_for_Beginner
gyoogle님 Github tech-interview-for-developer
https://devuna.tistory.com/22
https://velog.io/@gillog/큐Queue