[APSS] 19. 큐와 스택, 데크

jiho·2020년 1월 2일

APSS

목록 보기

5/6

학부시절에 매우 귀찮았고 공부하기 싫었던 자료구조들 알지만 자세히 알지는 못했던 내용들을 정리하고 즐기고(?)있습니다.
이전에는 왜 그 내용을 안좋아했을까요? 필요성을 못느꼈기때문입니다. 왜 사용해야하는지 몰랐기 때문이었던 것 같습니다. 취준생이 되서야 배우는 재미를 느끼기 시작했네요.

이번에는 큐와 스택, 데크에 대해서 한번 알아보겠습니다.
그 전에 자료구조를 왜 만들었을지에 대해 이야기해보죠.
컴퓨터로 표현할 수 있는 모든 자료는 변수로 표현할 수 있으니 변수만 있어도 되는데, 왜 이런 저런 용어들을 만들고 구조를 만들까요? 그렇게해서 무엇을 얻을 수 있을 까요?

이 질문에 대한 답은 크게 두 가지로 나눌 수 있습니다. 추상화와 최적화입니다.
사실 (거의) 모든 자료구조는 이 두가지 목적을 이루기 위해 고안된 것입니다.

추상화

현실세계에서 사용하는 개념이나 언어들은 컴퓨터로 작성하기에 모호하고 많은 정보를 담고 있기 때문에 추상화된 자료구조는 개념에서 중요한 뼈대만 뽑아내고 이름을 붙이고 명확한 정의들을 곁들여 사람들이 쉽게 사용할 수 있도록합니다.
즉, 사람들의 이해와 의사소통을 위해 자료구조들이 사용된다는 것입니다.

최적화

자료구조를 설계하는 다른 목적인 최적화는 프로그램의 동작 속도를 빠르게 하기 위한 것입니다. 자료구조의 종류마다 사용처가 다양하고 장단점이 존재하기 때문에 확실하게 이해할 필요가 있습니다.

큐와 스택, 데크

이들은 일렬로 늘어선 자료들(sequence)을 표현하는 자료구조로, 여기에 자료를 넣고꺼내는 연산을 지원합니다. 이와 같은 연산들은 모두 배열이나, 연결 리스트를 이용하면 쉽게 구현할 수 있는 것들 입니다. 그럼에도 큐와 스택, 데크가 중요한 이유는 흔히 사용하게 되는 자료 구조의 형태에 이름을 붙였다는 데 있습니다. 따라서 개발자간의 의사소통이 더 쉬워지고, 더 큰 그림을 보며 프로그램을 설계할 수 있습니다.

큐(Queue)

한쪽 끝에서 자료를 넣고 반대쪽 끝에서 자료를 꺼낼 수 있습니다. 이러한 속성에 따라 가장 먼저들어간 자료를 가장 먼저 꺼내게되지요. 이 속성을 선입선출(FIFO, First In First Out)이라고 합니다. 큐는 일상 생활과 아주 밀접해 있습니다. 놀이공원이나 음식점에서 선 줄, 한 일의 목록등을 큐로 표현할 수 있습니다.
CS에서 큐의 대표적인 예로 Process 스케쥴링이 있습니다.
큐의 단점 또한 존재합니다. 순서가 확실하게 정해져있기 때문에 만약 하나의 프로세스 처리가 길어진다면 병목현상이 발생할 가능성도 존재하는 것입니다.

(사용사례 더 정리하기)

스택(Stack)

스택은 한쪽 끝에서만 자료를 넣고 뺄 수 있습니다. 따라서 가장 늦게 들어간 자료를 가장 먼저 꺼내게 되며, 이 속성은 후입선출(LIFO)이라고도 부릅니다. 스택은 전산학 전에 걸쳐 널리 사용됩니다.함수 호출이 끝나고 이전 함수로 돌아갈 때, 이 함수 바로 이전의 함수로 돌아가야하지요. 때문에 컴퓨터는 내부적으로 스택을 사용해 함수들의 문맥(context)를 관리합니다.

덱(dequeue)

덱는 양쪽 끝에서 자료들을 넣고 뺄 수 있는 자료구조를 말합니다. 따라서 데크를 이용하면 스택과 큐 모두를 구현할 수 있지요.

자료구조에서 자료를 넣는 작업을 푸시(push)그리고 자료를 꺼내는 작업을 팝(pop)이라고 합니다. 이들 연산은 모두 상수시간, 즉 O(1)에 이루어져야합니다.

큐, 스택, 데크의 구현

연결리스트를 통한 구현

연결 리스트를 사용해서 구현하는 것은 매우 간단합니다. 연결 리스트를 이용하면 양쪽 끝에서의 추가와 삭제를 모두 상수 시간에 할 수 있기 때문에, 모든 연산이 상수 시간이어야한다는 요구조건을 쉽게 충족 시킬 수 있습니다. 물론 이 경우 노드의 할당과 삭제 그리고 포인터를 따라가는데 시간이 걸리기 때문에 연결 리스트가 가장 효율적인 구현은 아닙니다.