queue

@algorithm.ts/queue

A typescript implementation of Priority Queue (based on min-heap) and Circular Queue.

Install

• npm

  npm install --save @algorithm.ts/queue

• yarn

  yarn add @algorithm.ts/queue

Usage

PriorityQueue

Priority Queue is a special queue structure, the first element of the queue always returns to the minimum value in the queue, and the amortized time complexity of the enqueue and dequeue operations are both $O(\log N)$.

• IPriorityQueue: PriorityQueue implements the IPriorityQueue interface.

  Signature	Description
  consuming(): IterableIterator<T>	Popup the elements from the queue by the dequeue order.
  count(filter: (element: T) => boolean): number	Count the elements in the queue which matched by the filter.
  dequeue(newElement?: T): T|undefined	Popup the top element, and push the given newElement if it is not undefined.
  enqueue(val: T): void	Push a element into the priority queue.
  enqueues(elements: Iterable<T>): void	Push multiple elements into the priority queue.
  enqueues_advance(elements: ReadonlyArray<T>, start: number, end: number): void	Push multiple elements into the priority queue.
  exclude(filter: (element: T) => boolean): void	Remove elements matched the filter.
  destroy(): void	Destroy the queue and release the memory.
  front(): T|undefined	Get the top element from the priority queue.
  init(initialElements?: Iterable<T>: void	Initialize priority queue with initial elements.
  readonly size: number	Get the number of elements.
  readonly destroyed: number	Indicate whether the priority queue destroyed.

• IPriorityQueueProps

  export interface IPriorityQueueProps<T> {
    /**
    * If the compare(x, y) < 0, then x has a higher precedence than y.
    */
    compare: ICompare<T>
  }

  • new PriorityQueue<number>({ compare: (x, y) => x - y }): The top element has a minimum value.
  • new PriorityQueue<number>({ compare: (x, y) => y - x }): The top element has a maximum value.

CircularQueue

Circular queue is a queue structure, the main purpose of its design is to reuse space as much as possible on the basis of ordinary queues. Circular queues usually need to specify the maximum volume C of the collector. If the number of elements in the queue exceeds C, only the most recent C elements are kept in the queue. Other operations are the same as ordinary queues.

• ICircularQueue: CircularQueue implements the ICircularQueue interface.

  Signature	Description
  consuming(): IterableIterator<T>	Popup the elements from the queue by the dequeue order.
  count(filter: (element: T) => boolean): number	Count the elements in the queue which matched by the filter.
  dequeue(newElement?: T): T|undefined	Popup the top element, and push the given newElement if it is not undefined.
  enqueue(val: T): void	Push a element into the circular queue.
  enqueues(elements: Iterable<T>): void	Push multiple elements into the circular queue.
  enqueues_advance(elements: ReadonlyArray<T>, start: number, end: number): void	Push multiple elements into the circular queue.
  exclude(filter: (element: T) => boolean): void	Remove elements matched the filter.
  destroy(): void	Destroy the queue and release the memory.
  front(): T|undefined	Get the first enqueued element from the circular queue.
  back(): T|undefined	Get the last enqueued element from the circular queue.
  init(initialElements?: Iterable<T>: void	Initialize circular queue with initial elements.
  resize(MAX_SIZE: number): void	Resize the max-size of queue with the given size.
  rearrange(): void	Rearrange elements, that is, put the first element in place 0-index.
  readonly size: number	Get the number of elements.
  readonly destroyed: number	Indicate whether the circular queue destroyed.

• ICircularQueueProps

  export interface ICircularQueueProps {
    /**
    * Initial capacity of the circular queue.
    */
    capacity?: number
    /**
    * Automatically extends the queue capacity when the queue is full.
    * @default true
    */
    autoResize?: boolean
    /**
    * @default 1.5
    */
    autoResizeExpansionRatio?: number
  }

Example

• Basic -- PriorityQueue

  import { PriorityQueue } = '@algorithm.ts/queue'
  
  const Q = new PriorityQueue<number>({ compare: (x, y) => y - x })
  
  Q.enqueue(3)
  Q.enqueue(7)
  Q.enqueue(-5)
  Q.enqueue(1)
  Q.size        // => 4
  Array.from(Q) // => [7, 3, -5, 1] !!!NOTE: the result are not guaranteed to be ordered.
  
  Q.dequeue()   // => 7
  Q.dequeue()   // => 3
  Q.front()     // => 1
  Q.front()     // => 1
  Q.dequeue()   // => 1
  Q.front()     // => -5
  Q.dequeue()   // => -5
  Q.front()     // => undefined
  Q.dequeue()   // => undefined

• Basic -- CircularQueue

  import { CircularQueue } from '@algorithm.ts/queue'
  
  const queue = new CircularQueue<{ name: string }>()
  
  // Initialize the circular-queue with the maximum number of elements it can
  // be managed.
  queue.init(100)
  
  // Append a element to the end of the queue.
  queue.enqueue({ name: 'alice' }) // => 0
  queue.enqueue({ name: 'bob' }) // => 1
  queue.size          // => 2
  
  // Get the front element of the queue.
  queue.front()       // => { name: 'alice' }
  
  // Get the last element of the queue.
  queue.back()        // => { name: 'bob' }
  
  // Take off the first element of the queue.
  queue.dequeue()     // => { name: 'alice' }
  queue.size          // => 1

• A solution for 剑指 offer#63 https://www.nowcoder.com/practice/9be0172896bd43948f8a32fb954e1be1

  import { PriorityQueue } from '@algorithm.ts/queue'
  
  const lowerQ = new PriorityQueue<number>({ compare: (x, y) => x - y })
  const upperQ = new PriorityQueue<number>({ compare: (x, y) => y - x })
  
  export function Insert(num: number): void {
    if (lowerQ.size === upperQ.size) {
      upperQ.enqueue(num)
      lowerQ.enqueue(upperQ.dequeue()!)
    } else {
      lowerQ.enqueue(num)
      upperQ.enqueue(lowerQ.dequeue()!)
    }
  }
  
  export function GetMedian(): number {
    return lowerQ.size === upperQ.size
      ? (lowerQ.front()! + upperQ.front()!) / 2
      : lowerQ.front()!
  }

Related