스택, 큐
스택, 큐는 일종의 규칙이다
추상적 자료구조, ADT(Abstract Data type) 라고도 부른다.
스택(Stacks)
스택의 일상적인 예로는 블럭을 쌓고 빼는과정, Ctrl + Z 와 같은 기능, 웹브라우저의 이전페이지 가기와 같다.
스택은 배열이 수직으로 쌓여있다.
요소를 추가, 삭제할 때 맨 위에서부터 차례로 할 수 있다.
LIFO(Last In, First Out), 후입선출 방식이다.
큐(Queues)
큐의 일상적인 예로는 놀이공원 줄서기, 콜센터 상담대기와 같다.
먼저 들어온게 먼저 나가는 구조이고 추가는 뒤에만 할 수 있다.
FIFO(First In, First Out) 선입선출 방식이다.
데크(deque)
데크는 특히 push/pop 연산이 빈번한 알고리즘에서 리스트보다 월등한 속도를 자랑한다.
양방향으로 큐가 있는 구조이다
앞,뒤 양방향으로 요소를 추가 제거할 수 있다.
데크는 양끝 엘리먼트의 append와 pop이 압도적으로 빠르다.
일반적으로 리스트 양끝의 요소에 접근하여 추가, 제거를 할 경우,
시간복잡도가 O(n)이 소요되는 데 반해, 데크(deque)는 O(1)로 접근 가능하다.
데크는 스택이나 큐처럼 사용할 수도 있다.
시작요소나 끝의 요소에 접근하여 추가 제거하는데에 최적화된 연산 속도를 제공한다.
대부분의 경우에 데크는 리스트보다 좋은 옵션으로 사용할 수 있다.
Software Engineer