[자료구조]큐 와 스택의 실제 사용예를 알고싶습니다!!


안녕하세요!! 이번에 개인적으로 알고리즘 및 자료구조를 스터디를 통해 공부 중인데

list의 경우, 단일 연결리스트(singly linked list), 이중 연결리스트(double linked list)등등

같은 list임에도 다르게 구현된 이유에 대해서는 확 와닿는데요~

막상 큐, 스택파트에서는 교제에 실제 예제가 상대적으로 적어서 잘 모르겠더라고요.

  1. 실제로 스택이 일반적으로 구현되어 사용되는 부분이 있나요?? 스터디원끼리 짜내고 짜낸 결론?은 "계산기"를 스택을 이용해 우선순위 연산자 같은것을 구현 할 수 있다~ 정도인데요~ 다른 예제도 알고 싶습니다.

  2. 또한, 큐는 priority queue는 정렬이나 힙을 구현할때 사용하는 예를 본적이 있는데 일반적인 queue, circular queue, deque등등을 사용하는 실제 사례가 혹시 있는지 궁금해서 질문합니다!

  3. 우선 순위큐(priority queue)의 예제로 "os에서의 스케쥴링"을 생각해 봤는데요~ 물론 실제로 큐를 사용하지 않을것 같지만, 우선순위큐의 "개념"을 사용하는 예제로 "스케쥴링"이 될 수 있다~ 라고 결론을 내려도 문제는 없는 것일까요???

  • 2016년 05월 04일에 작성됨

  • 예를 들어 일정 간격으로 들어오는 펄스의 평균값을 연산하고자 할때 Queue를 사용하면 정확하게 딱 맞지요~ Stack의경우에는 워낙 많지만, ctrl+z기능이 들어간곳은 기본적으로 Stack이겠죠?    오유석   2016.5.4 18:49     
조회수 1922


1 답변


좋아요
3
싫어요
채택취소하기

큐와 스택은 가장 많이 사용되는 자료구조입니다.

구현은 연산의 성능을 고려하기 때문에 다양한 방법이 고안된 것으로 생각하면됩니다.

개념적으로 큐는 선입선출(먼저 등록된 것을 먼저 사용하는 경우)의 특징을 가지고, 스택은 선입후출 혹은 후입선출(마지막에 등로된 것을 먼저 사용하는 경우)의 특징을 가집니다.

어떤 문제를 해결하고자 할 때, 위의 특성 중 어디에 해당하는 지에 따라서 큐로 할지 스택으로 할지 고려하면 됩니다.

당장은 알고리즘을 배울 때에 많이 사용하게 될 겁니다. 특히 특정 자료의 탐색 순서를 결정해야 하는 많이 다루게 됩니다. 예를 들어 문제를 해결해가는 과정에서 분기점을 만났을 때(예: 미로에서 갈림길을 만났을 때), 각각의 분기를 순서대로 해결할 건지(너비우선탐색-BFS - 큐), 한 분기를 먼저 다 해결하고 다음 분기를 해결한 건지(깊이우선탐색-DFS - 스택)에 따라 사용하는 자료구조가 다릅니다.

기타 현실적인 문제에서 위에서 설명한 개념에 해당하는 상황을 만난다면, 자료구조는 통상 큐와 스택중에 하나를 선택하게 될 겁니다. 어디까지나, 자료를 저장하고 꺼내는 방법의 하나일 뿐입니다. 다시 말해서 큐나 스택은 망치나 스크류드라이버 정도로 생각하시면 됩니다.

  • 첫 번째, 자료를 탐색하는 방법에서 많이 사용합니다. 앞으로 Tree나 Graph 자료구조를 배우게 될 텐데, 이들 자료구조는 큐와 스택을 모르면 이해도 어렵고 구현하기도 쉽지 않습니다. 즉, 큐와 스택을 써야지하고 쓴다기 보다는 순서를 고려해야 상황이거나 우선적으로 선택해야 하는 상황에서 많이 사용합니다. (어떤 것을 선택하고, 어떤 것을 버려야 하는 문제가 아니라, 어떤 것을 먼저 선택할 것인냐의 문제에서는 대부분의 경우에 사용하게 되겠습니다.)
  • 두 번째, 우선순위큐는 조금 특별한 문제를 풀기위한 것으로 선입선출 개념에서 약간 변형을 한것으로 나중에 들어왔지만, 먼저 처리해야 하는 자료가 발생할 경우에 필요로 합니다. 이러한 판단은 어떤 상황을 회피하거나, 우선 순위를 두어야 하는 상황에서 사용합니다.
    • 환형큐는 배열이라는 특성(혹은 제한된 메모리 사용)에 맞게 고안된 것입니다. (구현 및 성능을 고려해야 할 것입니다.)
    • 덱(deque)는 조금 특이한 경우인 데, 큐와 스택을 합친 것으로 생각하면 될 것 같네요. 양쪽 끝에서 삽입/삭제가 가능한 자료구조로 선입선출/후입선출의 복합적인 성격이 필요한 경우에 사용하겠습니다.
  • 세 번째, 사용할 수 있습니다. 우선 순위라는 것을 계산하는 방법이 더 큰 이슈가 되겠지만, 사용가능합니다.

마지막으로 자료구조 시간에 배우는 것은 프로그램을 개발하기 위한 연장도구에 대해서 이해하는 것입니다. 우리가 사용하는 망치, 스패너, 장도리, 일자 스크류 드라이버, 십자 스크류 드라이버 등 다 쓰임새가 있고 사용하는 방법이 있는데, 자료구조는 프로그래밍에 필요한 연장들을 배우는 것입니다.

전통적으로 해결하는 방법이 정립된 것(알고리즘)에서는 통상 사용하는 자료구조가 있는 데, 구현의 관점이 아니라, 문제 해결이라는 관점에서 요구되는 자료 처리 특성을 이해하면 어떤 자료구조는 쓰는게 좋을지 판단이 설겁니다.

배운 연장을 어떻게 쓸지는 상황에 따라 판단해야 합니다. 남들이 말하는 방법대로 사용하지 않아도(예를 들어 스패너로 망치질을 한다거나...) 문제를 해결할 수는 있습니다. 이렇게 사용하는 것이 "맞느냐? 틀리느냐?"라는 질문보다 "그러한 선택이 최선이었는가?"에 대한 고민을 거듭하는 것이 더 발전적입니다.

답변이 좀 길어졌습니다.

  • 2016년 05월 04일에 수정됨
    리눅스(유닉스) 기반의 시스템에서 웹 서비스를 개발하고 있습니다.
  • 2016년 05월 04일에 작성됨
    리눅스(유닉스) 기반의 시스템에서 웹 서비스를 개발하고 있습니다.

로그인이 필요한 기능입니다.

Hashcode는 개발자들을 위한 무료 QnA사이트 입니다. 작성한 답변에 다른 개발자들이 댓글을 작성하거나 좋아요/싫어요를 할 수 있기 때문에 계정을 필요로 합니다.
► 로그인
► 계정만들기
Close