자료구조 - 스택(Stack), 큐(Queue), 덱(Deque)
스택(Stack)
- 스택이란 ?
스택(Stack)은 순서대로 쌓여진 데이터를 의미힙나다.
스택은 한 쪽으로만 데이터의 입·출력이 동작하는 자료구조입니다.
기본적으로 FILO(First In Last Out)의 동작방식을 가지며 이는 말 그대로 먼저 들어간 요소가 가장 마지막에 꺼내진다는 것입니다.
메모리에서 함수 호출 시 변수, 리턴값 등의 데이터를 저장하는 공간입니다.
데이터를 넣는 것은 push(), 빼는 것은 pop()이라고 합니다.
- 스택의 구조
스택에 먼저 저장하는 데이터는 스택의 가장 아래쪽(높은 주솟값)부터 쌓이고 나중에 저장되는 데이터는 그 위로 쌓입니다.
스택의 동작방식을 그림으로 나타내보겠습니다.
기본적으로 스택의 구조는 이런식으로 생겼습니다.
다음은 스택에 A, B, C를 넣고 다시 빼는 과정을 나타냅니다.
위처럼 A와 B와 C를 넣었을 때, 먼저 넣은 요소가 아래에 있고 후에 넣은 요소들이 위로 쌓이는 것을 알 수 있습니다.
다음은 pop()의 동작과정입니다. A, B, C가 순서대로 스택에 들어있을 때, pop()을 실행하면 먼저 C가 나오고 그 다음 pop()을 실행하면 B가 나옵니다. 마지막으로 pop()을 실행하면 A가 나오고 스택은 다시 비어있는 상태로 돌아가게 됩니다.
이미지 출처 : https://cwjuns.tistory.com/18
- 스택의 사용
스택은 메모리의 스택 영역에서 함수의 변수데이터 저장 및 실행결과 저장 등에 사용됩니다.
큐(Queue)
- 큐란 ?
큐(Queue)는 FIFO(First In First Out)의 동작방식을 갖는 자료구조입니다.
예를 들어, 음식점을 갔는데 웨이팅이 있다고 가정한다면 먼저 온 사람이 1번, 그 다음이 2번, ··· 의 순으로 대기번호를 받게 됩니다. 그리고 실제로 식당에 입장할 땐 1번부터 순서대로 입장하게 됩니다. 이와 같이 동작하는 자료구조가 큐입니다.
스택(Stack)은 한 쪽에서만 입·출력이 일어나는 자료구조라고 하였습니다. 그렇다면 큐는 어떤 식으로 입·출력이 일어날까요? 정답은 한 쪽 끝에서는 입력만, 한 쪽 끝에서는 출력만 일어나는 자료구조입니다.
입력과 출력은 앞으로 push()와 pop()이라고 말하도록 하겠습니다.
- 큐의 구조
큐의 구조는 위에 언급한 것처럼 줄을 서는 대기열과 같습니다. 따라서 1자로 이루어진 배열의 형태를 띱니다.
연속적인 데이터를 표현하기 위해 가장 흔하게 배열을 많이 사용하지만, 인덱스간의 참조가 자주 발생하고 중간의 삽입, 또는 삭제가 빈번하게 일어난다면 링크드리스트(Linked List)를 사용하여 구현하기도 합니다.
다음은 큐를 나타낸 그림입니다.
큐에는 Front와 Rear라는 포인터가 존재합니다. Front는 큐의 가장 앞 부분을 가르키는 포인터이고 Rear는 큐의 가장 뒷 부분을 가르키는 포인터입니다. 큐에서 pop()을 실행하게 되면 front가 가르키고 있는 주소의 값을 꺼내게 되고, push()를 실행한다면 Rear가 가르키는 부분에 새로 넣는 요소를 연결하고 Rear는 새로 넣은 요소를 가르키게 됩니다.
- 큐의 사용
큐는 많은 부분에서 사용되는 개념입니다. 위에서 언급한 것처럼 실생활에선 줄서서 기다리는것, 업무가 주어질 때 먼저 주어진 업무를 처리하는 것, 등등 에서 이용됩니다.
또한, 컴퓨터에서 가장 중요한 부분인 운영체제에서 프로세스가 실행, 대기, 블록의 상태로 변화할 때 프로세스의 실행 순서를 지정하는 것에도 큐를 사용하게 됩니다. (ReadyQueue, BlockedQueue 등)
- 추가개념
위에서 큐는 일을 처리할 때 먼저 주어진 업무를 먼저 처리하는 식으로 동작한다고 하였습니다.
만약 중요도가 10%인 업무가 주어지고 이후에 중요도가 80%인 업무가 주어질 때, 큐의 동작방식을 따른다면 어떻게 될까요?
당연히 중요도가 10%인 업무를 먼저 처리하게 될 것입니다. 컴퓨터의 연산에서분만 아니라 현실에서도 이 방법은 별로 효율적이지 않습니다. 중요도가 높은 업무를 먼저 처리하는 것이 현명하겠죠.
이러한 방법을 구현하기 위해 우선순위 큐(Priority Queue)라는 개념이 사용됩니다.
우선순위 큐는 힙(Heap)이라는 자료구조에 대해 이해해야 하므로 다른 포스팅에서 다루도록 하겠습니다.
에서 다루었습니다.
덱(Deque)
- 덱이란?
덱(Deque)은 양방향 큐(Double-ended Queue)입니다. 쉽게 말하면 양쪽 끝에서 입력과 출력이 모두 일어날 수 있는 자료구조인데 이는 스택과 큐를 조합하여 구현할 수 있습니다.
- 덱의 구조
덱의 기본적인 구조는 Front와 Rear를 갖고 있다는 점에서 queue와 비슷합니다.
다만, pushFront()와 pushBack, popFront()와 popBack()의 4가지 동작함수가 있다는 점에서 큐와 차이가 있습니다.
왼쪽에서 push()가 일어나게 되면 front의 prev 포인터에 입력된 값을 연결해주고 front가 새로 집어넣은 요소를 가르키게 합니다.
오른쪽에서 push()가 일어나게 되면 rear의 next 포인터에 입력된 값을 연결해주고 rear가 새로 집어넣은 요소를 가르키게 합니다.
왼쪽에서 pop()이 일어나게 되면 front가 가르키는 주소의 값을 리턴하고 front는 front의 next를 가르키게 됩니다.
오른쪽에서 pop()이 일어나게 되면 rear가 가르키는 주소의 값을 리턴하고 rear는 rear의 prev를 가르키게 됩니다.
- 추가개념
덱은 구현이 어렵기 때문에 자주 사용되는 자료구조는 아닙니다.
덱은 데이터의 삽입과 삭제를 효율적으로 수행할 수 있기 때문에 데이터가 가변적일 경우 주로 사용됩니다.
- 참고
https://velog.io/@hanif/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EB%8D%B1