Stack & Queue

Stack

    - 나중에 넣은 element가 먼저 나오는 (LIFO : Last In First Out) 자료구조

특징

 

    - 삽입과 삭제 시간 복잡도 : O(1)

 

사용

    - 재귀 알고리즘에서 back-tracking할 때 주로 사용

    - 예시 : undo, 웹 페이지의 backward

 

 

 

 

Queue

    - 먼저 넣은 element가 먼저 나오는 (FIFO : First In First out) 자료구조

   

 

특징

    - 삽입과 삭제 시간 복잡도 : O(1)

 

사용

    - 시간 순으로 입력된 데이터를 처리하는 알고리즘에서 주로 사용

    - 예시 : 프로세스 관리, 프린터

 

종류

    - 선형 큐

        * 막대 모양

        * 크기가 제한되어 빈 공간을 사용하려면 모든 자료를 꺼내거나 자료를 한 칸씩 옮겨야 하는 단점

        * 오버플로우 : 큐가 꽉 차서 더 이상 넣을 수 없는 경우

        * 언더플로우 : 큐가 비어 있어 자료를 꺼낼 수 없는 경우

 

    - 환형 큐

        * 선형 큐에 공간이 남아 있지만 마지막 배열을 가리키고 있을 때 오버플로우가 발생하는 문제 해결

        * rear 위치가 큐의 front 위치에 닿으면, rear 위치는 front 위치를 가르키고 front 위치에 데이터를 넣는 방식