자료구조 Queue / Stack

== Queue(FIFO, First In First Out) ==

- Enqueue

def enqueue(self, item) : self.item.insert(0,item)

- Dequeue

def dequeue(self, item): self.item.pop

- Queue Example

- Print job queue

- BFS(Breadth First Search)

== Stack(LIFO, Last In First Out) ==

- Push

def push(self,item): if len(self.items) < self.max: self.items.append(item) else: print("overflow")

- Stack Overflow 

stack 메모리의 최대치를 넘어서 push 할 수 없는 경우.

-  Pop

code

def pop(self): if len(self.items) > 0: self.items.pop() else: print("underflow")

- Stack Underflow

- Stack Example

- Browser back button

- DFS(Depth First Search)

Source Code : The-G

---

- Some Question

Q. 큐와 스택의 실제 사용 예를 알고 싶습니다.

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

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

개념적으로 큐는 선입선출의 특징을 가지고, 스택은 후입선출/선입후출의 특징을 가진다.

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

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

Q1. 실제로 스택이 일반적으로 구현되어 사용되는 부분은 어디인가요?

A1. 자료를 탐색하는 방법에서 많이 사용합니다. 앞으로 Tree나 Graph 자료구조를 배우게 될 텐데, 이들 자료구조는 큐와 스택을 모르면 이해도 어렵고 구현하기도 쉽지 않습니다. 즉, 큐와 스택을 써야지하고 쓴다기 보다는 순서를 고려해야 하는 상황이거나, 우선적으로 선택해야 하는 상황에서 많이 사용합니다. (어떤 것을 선택하고, 어떤 것을 버려야 하는 문제가 아니라, 어떤 것을 먼저 선택할 것이냐의 문제에서는 대부분의 경우에 사용하게 됩니다.) 

Q2. 큐는 Priority queue는 정렬이나 힙을 구현할 때 사용하는 예를 본적이 있는데 일반적인 queue, circular queue, deque등등을 사용하는 실제 사례가 혹시 있는지 궁금합니다.

A2. 우선순위큐는 조금 특별한 문제를 풀기위한 것으로 선입선출 개념에서 약간 변형한 것으로 나중에 들어왔지만, 먼저 처리해야 하는 자료가 발생할 경우에 필요로 합니다. 이러한 판단은 어떤 상황을 회피하거나, 우선 순위를 두어야 하는 상황에서 사용합니다.

- 환형큐(circular queue)는 배열이라는 특성(혹은 제한된 메모리 사용)에 맞게 고안된 것 입니다.(구현 및 성능을 고려해야 할 것입니다.)

- 덱(deque)는 조금 특이한 경우인 데, 큐와 스택을 합친 것으로 생각하면 됩니다. 양쪽 끝에서 삽입/삭제가 가능한 자료구조로 선입선출/후입선출의 복합적인 성격이 필요한 경우에 사용합니다.

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

A3. 사용할 수 있습니다. 우선순위라는 것을 계산하는 방법이 더 큰 이슈가 되겠지만, 사용가능합니다.

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

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

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

reference 상상개발자

reference hashcode-허대영님!!