Queue

Queue is a kind of data structure that insertions done at one end, deletions done at the other end. It is FIFO by design which is in contrast with 202112031157. It could be implemented in array#.

Queue can be used for:

  • printer job queue
  • file server
Links to this page
  • Unweighted Shortest Path

    To calculate the #shortest path for unweighted graph, the following algorithm used the strategy breadth-first search where the siblings of the vertex get searched first which utilise the 202112101836.

  • Traversal
    In level-order traversal, do not use recursive method, use it alongside with Queue instead
  • Topological Sort
    When optimised with 202112031157 or 202112101836, it results in \(O(\vert E \vert + \vert V \vert)\)

    Note: This algorithm uses 202112101836 where all vertices of indegree 0 will be placed into the queue initially or upon decremented.

  • Stack

    Stack is a kind of data structure that insertions and deletions only performed at the top of its structure. It is LIFO by design which is in contrast with Queue. It could be implemented in list# or array#.

  • Priority Queue/Heap

    Heap is a kind of #Queue that prioritise short tasks over long tasks. Its implementation could be based on tree# or list#.

  • Pipe

    Pipe provides a one-way flow of data, where the output of a process is directed into the input of another, which can be created using pipe() #Unix System Call. Pass in a file descriptor array (of type int) with a size of 2, the system call will return 2 file descriptors for use: fd[0] for reading and fd[1] for writing. A typical use case of Pipe is to establish a communication channel# between two related processes. The maximum amount of data allowed in the pipe (OS treats it like a Queue#) is usually 5120 bytes. In #unix, Pipe is implemented using #Unix Domain Sockets.

  • Array Implementation of Queue

    #202112101836 could be implemented using Array. Since Array is being used, the program need to declare three vairables: Front, Rear and Size to keep track of the queue’s information.

#data-structure #queue