ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • Stack, Queue, Circular Queue
    공부/자료구조 2018. 7. 30. 23:02

    Stack

    LIFO(Last-In-First-Out) - 가장 마지막에 들어온 데이터가 가장 먼저 나감


    stack에서 데이터의 삽입, 삭제를 push와 pop으로 부름

    stack을 구현하기 위해선, 초기에 pop이 되지 않도록 array가 비어 있는지 확인하는 함수 (isEmpty)가 필요. 타입선언 언어라면 어레이의 사이즈를 정하기 때문에 어레이에 데이터가 가득 찼는지 확인하는 함수 (isFull)이 필요.

    Queue

    FIFO(First-In-First-Out) - 가장 먼저 들어온 데이터가 가장 먼저 나감


    위 그림에서 f(front)는 데이터의 시작위치를 가리키고 r(rear)은 현재 입력된 데이터의 위치를 가리킴


    stack과 유사하게 어레이가 비어있는지 확인하는 함수 (isEmpty)와 가득 찼는지 확인하는 함수 (isFull)이 필요함.

    Queue의 문제점

    데이터를 삭제할 때마다, 포인터가 한 칸씩 앞으로 이동하기 때문에 삭제된 뒷 공간을 활용할 수 없음.

    이러한 문제점 때문에 Circular Queue가 등장

    Circular Queue

    Queue처럼 r을 +1, f를 +1 하는 방식이 아닌 모드(%)를 사용하여 계산

    r = (r + 1) % MAX_CIRCULAR_QUEUE_SIZE
    f = (f + 1 ) % MAX_CIRCULAR_QUEUE_SIZE


    초기 f와 r은 0으로 시작위치가 동일.




    Circular Queue에 데이터를 입력하는 함수(add)나 데이터를 삭제하는 함수(delete)를 작성할 때 가장 최상단에 r과 f가 동일한지 비교하는 함수가 무조건 존재해야함.

    만일 r과f가 동일하다면 어레이는 더이상 삭제할 데이터가 없거나 이미 가득 찼다는 뜻

    댓글