# Stack & Queue - Stack 과 Queue 도 가장 심플하고 많이 사용되는 자료구조기 때문에 그 동작 원리에 대해서는 별로 말할게 없다. Stack은 가장 마지막에 들어간 것이 가장 먼저 나오는 LIFO 형태이고, Queue는 가장 처음에 들어간 값이 가장 먼저 나오는 FIFO 형태이다. Stack --- #### 구현 - Stack 을 구현할 때는 보통 array을 사용한다. 그리고 **`top`** 이라는 변수를 통해서 현재 Stack의 가장 마지막 값을 가리키도록 한다. - **Insert**: Stack을 추가할 때는 top을 하나씩 증가시키면서 배열에 값을 채우고, - **Delete**: 지울 때는 top의 값을 하나씩 줄여준다. - **IsEmpty**: 그리고 비어있을 때 top은 유효하지 않은 인덱스값인 -1을 갖고 있고, - **IsFull**: 꽉 찼을 때는 배열의 크기와 같은 값을 갖게 된다. - 물론 Linked List 를 활용해서 구현할 수 있다. 기본적으로 구현하는 Linked List의 경우 `tail` 이라는 값이 가장 마지막 값을 갖고 있다. 하지만 이 때는 기존에 구현한 Linked List와 다른 점이라고 하면 head의 포인터가 없고 tail만 존재하는 Linked List라고 볼 수 있다. #### 사례 - Stack의 사용 사례를 생각해보면 `function call (함수 호출)`이 가장 먼저 생각난다. Function call 이 발생할 때 메모리의 Stack 공간에 함수의 현재 로컬 변수의 값과 돌아갈 함수의 위치 등에 대한 정보를 저장해두고, 그 다음 동작을 수행한다. 따라서, 함수가 return 이 되면 가장 위에 있던 값이 Stack에서 빠지게 되면서 가장 마지막 순서에 가장 초반에 호출되었던 함수의 상태값들이 사용되는 구조다. ![](https://i.imgur.com/mNjSDfd.png) Queue --- #### 구현 - Queue를 구현할 때 역시 Array를 사용할 수 있는데, 물론 Linked List 를 통해서 구현할 수 있다. 구현할 때 핵심은 `head` 와 `tail` 2가지 포인터가 필요하다. head 는 Queue의 첫번째 아이템을 가리키도록 하고, tail 은 마지막 아이템을 가리킨다. - **Init**: x - **Insert**: tail을 하나 증가시키고, tail이 가리키는 곳에서 데이터를 삽입한다. - **Delete**: head가 가리키는 곳을 하나 증가시킨다. - **IsEmpty**: tail == head 면 Empty라고 판단한다 - **IsFull**: tail이 Array의 크기와 같아지면 Full 이라고 판단한다 #### 원형 큐 (Circular Queue) - Array 로 구현할 때 확장해서 생각해야되는 것이 있다. Array 는 분명히 제한된 공간이기 때문에 삭제를 데이터를 삭제하고, 추가하는 과정에서 버리는 공간이 있지 않을까 생각이 든다. 이러한 문제를 해결하기 위해서 Circular Queue 라는 것을 사용한다. - Circular Queue 를 사용하면 발생하는 문제가 하나가 있다. 아까는 head의 초기값을 -1로 했는데, 이제 이 조건을 쓰기 어렵다. 왜냐하면 데이터를 삽입하고 삭제하다보면 head의 초기값이 -1이 아닌 경우가 발생하기 때문이다. 또한 IsFull 의 로직을 업데이트 해야하는데, IsEmpty와 동일한 로직으로 처리하게 되는 경우 문제가 발생한다. - 이 문제를 해결하기 위해서 원형 큐를 사용할 때는, N 크기의 Array에서 N-1개만 사용하는 방법을 사용한다. - **Init**: head = -1, tail = 0 을 가리킨다 - **Insert**: tail이 가리키는 곳에서 데이터를 삽입하고 tail을 하나 증가시킨다 - **Delete**: head가 가리키는 곳을 하나 증가시킨다. - **IsEmpty**: tail == head 면 Empty라고 판단한다 - **IsFull**: (tail+1)%size == head 면 Full이라고 판단한다 [N-1 크기의 Circular Queue](http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/8-List/array-queue2.html) ![](https://i.imgur.com/B97qDRy.png) Stack vs Queue --- - Stack으로 Queue를 구현하는 방법 - Queue로 Stack을 구현하는 방법 - Stack 이 사용되는 사례와 Queue 가 사용되는 사례 비교