computer science/data structure4 Implement Circular Queue using linked list Circular Queue A circular queue can be implemented using array and linked list. To implement a circular queue using a linked list, you must use a circular linked list where the rear node is connected to the front node. Complexity Time Complexity Enqueue : \(O(1)\) Dequeue: \(O(1)\) Space Complexity : \(O(n)\) as the queue is size of \(n\) Implement Circular Queue using linked list header // // C.. 2024. 4. 19. Implement Circular Queue using array Circular Queue A circular queue is extended version of normal queue. It uses fixed-size buffer where the last element is connected to the first element. How to Implement a Circular Queue A circular queue can be implemented using two data structures Array Linked List Complexity Time Complexity Enqueue : \(O(1)\) Dequeue: \(O(1)\) Space Complexity : \(O(n)\) as the queue is size of \(n\) Implement.. 2024. 4. 19. Doubly Linked List Doubly Linked List A doubly linked list whose nodes contain three fields data the pointer to the previous node the pointer to the next node Time complexity \(n\) : the number of nodes insert new node: \(O(1)\) append new node: \(O(1)\) delete \(i\)th node \((0 \le i \lt n)\) forward and backward : \(O(1)\) others : \(O(n)\) delete a pointer to the node that is given : \(O(1)\) find forward and b.. 2024. 4. 17. 단조 스택(Monotonic Stack) 단조 스택(Monotonic Stack) 이란 단조 스택(Monotonic Stack)은 스택(Stack) 자료 구조의 변형 중 한 개로 스택의 원소들이 단조 증가 혹은 단조 감소 상태인 스택을 말한다. 겉보기에는 힙(Heap) 자료구조와 비슷하게 보이지만 다르다. 정확하게 말하자면 단조 스택이란 스택에 원소를 삽입할 때 스택의 상태가 단조 증가 혹은 감소를 유지되는 것을 말한다. 사실 단조 스택은 자주 쓰이지는 않는다. 하지만 특정 문제에서는 단조 스택이 힘을 발휘할 때가 있다. 그중 한 개는 자신보다 처음으로 크거나 작은 원소의 값을 찾는 문제(Next Greater or Smaller Element)이다. 예를 들어 배열 [2, 1, 2, 4, 3]가 주어졌을 때 자신보다 처음으로 큰 원소를 저장하.. 2022. 11. 1. 이전 1 다음