Data structures: Introduction to Queues

Hello everyone ! We have been talking about data structures for some time now. As we know, data structures are.


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 !

92 thoughts on “Data structures: Introduction to Queues”

  1. Oh God! not again please. . . . .. Can't the tutorial be proceeded without mentioning 'time-complexity' everytime? Everywhere it creates nothing but annoyance . . . .

  2. usually i wont waste time putting up comments for videos but this time i gotta say that u r awesome teacher and a good technical person keep sharing videos sir thank you!

  3. "That would be really rude of the printer". Made my day
    Thanks for all the videos. I don't get it why you've got 1 dislike at every video. maybe somene is jealous at your channel

  4. sir your teaching method is excellent ….continue it and make all programmer strong enough!!!
    you really changed my view of thinking sir!!

  5. Hats off to u man. Your tutorials were really very helpful. It helped me clear my basics. Keep on the good work. Cheers!

  6. You present the video in such a lucid manner if I'm not even paying half of my attention I'd still be able to understand you.

  7. i think after taking ur tutorial ur r great teacher there is no need to take classes of university thats why there is a probability of shortage of attenedence in university

  8. i have a quick question , when i print my document/documents i am sending the data to my printer in a queue schedule correct FIFO. What if my printer said " no! i am busy " should i hack the kernel programming structure and fix the error? or should i lay off the drugs because a printer should not be talking to me ?

    jk great video

  9. Yes. This guy is an amazing teacher, with and delightful touch of humor. Does anyone know if he is still active on youtube? Great content!

  10. #include<stdio.h>

    int solveMazeUtil(int maze[10][10],int n, int x, int y, int sol[10][10]);

    void printSolution(int sol[10][10],int n)
    {
    int i,j;
    for ( i = 0; i < n; i++)
    {
    for (j = 0; j < n; j++)
    printf(" %d ", sol[i][j]);
    printf("n");
    }
    }

    int isSafe(int maze[10][10],int n, int x, int y)
    {

    if(x >= 0 && x < n && y >= 0 && y < n && maze[x][y] == 1)
    {

    return 1;
    }

    return 0;
    }

    int solveMaze(int maze[10][10],int n)
    {
    int sol[10][10];
    int i,j;
    for(i=0;i<n;i++)
    for(j=0;j<n;j++)
    sol[i][j]==0;

    if(solveMazeUtil(maze,n,0, 0, sol) == 0)
    {
    printf("Solution doesn't exist");
    return 0;
    }

    printSolution(sol,n);
    return 1;
    }

    int solveMazeUtil(int maze[10][10],int n, int x, int y, int sol[10][10])
    {
    return 1;

    if(maze[x][y]==9)
    {
    sol[x][y] = 9;
    return 1;
    }

    if(isSafe(maze,n, x, y) == 1)
    {

    sol[x][y] = 1;

    if (solveMazeUtil(maze,n, x+1, y, sol) ==1)

    return 1;

    if (solveMazeUtil(maze,n, x, y+1, sol) == 1)
    return 1;

    sol[x][y] = 0;
    return 0;
    }

    return 0;
    }

    int main()
    {
    int maze[10][10];

    int i,j,n;
    printf("enter size of arrayn");
    scanf("%d",&n);

    printf("enter mazen");
    for(i=0;i<n;i++)
    for(j=0;i<n;i++)
    scanf("%d",maze[i][j]);

    solveMaze(maze,n);
    return 0;
    }

    can u help me debugg this… its mouse in a maze problem…

  11. You are really good teacher sir. Thank you 🙂 I have a doubt, like in arrays we have seen that it accepts only similar data types, so what is the scenario in queue, linklist, tree etc. Kindly reply 🙂

  12. great tutorial, cant believe how anyone could dislike your tutorial. started watching your playlist, also love how you put time by implementing subtitles 🙂

  13. thanku sir ..ur videos are really awsm .thanks alot 4 sharing such precious knowledge !!!your videos help me to learn alot !1

  14. I've used YouTube since it first launched. I never commented on a video. This being said, I would like to personally thank you for making a positive difference. Your videos are on point and I appreciate that you took the time to make them.

  15. Seriously consider teaching if you haven't!! You are an incredible teacher my friend, I feel more and more prepared for my final exam with every video. You teach better than my professor, and I'm pretty sure he is one of the top paid professors at my university.

  16. Thank you so much. Your videos on data structures have been a real life saver. I was having such a hard time wrapping my mind around these from what I've read in my textbook and online. You have broken each of these structures down in such a way that makes them easily understandable. Thank you. Thank you. Thank you.

  17. Thank you for the video! notice the "Next" button, link to the same video, and not to the "Implementation of Queue" video.

  18. it would be really great if u do videos of java.there are many complicated concepts in java and u will definitely do a great job in making us understand them.I like all ur videos.Tq

  19. You r really a hero sir..😆😆 please please make …video on other topics of computer science as well… I really love the way u explain the things in few minutes … i Admire the depth of ur knowledge …thanks😊

  20. Very nice tutorial………………..
    http://www.mukeshrajput102.com/2017/12/implementation-of-queue-using-linear.html

  21. You said that deletion is done from the head or front but when you said de queue 3 it is present at the rear.. how is that??????

  22. Get More Data Structure Program by Download this App
    https://play.google.com/store/apps/details?id=com.data_structure.user.datastructureandalgorithmusingc

  23. usually i don't comment…But this time i am doing…I liked your explanation…..It cleared all my concepts….Mind blowing….

Leave a Reply

Your email address will not be published. Required fields are marked *