Queues Data Structure At Banks!
Do you have a bank account? Have you ever got inline and waited for your turn to speak to a teller?
We all do! Whether its a bank or clothing store or super market, we all had been in a queue and waited our turn to perform a transaction.
Queue Data Structure
In computer science, a queue is a collection of items that are managed in a sequence. First one in is first one out (FIFO). Queue can be modified by adding items at one end of the sequence and removing an item from the other end of the sequence.
- Enqueue & Dequeue methods
“Queue is an abstract data structure, somewhat similar to Stacks. Unlike stacks, a queue is open at both its ends. One end is always used to insert data (enqueue) and the other is used to remove data (dequeue). Queue follows First-In-First-Out methodology, i.e., the data item stored first will be accessed first.” (Tutorialspoint.com) There are multiple different ways to implement queues and stacks with linked lists and arrays.
- Linkedlist Queue
In a singly-linked list with just a head pointer, the time complexity of prepend a value is O(1). We simply create the new element, connects its pointer to point to the old head of the list, then updating the head pointer. The time complexity to delete the first element is also O(1), which is done by updating the head pointer to point to the element after the current head, then freeing the memory for the old head. However, “the constant factors in these O(1) terms may be high due to the expense of dynamic allocations. The memory overhead of the linked list is usually O(n) total extra memory due to the storage of an extra pointer in each element.” (templatetypedef)
- Array Queue
In a dynamic array, we can access any element in O(1) time. We can also append an element at the same time complexity. This means that the total time for n insertions is O(n). However, the actual time bounds on any insertion may be much worse. But, there are techniques to try to time complexity by allocating extra space and lazily copying the elements over. Typically, the memory usage of a dynamic array is quite good. When the array is completely full, there is only O(1) extra overhead. Because allocations are infrequent and accesses are fast, dynamic arrays are usually faster than linked lists. (templatetypedef)
- Circular Queue
Circular Queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle. It is also called ‘Ring Buffer’. In a normal Queue, we can insert elements until queue becomes full. But once queue becomes full, we can not insert the next element even if there is a space in front of queue. Operations on Circular Queue require the use of addition variables such as read and if statements. For example, steps for enqueue operation; First check wether the queue is full by checking if rear is equal to size-1 and if front is equal to — or if rear is equal to front-1. If it is full then display queue is full. Otherwise, check if rear is equal to size-1 and front is not 0 if it is true then set rear equal to 0 and insert item.
- Helpful Methods
The peek() method returns the item at the front the queue. It does not deletes the item in the container. This is similar to a bank teller looking at the line and seeing who is in front. This method returns the head of the queue. The method does not throws an exception when the queue is empty, it returns None instead.
Helper methods such as is_empty() and length() make it easier to manage the code. Method is_empty() used to check if the queue is empty or not and returns a boolean. This is done by checking if the size of the Linkedlist is or length of Array queue are equal to zero. Length() method returns the current length of the queue or the number of objects present in it.
- Real World Application
Some examples of real-world queue application are all the aspects where someone or some objects need to wait in line and the server must maintain the line serial for serving. like-
- Car wash
- Ticket counter line where people who come first will get his/her ticket first.
- Bank line where people who come first will done his/her transaction first.
- Toilet or Washroom use line
- Key press sequence in keyboard.
- ATM booth line
