Queue

Queue is a first-in-first-out data structure. The element that is added to the queue data structure first, will be removed from the queue first. Dequeue, priority queue, and circular queue are the variants of queue data structure. Queue has the following application uses:

Queue Data Structures

• A queue is an extended form or a linear data structure in which the initial element is added from one end, known as the REAR (sometimes known as the tail), and the last member is deleted from the other end, known as the FRONT (also called head). 
• This turns the queue into a FIFO data structure, meaning that the member that was added first will likewise be removed first.
• Enqueue is the process of adding an element to a queue, while Dequeue is the process of removing an element from a queue.

Basic features of Queue

1. Like Stack, Queue is also an ordered list of elements of similar data types.
2. Queue is a FIFO( First in First Out ) structure.
3. Once a new element is inserted into the Queue, all the elements inserted before the new element in the queue must be removed, to remove the new element.
4. peek( ) function is oftenly used to return the value of first element without dequeuing it.

---

Applications of Queue

Queue, as the name suggests is used whenever we need to have any group of objects in an order in which the first one coming in, also gets out first while the others wait for there turn, like in the following scenarios :

1. Serving requests on a single shared resource, like a printer, CPU task scheduling etc.
2. In real life, Call Center phone systems will use Queues, to hold people calling them in an order, until a service representative is free.
3. Handling of interrupts in real-time systems. The interrupts are handled in the same order as they arrive, First come first served.

---

Implementation of Queue

• An Array, Stack, or Linked List can be used to implement a Queue. Using an Array is the simplest approach to construct a queue. 
• The queue's head(FRONT) and tail(REAR) initially point to the array's first index (starting the index of array from 0). 
• The tail moves ahead as we add elements to the queue, always pointing to the spot where the next element will be inserted, while the head stays at the first index.

Queue Data Structure using Stack...

Data in Data Structure

Data Definition

Data Definition defines a particular data with the following characteristics.

Atomic − Definition should define a single concept.
Traceable − Definition should be able to be mapped to some data element.
Accurate − Definition should be unambiguous.
Clear and Concise − Definition should be understandable.

Data Object

• Data Object represents an object having a data.

Data Type

The data type sets the values that may be used with the corresponding type of data, as well as the types of operations that can be performed on the corresponding type of data, such as integer, string, and so on. There are two categories of data:

• Built-in Data Type
• Derived Data Type

Built-in Data Type

Those data types for which a language has built-in support are known as Built-in Data types. For example, most of the languages provide the following built-in data types.

• Integers
• Boolean (true, false)
• Floating (Decimal numbers)
• Character and Strings

Derived Data Type

Derivative data types are data types that are implementation independent, meaning they can be implemented in any way. These data types are usually created by combining primary or built-in data types with their relevant operations. For example,

• List
• Array
• Stack
• Queue

Basic Operations

Various operations are performed on the data in the data structures. The data structure that is chosen is mostly determined by the frequency with which the operation on the data structure must be done.

• Traversing
• Searching
• Insertion
• Deletion
• Sorting
• Merging

Queue Data Structure

Queue Data Structure using Stack

Queue Data Structure

• A queue is defined by its FIFO (First In First Out) property, which means that the element that is inserted first is removed first. 
• As a result, instead of using an array for storage, we can use a Stack to create a Queue.
• For performing enqueue we require only one stack as we can directly push data into the stack, but to perform dequeue we will require two Stacks because we need to follow the queue's FIFO property and if we directly pop any data element out of Stack, it will follow LIFO approach(Last in First Out).

Implementation of Queue using Stacks

• In all we will require two Stacks, we will call them InStack and OutStack.

class Queue {
  public:
  Stack S1, S2;
  //defining methods
  
  void enqueue(int x);
  
  int dequeue();
}

• We know that Stack is a data structure, in which data can be added using the push() method and data can be deleted using the pop() method. 
• To learn about Stack, follow the link: Stack Data Structure

Adding Data to Queue

• As our Queue has Stack for data storage in place of arrays, hence we will be adding data to Stack, which can be done using the push() method, hence :

void Queue :: enqueue(int x) {
  S1.push(x);
}

Removing Data from Queue

• When we say remove data from Queue, it always means taking out the First element first and so on, as we have to follow the FIFO approach. 
• But if we simply perform S1.pop() in our dequeue method, then it will remove the Last element first. So what to do now?

int Queue :: dequeue() {
  while(S1.isEmpty()) {
    x = S1.pop();
    S2.push();
  }
    //removing the element
  x = S2.pop();
    while(!S2.isEmpty()) {
    x = S2.pop();
    S1.push(x);
  }
    return x;
}