[Data structure] 자료구조 - stack, queue

자료구조의 가장 기본이 되는 stack ( 스택 ) 과 queue ( 큐 ) 는 자료구조의 처음을 장식한다. 그런데 정작 사용할 때에는 어떻게 해야할 지 막막한 게 초보자의 마음이리라. 자료구조는 구현과는 제법 거리가 있다. 스택과 큐는 그냥 배열로 선언해서 사용해도 무방하다. 이처럼 자료구조는 어떤 방식으로 데이터를 관리할 지 그 구조에 대해 설명하는 것이지, 어떤 방식으로 구현해야만 한다는 건 아니다. 따라서 앞으로 정리하게 될 모든 자료구조도 개념에 대해 이해하는 게 우선이라는 점을 기억하자. 또, 자료구조는 알고리즘과 뗄 수 없는 관계이기때문에 아주아주 중요한 개념이라는 것 정도는 알고 있자.

 

Stack ( 스택 )

스택은 동전쌓기처럼 가장 나중에 쌓은 동전을 가장 먼저 꺼낼 수 있는 구조이다.

위의 그림처럼 하나의 요소를 차곡차곡 쌓는 구조를 스택이라고 한다. 쌓여있기때문에 아래에서 뽑으려면 무너질거다. 어릴 때 장롱에 쌓여있는 이불 중에 좋아하는 이불을 꺼내려다가 이불을 쏟아 엉망으로 만들고 엄마한테 혼난 경험이 있다면 이해하기 쉽다. 이 나이 먹고 중간에 있는 이불을 꺼내다가 엄마에게 혼나면 부끄러우니까, 아예 중간에서 뽑을 수 없도록 만든 게 스택이다. 그리고 이불을 위에다 쌓는 과정을 push ( 푸쉬 ), 위에서부터 하나씩 꺼내는 과정을 pop ( 팝 ) 이라고 한다.

 

 

Queue ( 큐 )

큐는 식당에서 먼저 주문한 손님의 음식을 먼저 서빙하게 하는 것이다. 혹시 식당에서 서빙 알바 해본 적 있는가? 두 명의 손님이 시간차를 두고 식당에 자리를 잡았지만, 나중에 온 손님의 음식이 먼저 나오면 먼저 주문한 손님은 꼭 컴플레인을 건다.

 

" 제가 먼저 왔는데 왜 저기 음식이 먼저 나와요?"

 

그리고 사장님에게 가서 말하면 사장님은 주문 들어온 순서대로 만든 거라면서 오히려 주문을 받은 나를 혼낸다. 억울하고 서러워서 내가 큐를 도입했다. 무조건 먼저 주문한 손님의 주문서를 순서대로 주방에 넣는 거다. 절대 나중에 주문한 손님의 주문서가 먼저 들어갈 수 없도록 막아두고, 주문서를 주문순서대로 차례대로 집어넣는다.

이때 주문서를 넣는 과정을 enqueue ( 엔큐 ), 들어온 주문서의 순서대로 주방에서 하나씩 꺼내는 과정을 dequeue ( 디큐 ) 라고 한다.

 

 

 

이게 전부다. 간단하지만 아주 강력한 두 자료구조는 실제 코딩을 할 때에 매우 유용하고 자주 쓰인다. 개념은 꼭 이해하고 있자.