지난 스택(Stack)편에 이어 이번 시간에는 큐(Queue)에 대해 알아보겠다. Show 스택(Stack) 편 link https://algoroot.tistory.com/54 [알고리즘, 자료구조] 자바스크립트로 스택(Stack)구현하기 어떤 데이터의 구체적인 구현 방식은 생략한 채, 데이터의 추상적 형태와 그 데이터를 다루는 방법만을 정해놓은 것을 가지고 ADT(Abstract Data Type) 혹은 추상 자료형이라고 한다. 그 중 널리 사 algoroot.tistory.com
큐(Queue) / Dequeue, Enqueue / 이해를 돕기 위해 그려본 Queue의 flow 속성
메소드
큐 (Queue) 사용 사례데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용한다.
JavaScript 배열로 큐(Queue) 구현dequeue()에서 shift() 를 사용해 간단히 구현할 수 는 있다. 하지만 shift()특성상 배열 맨 앞의 요소(0번째 요소) 를 삭제하게 되면 배열의 길이(length)만큼 기존 요소들을 앞으로 당겨줘야하므로 시간복잡도가 O(n)이 되어버린다. 정석대로의 큐(Queue)라면 시간복잡도가 O(1)이 되어야한다.
배열을 이용하지 않고 큐(Queue) 구현 ( In JavaScript)시간복잡도를 O(1)으로 하기 위해 연결리스트(LInked List)를 통해 큐(Queue)를 자바스크립트(JavaScript)로 구현해보겠다.
프린트 테스트까지 완료. 큐(Queue)의 Big-O (Time Complexity)Insertion : 큐(Queue)에 데이터를 추가하는 것은 큐(Queue)의 맨 뒤 요소(rear) 에 하나를 추가(push) 하면된다. 스택에 들어있는 값들이 무수히 많아도 하나의 데이터의 삽입은 한 번이기 때문에 시간 복잡도는 O(1)이 된다. delete : FIFO에 따라 삭제를 할 때도 첫 번째 데이터(front)가 삭제되는 것이므로 스택의 크기에 상관없이 시간복잡도는 O(1)이된다. Access : 큐(Queue) 특성상 한쪽 끝(rear) 으로만 자료를 넣고 뺄 때는 첫 번째 데이터(front)가 빠지게 되는 자료구조이므로 데이터 접근 또한 첫 번째 데이터(front)를 통해서만 접근이 가능하다. 삭제 또한 첫 번째 데이터(front)을 통해서만 가능하다. 따라서 n번 째 접근은 첫 번째 데이터(front)부터 순회하기 때문에 O(n)의 시간복잡도를 가진다. Search : 데이터를 찾을 때 만약 큐(Queue)의 첫 번째 데이터(front)를 찾는다면 시간복잡도는 O(1)일 것이다. 하지만 가장 뒤에있는 데이터를(rear) 찾는다면 데이터의 개수만큼 작업이 발생되므로 시간복잡도는 O(n)이 되겠다.
빼놓을 수 없는 스택(Stack) 자료구조 이해 & 구현하기! https://algoroot.tistory.com/54 [알고리즘, 자료구조] 자바스크립트로 스택(Stack)구현하기 어떤 데이터의 구체적인 구현 방식은 생략한 채, 데이터의 추상적 형태와 그 데이터를 다루는 방법만을 정해놓은 것을 가지고 ADT(Abstract Data Type) 혹은 추상 자료형이라고 한다. 그 중 널리 사 algoroot.tistory.com Reference https://gmlwjd9405.github.io/2018/08/02/data-structure-queue.html https://makasti.tistory.com/92 https://www.youtube.com/watch?v=LbAKOE5_Du4 https://www.youtube.com/watch?v=iY0Ab5z5jY0 |