알고리즘 & 자료구조 - 큐(Queues), 스택(Stacks)

  실제로 프로그래밍 언어들에서 존재하지 않는다. 스택과 큐는 일종의 "규칙"이다. 이들을 추상적 자료구조(ADT - Abstract Data Type)라고 부른다. 자료구조의 방법이 코드로 정의된 것이 아니라, 구조의 행동 양식만 정의된 것이다. 규칙들만 이해하면 직접 '스택'과 '큐'라는 자료구조를 만들 수 있다. 스택과 큐는 배열(array) 위에 규칙을 설정한 모습이다.

  스택은 배열이 수직으로 쌓여있는 것이다. 스택을 이해하기 위해서는 팬케이크가 쌓여 있는 모습을 상상해보자. 팬케이크를 쌓을 때, 새로운 팬케이크는 그 위에 쌓는다. 팬케이크 더미를 줄이고 싶을 때는 맨 위에 있는 팬케이크부터 먹는다. 배열에 요소를 추가하거나 삭제할 때 맨 위체서부터 차례대로 할 수 있다. 이런 방식을 "LIFO"라고 한다.

  큐는 배열이다. 큐는 줄서는 것이다. 버스를 기다린다고 가정하면, 줄 맨 앞에 서 있는 사람이 가장 먼저 버스를 탄다. 줄에 가장 뒤에 서서 기다린 사람은 버스에도 가장 마지막에 탑승하게 된다. 이런 방식을 "FIFO"라고 한다.

 

  언제 큐를 쓰고 스택을 쓰는가?

  웹브라우저에서 뒤로가기를 누른다는 것은 스택을 사용하는 것이다. Ctrl + Z 되돌리기도 스택이다. 앱에서 '되돌리기'를 실행하려면 유저가 하고 있는 행동들을 스택에 차곡차곡 쌓다가 되돌리기를 누르는 순간 스택을 사용해 과거로 돌아간다. 

  큐의 예시는 이메일 전달 혹은 푸시 알림 기능, 쇼핑몰 주문 처리 방식(선착순) 콜센터의 백엔드. 큐는 모든 곳에 있다.

 

https://www.youtube.com/watch?v=Nk_dGScimz8