19. 큐와 스텍, 데크

19.1 도입

  • 현실 세계의 규칙을 추상화하는 추상화 자료 구조(ADT)의 대표적인 예: 큐, 스택 ,데크
    • 배열과 연결 리스트를 이용해 구현할 수 있다.
  • 그럼에도 이름을 붙였다는 데는 이유가 있다.
    • 개발자간의 의사소통이 더 쉬워지고, 더 큰 그림을 보며 프로그램을 설계할 수 있기 때문이다
  • push: 자료구조에 자료를 넣는 작업
  • pop: 자료를 꺼내는 작업
  • 큐, 스택은 각각 넣고 빼는 방향에 따라 push, pop 연산을 O(1)에 지원
  • 데크(deque) 는 앞과 뒤 모두에서 push, pop 연산을 O(1)에 지원
  • C를 제외한 대부분의 언어들에서 스택, 큐, 데크는 기본적인 자료구조 이기 때문에 표준 라이브러리에서 구현체를 제공한다.

19.1.2 큐

  • 큐(queue)는 한쪽 끝에서 자료를 넣고, 반대 쪽 끝에서 자료를 꺼낼 수 있다.
  • 이와 같은 속성에 따라, 가장 먼저 들어간 자료를 가장 먼저 꺼내게 된다.
    • 선입선출(FIFO, First In First Out) 이라고도 한다.
    • 놀이공원에 선 줄이 대표적인 예

19.1.3 스택

  • 스택(stack)은 한쪽 끝에서만 자료를 넣고 뺄 수 있다.
  • 따라서, 가장 늦게 들어간 자료를 가장 먼저 꺼내게 된다.
    • 후입선출(LIFO, Last In First Out) 이라고도 한다.
    • 컴퓨터는 내부적으로 스택을 사용해 함수들의 문맥(context)를 관리한다. (함수의 호출 그 후,이전 함수로 돌아가는 상황)

19.1.4 데크(dequeue)

  • 데크 (dequeue: double-ended queue) 는 양쪽 끝에서 자료들을 넣고 뺄 수 있는 자료구조
  • 따라서, 데크를 이용하면 스택과 큐를 모두 구현 할 수 있다.

19.2 큐, 스택, 데크의 구현

19.2.1 연결 리스트를 통한 구현

  • 연결 리스트를 활용하면 양쪽 끝에서, 추가, 삭제를 O(1)에 할 수 있다.
  • 하지만, 노드의 할당과 삭제 그리고 포인터를 따라가는 데 선형시간이 걸리기 때문에, 연결 리스트를 통한 구현은 효율적인 구현이 아니다.

19.2.2 동적 배열을 통한 구현

  • 스택의 경우, 한쪽 끝에서만 자료의 추가, 삭제가 일어남으로 동적 배열을 곧 장 사용할 수 있다.

  • 하지만, 큐와 데크의 경우에는 뒤에서 원소를 추가하거나 삭제하기는 쉽지만, 배열의 맨 앞에 원소를 삭제하기 위해서는 O(N)의 시간이 걸린다.

    • 따라서, head, tail 변수로 첫 번째 와 마지막 원소의 위치를 유지하면서,

    • 맨 앞에서 원소를 꺼낼 때 뒤에 있는 원소들을 모두 앞으로 옮겨오는 대신 head를 다음 원소로 옮긴다.

    • 이 방법은 시간은 O(1)에 만족하지만, 공간이 너무 많이 버려진다는 문제가 발생

    • 앞의 버려지는 공간을 재활용하면서, 더 이상 원소를 삽입할 곳이 없을 때만, 동적 배열을 재할당하는 것으로 해결

    • tail이 배열의 끝에 도달하자 처음으로 다시 돌아가서 원소를 저장,

    • 동적 배열의 처음과 끝을 붙여 원형으로 만들었다고 볼 수 도 있다.

    • 이와 같은 배열의 구현을 환형 버퍼(circular buffer) 라고 한다.

image-20240402145108616.png

Reference