알고리즘 | 탐색 기본 - Stack, Queue

 

스택과 큐 모두 일을 처리하는 순서, 값을 처리하는 순서에 대한 개념.

새롭게 추가되는 값 / 지금 당장 처리해야하는 값을 생각하며 일을 한다.

 

 

Stack

• Last In First Out : LIFO
• 예 / 엘레베이터 : 늦게 온 사람이 제일 먼저 내린다. (문이 하나!)
• 새로운 것 : 뒤로 쌓는다 -> 리스트 : .append()
• 처리할 것 : 뒤에서부터 꺼내 쓴다 -> 리스트 : .pop()

task = ['eat', 'poop', 'sleep']
task.append('cry')
>>> ['eat', 'poop', 'sleep', 'cry']
task.pop()
>>> ['eat', 'poop', 'sleep']

 

리스트.pop() 은 파괴적 함수로 리스트의 마지막 값을 제거한다.

---

Queue

• First In First Out : FIFO
• 예 / 놀이공원 매표소 : 먼저 온 사람이 먼저 떠난다! (출입구가 앞 뒤로 두 개!)
• 새로운 것 : 뒤로 쌓는다 -> 리스트 : .append() 메소드
• 처리할 것 : 앞에서부터 꺼내 쓴다 -> 리스트 : .pop(0) 메소드

task = ['eat', 'poop', 'sleep']
task.append('cry')
>>> ['eat', 'poop', 'sleep', 'cry']
task.pop(0)
>>> ['poop', 'sleep', 'cry']

 

task.pop(0)과 같이 맨 앞의 인덱스(0)을 지정해 주어 앞에 있던 eat이 사라졌다.

---

참고사항

파이썬 언어의 특성상 Queue를 사용할 때 속도 이슈가 있음을 주의하면 좋다! 제일 앞의 원소를 추출하는 pop(0) 때문이다. 따라서 코딩테스트에서 특히 주의할 것. 로직에 결함이 없더라도 시간 초과로 통과가 안될 수 있음...!

코딩 테스트에서 반드시 큐를 사용하겠다고 한다면 --> deque라고 하는 패키지를 불러서 사용하는 것이 좋다.