자료구조: 큐와 스택

컴퓨터 과학에는 다양한 자료구조가 있다.  

자료구조의 사전적 정의는 다음과 같다.

 

"자료구조(資料構造, 영어: data structure)는 컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미한다." 

 

역시 너무 어렵다.

사전이나 전문지식 관련 책들은 쉬운 것도 어렵게 설명하는 것처럼 느껴진다. 아마 추상적인 개념을 최대한 짧고 명확하게 표현하다 보니 어려운 단어와 문법을 많이 사용할 수 밖에 없는 걸까?   

 

나도 완벽히 이해 했다고 하긴 어렵지만 내 머릿속 개념은 이렇다.

컴퓨터에 무언가를 입력하면 그것은 메모리 위에 올라가 저장된다. 그리고 언젠가 그 입력한 데이터를 찾아서 쓸 경우가 있을 것이다. 그때 어떻게 데이터를 찾아서 쓸 것인지에 대한 방법과 규칙이 자료구조의 기본적인 의미라고 생각한다.  

 

이제 대표적인 자료구조인 큐와 스택에 관해서 이야기 해보려고 한다.  

데이터가 쌓이고 꺼내지는 과정을 우리의 실생활에 비유해 보겠다. 

큐는 '사람'줄을 서는것에 비유할 수 있다. 어딘가에 줄을 서면 가장 먼저와서 서있던 사람이 제일 먼저 입장하거나 무언가를 받는다. 그럼 자연스레 내 차례가 한칸한칸 앞당겨지고 나의 순서가 된다.

즉 먼저 온 사람이 먼저 나가는, 사람의 입장에서 지극히 상식적인 구조다.  

큐 자료구조에서는 새로운 사람이 오는(새로운 입력 데이터가 쌓이는)것을 인큐(enqueue)라고 부르고 한개 꺼내는 동작을 디큐(Dequeue)라고 부른다.   

 

스택의 구조는 '물건' 이 쌓이는 구조와 비슷하다. 편의점 냉장고에 매일 우유를 한개씩 넣을 때, 우유가 쌓인다면 제일 깊은 곳에 있는 우유가 제일 오래된 우유일 것이다. 

우유는 사람과 달리, 냉장고 속에 있을 때, 먼저 왔다는 이유로 선택받지 않는다. 오히려 오래된 우유일수록 외면받는다. 

스택의 경우는 뭔가 하나 들어오는 것을 푸시(push), 빠져나가는 것을 팝(pop)이라고 부른다. 

 

이렇게 큐와 스택을 사람과 물건에 비교해 보았다. 

컴퓨터의 데이터가 이렇게 두가지 방식으로 처리된다면, 분명 장단점이 있을 것이다. 

과학적으로 분석하기 전에, 뭐가 더 괜찮고 끌리는지 생각해보면, 나는 큐가 더 끌렸다. 왠지 모르게 공평해 보이고 편리해 보이는 그런 이미지가 느껴진다. 

하지만 효율성 면에서만 본다면 큐의 완패다. 큐에 12345를 집어넣고 5를 쓰려면 1이나오고 2가 1의자리로 움직이고 3이 2의자리로 움직이고 4가 3의자리로 움직이는 식으로 하나의 데이터를 얻기위해 모든 데이터가 불필요한 데이터의 움직이게 된다. 버스를 기다릴때, 앞사람이 앞으로 갈수록 나도 계속 움직여야하는것과 똑같다. 

 

반면에 스택은, 데이터가 쓰이는 동안 제일 오래된 데이터는 아무것도 안하고 편하게 쉴 수 있다. 큐처럼 한번 쓸 대마다 한칸씩 계속 움직일 번거로움이 없다.    

나도 설명하다 보니 너무 어렵게 적은 것 같다. 하지만 이제 막 시작한 블로그이니 배움을 얻기위해 이곳에 도달하는 모든 사람들을 위해서 더욱 더 쉽게 설명하기 위해서 열심히 노력하겠습니다.