Let's talk about queues probably one of the most useful data structures in computer science. So this is going to be part one of three in the queue series. So the outline of things we'll be looking at. First, we're going to begin by talking about queues and what they are. Then we're going to go into some complexity analysis concerning queues. Then we'll discuss the implementation details of n queuing and D queuing elements from a queue followed by some source code at the very end in the last video.

So discussion about queues So what exactly is a queue? So below you can see an image of a queue but accuse just a linear data structure that models a real world queue. Having two primary operations we can do with our n queuing and D queuing. So ever queue has a front and a back end We insert elements through the back and remove through the front. Adding elements to the back of the queue is called n queuing. and removing elements from the front of the queue is called D queuing.

However, there's a bit of terminology surrounding queues because there's not really any consistency or when we refer to in queueing D queuing, many people will use multiple different terms. So, n queuing is also called adding but also offering a similar type of thing happens when we're talking about D queuing. So, this is when we remove things from the front of the queue. This is also called polling elements. However, some people will also refer to this as removing an element from the queue. But the problem with saying that is that can cause some ambiguity didn't They mean removing from the front of the queue specifically or from the entire queue.

Make note that if I say removing I'm going to be referring to removing from the front of the queue unless I say otherwise. So let's look at an example of how queue works in detail. However, first notice I have labeled the queues front and back ends so you know where I'm going to be n queuing and D queuing from respectively to avoid confusion, first instructions as in Q 12. So we add 12 to the end of the queue. Then dq so we remove the first element from the front of the queue, which is 55. Another dq operation this time we remove minus one from the front of the queue.

Next and Q seven so add seven to the back of the queue. dq so remove the front element being 33 and lastly and Q minus six. So add it back with the Q just like that. So now that we know where q is, where does this data structure actually get used? Well, a classic example of where Q just gets uses to model a real world cue where you're waiting in the line at a movie theater or in the line at a restaurant. For instance, have you ever been to say McDonald's, where all the caches are full, as soon as one of them gets fried, the next person in line gets order food?

Well, that's a cue. So queues can also be really useful if you have a sequence of elements coming in, but you only keep track of say, the most recent elements. Well, you can add those elements to your queue. And once your queue gets larger than x elements, just dq essentially, queues are also often used in server management. So, suppose for a moment that you have a web server, that's idly waiting for requests from people to use your website, that at any given moment, you can simultaneously serve up to five people. But no more.

If 12 requests come in, in a short amount of time, you're not going to be able to process all of them as new ones come in. So what you do is you process the five that you're able to, and the remaining seven gets a chill in a queue waiting to be served. And whenever you finish processing a request, you dq in the next request, and then you start processing it and you do this until the queue is empty. While you're doing this, more requests come in to access your webpage. Well, they just add them to the end of the queue. queue They are also using graph theory to perform a breadth first search traversal on a graph, which is actually really useful.

We're going to see this example in the next video. All right now concerning complexity analysis of a queue. So as we've seen, it's pretty obvious that n queuing and D queuing operations are constant time. There's also another operation on a queue I have not mentioned yet, and this is peaking. peaking means that we're looking at the value at the front of the queue without removing it. This is also constant time.

However, checky if an element is contained within the queue, is linear time since we would potentially need to scan through all the elements. There's also elements of removal in the sense not in the sense of D queuing or polling, but in actually removing an element from the queue internally. This also requires linear time. Since we would have to scan through all the elements of the worst case Okay, in the next video we're going to look at some implementation details concerning q. So how it's actually done. So guys, thank you so much for watching, and I will catch you in the next video.