Stack & Queue

Stack이란?

• First In Last Out(FILO)형식으로 가장 먼저 들어간 데이터가 가장 마지막에 나올 수 있다.
• 한쪽 끝에서만 데이터를 추가하거나 삭제할 수 있다.
  
• 연속된 메모리 영역을 스택 영역으로 사용하고 현재 스택의 마지막 아이템 위치를 가리키는 포인터를 사용한다.
• 데이터가 추가되면 포인터의 위치를 옮겨 해당 포인터 위치에 데이터를 할당한다.(그림에서는 포인터가 위로 이동)
• 데이터를 꺼내오면 해당 포인터에 위치한 데이터를 가져오고 포인터를 옮긴다.(그림에서는 포인터가 아래로 이동)
• 데이터를 삽입하거나 꺼내는 연산 모두 스택의 마지막 아이템을 가리키는 포인터로 가능하기 때문에 시간 복잡도는 O(1)이다.

Stack의 연산

• push : 스택에 데이터를 추가하는 연산
• pop : 스택에서 가장 마지막 데이터를 꺼내는 연산
• top : 스택에서 가장 마지막 데이터를 반환하는 연산(스택 마지막 자리에는 남아있음)
• empty : 스택이 비어있는지 확인하는 연산

사용처

• 매칭되는 쌍 찾기 : 수식 표현에서 여는 괄호와 닫는 괄호가 매칭되는지 또는 HTML 문서에서 여는 태그와 닫는 태그가 잘 매칭되는지 확인할 때 스택을 이용해 확인한다.
• 수식 표현식 변경 : 컴퓨터 연산 시 중위 표현식을 후위 표현식으로 변환할 때 스택을 사용하여 연산을 처리한다.
• 작업 취소(Undo) : 프로그램에서 (Ctrl + Z)처럼 마지막으로 한 작업을 취소할 때 지금까지 한 작업들을 저장하는 용도로 스택을 사용한다.
• JVM

  자바의 메모리 영역 중 stack은 메소드, 지역 변수를 저장하기 위해 쓰인다.
  메소드가 호출되면 메소드의 매개변수, 지역 변수, 메소드가 실행이 끝나고 나서 반환해야하는 메모리 주소를 담은 새로운 프레임(Frame)이 스택의 가장 위쪽에 추가된다.
  자바의 쓰레드는 각각의 stack을 가지고 있기 때문에 여러 쓰레드들이 각기 다른 메소드를 동시에 실행할 수 있다.
  쓰레드의 스택이 비게 되면 쓰레드는 삭제된다.
  쓰레드가 처음 생성될 때 스택의 크기는 고정된다.
  스택의 크기가 충분하지 않다면, 쓰레드가 너무 많은 값들을 stack에 push하려하고, 이 때 런타임에러인 Stack Overflow가 발생한다.

Queue란?

• First In First Out(FIFO)형식으로 가장 처음에 들어간 데이터가 처음에 나올 수 있다.
• Queue는 3개의 포인터를 사용한다. 하나는 큐 자체에 접근하기 위한 포인터와 나머지 두 개는 큐의 가장 앞에 존재하는 데이터를 가리키는 포인터(Front)와 가장 뒤에 존재하는 데이터를 가리키는 포인터(Rear)이다.
• 데이터를 삽입하는 경우 Rear 포인터의 위치를 옮긴 후 해당 위치에 데이터를 할당한다.
• 데이터를 꺼내는 경우 Front 포인터에 위치한 데이터를 반한환 뒤 해당 포인터의 위치를 옮긴다.

Queue의 연산

• init : 큐를 초기화한다.
• enqueue(e) : 주어진 아이템 e를 큐의 맨 뒤에 추가한다.
• dequeue : 큐가 비어있지 않으면 맨 앞 아이템를 삭제하고 반환한다.
• is_empty : 큐가 비어있으면 true를 아니면 false를 반환한다.
• peak : 큐가 비어있지 않으면 맨 앞 아이템을 삭제하지 않고 반환한다.
• is_full : 큐가 가득 차 있으면 true를 반환한다.
• size : 큐의 모든 요소들의 개수를 반환한다.

Queue의 파생

원형 큐 (Circular Queue)

일반적인 큐에서 데이터를 꺼내는 경우 배열 앞 쪽이 비어버리기 때문에 공간 활용을 위해 배열에 존재하는 데이터를 앞 쪾에 비는 만큼 이동시켜야 하는 단점이 존재한다.
일반 큐와 달리 원형 큐는 데이터를 꺼내올 때 데이터를 이동하지 않는다. 대신 Front포인터를 한 칸 뒤로 이동시킨다. 배열의 끝에 도달할 경우 다시 배열의 처음으로 돌아와 데이터를 저장하는 배열을 순환 구조로 사용할 수 있도록 한다.

우선 순위 큐 (Priority Queue)

우선 순위가 높은 데이터가 먼저 나오게 되는 큐. FIFO의 특성을 잃는다.
배열을 사용하여 구현되는 큐와 달리 우선 순위 큐는 힙(Heap)을 사용하여 구현한다.