자바로 배우는 핵심 자료구조와 알고리즘 - 3. 스택과 큐는 왜 배울까?

오늘은 가장 단순한 자료구조인 스택(Stack)과 큐(Queue)에 대해서 알아보도록 하겠습니다.

사실 내용은 다들 아시죠? 아주 간단합니다.

• 스택은 LIFO(후입선출)인 자료구조이다
• 큐는 FIFO(선입선출)인 자료구조이다

그런데 이런 생각안해보셨나요? 도대체 아무것도 아닌 이 자료구조를 왜 배워야 하지? 사실 프로젝트에서는 거의 만들어볼 일이 없는데 말이죠.

사실 책에서도 유사한 내용을 언급하고 있고 다음의 클래스를 활용해서 리스트, 맵 관련 클래스의 성능을 측정하고 가시화합니다.

리스트의 성능 측정 (ProfileListAdd 클래스)
: https://github.com/yudong80/ThinkDataStructures/blob/master/solutions/src/com/allendowney/thinkdast/ProfileListAdd.java

맵의 성능 측정(ProfileMapPut 클래스)
: https://github.com/yudong80/ThinkDataStructures/blob/master/solutions/src/com/allendowney/thinkdast/ProfileMapPut.java

책을 보시면 다음 메서드들을 실행해보세요..
(ProfileListAdd 클래스)
//profileArrayListAddEnd();
//profileArrayListAddBeginning();
//profileLinkedListAddBeginning();
//profileLinkedListAddEnd();

(ProfileMapPut 클래스)
//profileHashMapPut();
//profileMyHashMapPut();
//profileMyFixedHashMapPut();

다시 원래의 물음으로 돌아가봅니다.
우리가 왜 배워야 하는지 말이죠.
제 생각은 다음과 같습니다.

1. 스택

스택의 의미는 (쌓아놓은 더미)입니다. 위로 쌓아놓게 되면 아래에 있는 것은 가져오기가 어렵죠? 바로 이런 매타포로 생각하시면 됩니다.

우리가 스택을 배워야 하는 이유는 프로그래밍 세계 곳곳에서 사용되기 때문입니다. 단어의 의미를 알아야 왜 쓰이는지도 생각할 수도 있습니다.

프로그래머에게 비근한 예는 콜스택(call stack)입니다.

특히 예외처리를 할 때 e.printStackTrace() 메서드를 호출하면 다음과 같은 내용이 출력됩니다.

(인터넷에서 발췌한 콜스택입니다)

java.lang.ArithmeticException: / by zero

  at Main.main(Main.java:10)
  at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
  at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
  at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
  at java.lang.reflect.Method.invoke(Method.java:498)
  at com.intellij.rt.execution.application.AppMain.main(AppMain.java:147)

이것을 보고 어디서 문제가 있었는지 조사하고 잘못된 부분을 고치게 됩니다.

프로그램의 호출구조가 스택을 가지지 않으면 안되기 때문이죠. main() 메서드에서 시작된 프로그램은 수많은 객체의 인스턴스의 메서드를 타고 가면서 목적한 결과를 만들어내는 것입니다. 특히 재귀적인 호출이 스택의 대표적인 예입니다.

2. 큐

큐는 좀더 심오합니다. 단순히 처음에 들어가는 것이 처음에 나오는 터널이 아니라 (대기행렬)이라고 생각하면 왜 배워야 하는지 이유를 알 수 있습니다.

대기행렬?

간단하게는 온라인 쇼핑몰에서 물건을 구매하려는 사람과 그 서비스를 제공하는 서버(server)의 관계로 볼 수 있습니다.

간단히 수요(demand)와 공급(supply)로 표현해보겠습니다.

demand < supply 이면 아무런 문제가 없습니다. 그리고 demand = supply 여도 (단순화된 상황에서는) 큰 문제가 없습니다.

그런데 demand > supply 인 경우에는 생각해볼 문제가 많습니다. 누구를 먼저 서빙해야 하지? 혹시 수요가 폭주해서
서버가 처리하지 못하면 그것을 기다려야 할지? 아니면 못판다고 튕겨내야 할지 말이죠. 몇명이나 기다리게 할지? 아니면 몇초까지 기다리게 할지 말이죠. 후자는 timeout(expired) 이라고 표기합니다.

대기행렬에 대한 문제는 우리가 매일 사용하는 운영체제(OS)에서도 매우 중요하게 다뤄집니다.

아무리 PC가 버벅거려도 윈도우 OS에서는 ctrl + alt + del 명령은 무조건 동작합니다. 왜 그럴까요? OS 내부에서 일종의 (우선순위)를 갖는 큐 처리를 했기 때문입니다.

빅데이터를 다루거나 게임, 쇼핑몰과 같은 수많은 백엔드 솔루션에서도 큐의 문제는 매우 중요한 문제입니다. 서버의 성능과 서비스 품질을 좌우하기 때문이죠.

3. 결론

제가 길게 설명드렸지만 결국 스택과 큐는 이미 우리 주변에 존재하고 있습니다. 이러한 자료구조를 단지 라이브러리의 클래스로만 생각해서는 안된다는 것이죠.

잘 배워두고 주변에서 어떻게 쓰이는지 알고 있는 것이 프로그래머의 기본기 향상에 큰 도움이 된다는 말씀을 드리고 싶었습니다.

그외에 리스트, 트리, 맵, 그래프 등에 대해서 기본 개념은 잘 알고 있어야 문제에 대한 응용력이 향상됩니다. AI같은 최신 기술을 알고 있다고 기술자로서의 깊이가 깊어지는 것은 아니죠.

오늘은 여기까지입니다.
감사합니다.

2018.6.6

yes24 책링크: http://www.yes24.com/24/Goods/61198657?Acode=101

#kr #kr-dev #java #busy #jjangjjangman