Queue, Stack

우리가 생활함에 있어서 어떤 작업이나 요청들을 처리할때 가장 쉽게 어떤 순서로 처리할까?

예를 들어, 내가 어떤 가게의 종업원이 되었다고 생각해보자. 요리를 하시는 사장님께 주문이 들어왔음을

알리는 순서를 어떤 식으로 구성할까? 일반적으로는 그냥 들어오는 순서대로이다. Queue가 해당 방식으로 구현된다. 

그렇다면 쉬운 또 다른 방식은 어떤 것이 있을까?

예를 들어, 내가 어떤 가게의 종업원이 되었다고 생각해보자. 사장님께서 요리 재료를 들고 들어오시면서

냉장고에 넣으라고 박스단위로 쌓아놓으셨다. 그럴땐 어떤 박스부터 냉장고에 넣을까? 보통은 맨위의

박스부터 냉장고에 넣는다. 그럼 맨위에 쌓인 박스는 사장님께서 제일 처음 가져온 박스일까? 아니다.

가장 마지막에 가져온 박스일 것이다. 이 경우, 가장 최근에 들어온 원소 먼저 처리하는 Stack이 해당 방식에

속한다. 

Stack과 Queue는 완전히 다른 방식으로 구조화되고 구축된다. 스택은 한 쪽 방면으로만 요소를 추가하고 제거

하는 반면 큐는 양쪽 방면을 모두 써서 요소를 추가하고 제거한다.

 

Queue에 대해서 자세히 알아보자.

큐 구조에서의 용어를 알아보자. 큐에 요소를 추가하는 것의 과정은 enqueuing 이라고 하고 반대로

제거하는 과정은 dequeuing 이라고 한다. 이 과정이 일어나는 방향이 중요한데 큐의 처음인 front에선

dequeuing이 일어난다. 제일 처음들어온 요소를 처리해야하기 때문이다. 큐의 마지막인 back부분에선

enqueuing이 일어난다. 마치 맛집에 들어가기 위해 줄을 설때 맨뒤에 서는 것과 같다.

즉, 큐는 선입선출(FIFO) 구조를 가진다.

 

Stack에 대해서 자세히 알아보자.

스택 구조에서의 용어를 알아보자. 스택에 요소를 추가하는 과정은 push라고 하고 반대로 제거하는 과정

은 pop이라고 한다. 이 과정이 일어나는 방향은 둘다 같은 방향에서 일어난다. top이라고 하는 제일 위의

방향에서 push, pop이 일어나는데 마치 박스를 쌓는 과정과 유사하다. 박스를 쌓기 위해선 맨 위에 다음

박스를 올리고 내릴 때도 맨 위의 박스를 내린다.

즉, 스택은 후입선출(LIFO) 구조를 가진다.

 

Queue와 Stack이 주로 같이 이야기 되는 경향이 뭘까?

그 이유는 두 추상 자료형를 구성하기 위해 유사한 함수를 작성하기 때문이다. 

아까 큐의 enqueue, dequeue / 스택의 push, pop에 대해서 말했는데 이것들은 많은 기능이 동일하다.

1. 스택의 push는 큐의 enqueue와 유사하다.

2. 스택의 pop은 큐의 dequeue와 유사하다.

3. size 및 isEmpty 라는 기능이 두 자료구조에서 정말 유용하다.

두 추상 자료형이 얽혀 있는 것처럼 보이는 또 다른 이유는 둘 다 array 나 linked list로 구현될 수 있다.

size 및 isEmpty라는 기능은 배열과 같이 정적 할당 구조에서 유용하다. size가 필요한 이유는 내가 할당한

범위를 벗어나 요소를 더 추가하려할 때, 유용할 것이고 isEmpty는 더이상 요소가 없는데 요소를 제거하려

할 때 유용할 것이다. 내가 할당한 메모리 공간이 더 이상 없는데 더 추가하려할 때 스택 오버플로가 발생한다.

linked list를 이용하여 스택을 설계하는 것이 좋은 이유는 둘 다 똑같이 한 방향으로 커지기 때문에 그렇다.

단일 링크드 리스트가 잘 어울릴 것이다.

array와 linked list를 사용하는 경우를 비교해보자. 배열을 이용하는 경우 큐에 넣어야 하는 경우에 생각해보면

enqueue를 계속하다 할당된 메모리 크기를 넘어가면 요소를 복사하고 다시 메모리를 더 크게 할당해서 이용해야한다.

dequeue를 생각해보면 반대로 맨 처음 요소를 삭제를 하고 그 다음 요소들을 제일 처음으로 끌어와서 이동을 시켜야한다.

시간, 공간 복잡성이 증가할 것이다. 

하지만 linked list를 이용하면 어떨까? 메모리가 분산될 수 있고 동적으로 증가할 수 있으니까 크기를 신경쓸 필요는 없어진다. 그리고 마찬가지로 참조 포인터만 수정을 하면 되니까 빼내는 것도 굉장히 쉬워진다. 배열을 사용했을땐

제거하는 경우 시간이 배열의 크기에 따라 달라졌었다. 하지만 지금은 크기에 상관없이 똑같은 시간 복잡도가 요구될 것이다. 

몰론 스택, 큐 둘다 배열, 링크드 리스트로 구현 가능하다. 하지만 두 가지 구현 간의 차이점과 어느 것이 더 나은지를

생각하는 것이 중요하다.

 

Queue, Stack이 중요한 이유

이 두 가지 추상 자료형이 중요한 이유는 실생활에서 굉장이 많이 사용하는 간단하면서도 효율적인 구조이기 때문이다.

 

추상 자료형 VS 자료 구조

추상 자료형 (Abstract Data Type)은 기능의 구현 부분을 나타내지 않고, 데이터의 형태와 그 연산들을 정의한 것이다.

예를 들어, 스택이나 큐에서 pop, push, size, isEmpty / dequeue, enqueue, size, isEmpty 와 같이 연산을 정의하지만 내부

데이터가 저장되는 것은 배열, 링크드 리스트 등 다양하게 구현 할 수 있기때문에 추상 자료형이다.

자료구자 (Data Structure)은 추상 자료형이 정의한 연산들을 구현한 구현체를 가리킨다.

즉, 추상 자료형은 구현 방법을 명시하고 있지 않다는 점에서 자료구조와는 다르다.

 

참조  - 해당 링크에서 더 자세한 내용을 배울 수 있습니다.

- https://medium.com/basecs/stacks-and-overflows-dbcf7854dc67

Stacks and Overflows

- https://medium.com/basecs/to-queue-or-not-to-queue-2653bcde5b04

To Queue Or Not To Queue

- https://gbsb.tistory.com/306#:~:text=%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%99%80%20%EC%B6%94%EC%83%81%20%EC%9E%90%EB%A3%8C%ED%98%95&text=%EC%B6%94%EC%83%81%20%EC%9E%90%EB%A3%8C%ED%98%95%EC%9D%80%20%EA%B8%B0%EB%8A%A5%EC%9D%98,%EA%B5%AC%ED%98%84%ED%95%9C%20%EA%B5%AC%ED%98%84%EC%B2%B4%EB%A5%BC%20%EA%B0%80%EB%A6%AC%ED%82%A8%EB%8B%A4.

자료구조(Data Structure)와 추상 자료형(ADT)