How to Implement a Queue in C

so what is a queue and how do you implement it in C that's our topic for today [Music] so I recently did a video about stacks one of the first data structures that you learn anytime you start a real study of data structures and today I want to talk about its cousin the queue so quick recap stacks were basically just a list of elements where you can only access them at one end the top you can push stuff on to the stack you can pop stuff off of the stack if this isn't making any sense you should go watch that video and then come back it may make today's video make more sense but queues are also basically a list there are linear data structure but instead of just accessing at one end we access at both ends but in a very controlled way we have two ends a head and a tail we add new elements to the tail and we remove things from the head so this is a data structure that basically works like a queue in a grocery store or really any scenario where you're waiting in line basically you're adding things to the back of the list and you're taking things off the front of the list and things get serviced in a first-come first-serve order just like with stacks we have two operations instead of push and pop we have n Q and D Q and Q is where we actually add something to the queue DQ is when we remove something from the queue and you're gonna find that we really use cues really everywhere in software anytime you have stuff arriving this can be work this can be network connections whatever anytime you have something that is arriving that you want to process in the order it arrived you want a queue and like a stack we can implement a queue with an array or with a linked list today I'm a little short on time so I'm going to focus on the linked list implementation and we'll pick up the array base queue in a future video and of course if you've never seen linked lists before and that's a little confusing check out my linked list videos just to catch up again link in the description also as always source code is available through patreon check the description for more information on how to get access but now let's jump into the code if you saw the snacks video this code should look familiar to begin with I just took that code replaced stack with Q and removed the code from push and pop so now we have this empty NQ and DQ we have our two operations and we have main that calls those functions but which of course won't work right now because our code doesn't do anything yet and like before we're working with intz just because they're simple and we could easily use doubles float structs pointers anything we want really but insert quick and easy so that's what we're going to use today now the first thing I'm going to change is the definition of what we want to call a queue here with a stack everything happens at one end all pushing and popping happens at that one end at the top so it was enough to just store a single pointer and call that our stack but with my queue I want to keep track of two pointers I need to keep track of the head and the tail which will put together in another struct and we're going to call that struct a queue this is basically just all the data that we're going to need to represent our queue and I'm gonna follow the advice that I recommended to myself in my stacks video and make an initialization function that sets up our queue in an object-oriented language this would be in your constructor but here it's just a function that's going to take a pointer to our struct that's so we can modify it and then we're going to set both the head and the tail to null meaning that our queue starts out empty and saving some typing let's rename these my queues to just queue I like that a bit better now in NQ we're just going to create a new node by calling malloc we set its value to the value we want to add to the cube and we set its next pointer to the goal that's because this is going at the end of the list so it's not going to have anything after it now we need to connect it to our list so we'll check to see if we have a tail on this list if we do we just connect it to the next pointer to the new node we just created then we set the tail to be the new node so it is now the new tail now one last thing if the list was empty and we just added the first element then head is going to still be null so let's just check to see if that's the case and if it is we can just set the head to point to that new node as well so just to recap we created a new node if there's a tail we connect the old up to this new tail and then we make sure that the head still make sense and that's really it of course we still need to return true if we were successful and let's come back up and return false if Malik failed basically just meaning that we couldn't get any more memory because that's really this functions only failure case unless of course someone passes in a bad pointer now let's look at D Q now anytime you're writing a function it's useful to think about its error cases what can I check now to see if this operation that was requested is even possible now with D Q the main check we want to do up front is the empty case if the queue is empty there's nothing we can do I can't return an integer from an empty queue so we're going to first check to see if the queue is empty and if it is we just returned after that we're going to save a pointer to the head and grab the integer value in the head then we just move the current head to point to the node after it this is the same thing we did with our stack and then of course if we run out of nodes we need to make sure to let the tail know and set it to null as well we definitely don't want to leave our tail dangling there and then of course we return our saved result okay so to recap we check for an empty queue just to make sure that we can do what we're being asked to do and then we save the head of the queue oh wait I forgot to free my memory that's not good that would have been a memory leak if I had forgotten to do that so now we save the result and you're going to return and then we finally remove it from the actual list and that looks pretty good let's make sure it works down here in main we need to clean up some stuff mostly just the initialization now let's call our init Q function and these queues are still called s1 s2 and s3 I told you I just copied the stack code over as a starter so that's going to bug me so let's change these to make them q1 q2 and q3 and we initialize the last two Q's okay so now let's see if it works so into the terminal we go we compile it okay nice I'm actually pleasantly surprised I didn't mess anything up there and we run it and it works it's just like our stack example except that the order is reversed so we're getting values out in first in first out or FIFO order rather than in last in first out order or LIFO order which is what we got from our stack so hopefully at this point you can see that queues aren't really complicated they're really not and they're used everywhere as I mentioned you can build a queue with an array as well as a linked list it's not complicated except we do have to be a little bit careful about our array indexes and how they wrap around this is usually using the modulus operator but we'll talk about that in a future video also I know a lot of you have been waiting for more information about the upcoming course that I'm offering in July I'm happy to be able to tell you today that the course page is now up at the following URL you can now sign up for the course space is of course limited because my time is limited and this is going to be a hybrid video and live interactive course check out the link for more information and I look forward to seeing you there if on the other hand you're interested in more free content tips and tutorials check out my other videos like these subscribe to the channel so you don't miss new videos on data structures and other topics that you care about and until next time everyone I'll see you later

Channel: Jacob Sorber

Views: 19,657

Rating: 4.9539475 out of 5

Keywords: queue in c, queue, queue programming, queue implementation, c programming, enqueue, data structures, learn data structures, data structures demo, linked list, hands on data structures training, data structures overview, data structures tutorials, queue in data structure, linked list in data structure, what is queue in data structure, queue tutorial, queue linked list, c queue, queue data structure

Id: FcIubL92gaI

Length: 7min 53sec (473 seconds)

Published: Tue Jun 16 2020