Hello everyone ! We have been talking about
data structures for some time now. As we know, data structures are ways to store and organize
data in computers. So far in this series, we have discussed some of the data structures
like arrays, linked lists and in last couple of lessons, we have talked about stack. In
this lesson, we are going to introduce you to Queues. We are going to talk about Queue
ADT. Just the way we did it for stack, first we are going to talk about queue as abstract
data type or ADT. As we know, when we talk about a data structure as abstract data type,
we define only the features or operations available with the data structure and do not
go into implementation details. We will see possible implementations in later lessons.
In this lesson, we are only going to discuss logical view of queue data structure. Ok ! so
let’s get started. Queue data structure is exactly what we mean when we say queue in
real world. A queue is a structure in which whatever goes in first, comes out first. In
short, we call Queue a FIFO structure. Earlier, we had seen stack which is a last-in-first-out
structure which is called a last in first out structure or in short LIFO. A stack is
a collection in which both insertion and removal happen from the same end that we call the
top of stack. In queue however, an insertion must happen from one end that we call rear
or tail of the queue and any removal must happen from the other end that we can call
front or head of the queue. If i have to define queue formally, as an abstract data type,
then a queue is a list or collection with the restriction or the constraint that insertion
can be and must be performed at one end that we call the rear of queue or the tail of queue
and deletion can be performed at other end that we can call the front of queue or head
of queue. Lets now define the interface or operations available with queue. Just like
stack, we have two fundamental operations here. An insertion is called Enqueue operation.
Some people also like to name this operation push. Enqueue operation should insert an element
at tail or rear end of queue. Deletion is called Dequeue operation. In some implementation,
people call this operation pop also. Push and pop are more famous in context of stack.
Enqueue and Dequeue are more famous in context of Queues. While implementing, you can choose
any of these names in your interface. Dequeue should remove an element from front or head
of the queue. And Dequeue typically also returns this element that it removes from the head.
The signatures of Enqueue and Dequeue for a queue of integers can be something like
this. Enqueue is returning void here while Dequeue is returning an integer. This integer
should be the removed element from the queue. You can design Dequeue also to return void.
Typically a third operation front or Peek is kept just to look at the element at the
head. Just like the top operation that we had kept in stack. This operation should just
return the element at front and should not delete anything. Ok, we can have few more
operations. We can have one operation to check whether queue is empty or not. If queue has
a limited size, then we can have one operation to check whether queue is full or not. Why
I am calling out these alternate names for operations is also because most of the time,
we do not write our own implementation of a data structure. We use in-built implementations
available with language libraries. Interface can be different in different libraries. For
example, if you would use the in-built queue in C++, the function to insert in push which
in C# its Enqueue. So, we should not confuse. I’ll just keep more famous names here. OK
! so these are the operations that i have defined with queue ADT – Enqueue, Dequeue,
Front and IsEmpty. We can insert or remove one element at a time from the queue using
Enqueue and Dequeue. front() is only to look at the element at head. InEmpty is only to
verify whether Queue is empty or not. All these operations that i have written here
must take constant time or in other words, their time complexity should be big-oh of
one. Logically, a queue can be shown as a figure or container open from two sides. So,
an element can be inserted or Enqueued from one side and and an element can be removed
or de-queued from other side. If you remember stack, we show a stack as a container open
from one side. So, an insertion or what we call push in context of stack and removal
or pop, both must happen from the same side. In queue, insertion and removal should happen
from different sides. Let’s say I want to create a queue of integers, lets say initially
we have an empty queue. I will first write down one of the operations and then show you
the simulation in logical view. Lets say i first want to enqueue number 2. This figure
that I’m showing here right now, is an empty queue of integers and I am saying that I’m
performing and Enqueue operation here. In a program, I would be calling an Enqueue function
passing it number 2 as argument. After this Enqueue, we have one element in the queue,
we have one integer in the queue. Because we have only one element in the queue right
now, front and rear of the queue are same. Lets Enqueue one more integer. Now, i want
to insert number 5. 5 will be inserted at rear or tail of the queue. Let’s Enqueue one
more. And now, I want to call Dequeue operation. So, we will pick 2 from head of the queue
and it will go out. If Dequeue is supposed to return this removed integer, then we will
get integer 2 as return. Enqueue and Dequeue are the fundamental operations available with
Queue. In our design, we can have some more for our convenience. Like we have front and
IsEmpty here. A call to front at this stage will get us number 5, integer 5 as return.
No integer will be removed from the queue. Calling IsEmpty at this stage can return us
a boolean false or a zero fro false and 1 for true. So, this pretty much is Queue works.
Now, one obvious question can be, what are the real scenarios where we can use Queue,
what are the use cases of Queue data structure. Queue is most often used in a scenario where
there is a shared resource that’s supposed to serve some request, but the resource can
handle only one request at a time. It can serve only one request at a time. In such
a scenario, it makes most sense to Queue up the requests. The request that comes first,
gets served first. Lets say we have a printer shared in a network. Any machine in the network
can send a print request to this printer. Printer can serve only one request at a time,
it can print only one document at a time. So, if a request comes when its busy, it can’t
be like – I’m busy, request later. That will be really rude of the printer. What really
happens is that the program that really manages the printer, puts the print request in a queue.
As long as there is something in the Queue, printer keeps picking up a request from the
front of the queue and serves it. Processor on your computer is also a shared resource.
A lot of running programs or processes need time of the processor and the processor can
attend to only one process at a time. Processor is the guy who has to execute all the instructions
, who has to perform all the arithmetic and logical operations. So, the processes are
put in a queue. Queue in general can be used to simulate wait in a number of scenarios.
We will discuss some of these applications of queue in detail while solving some problems
in later lessons. This is good for an introduction. In next lesson, we will see how we can implement
Queue. This is it for this lesson. Thanks for watching !