Queues - What are they and how do I implement one in Go?

In this video we cover the queue data structure. Specifically, we talk about how they relate to lines (like lines at the grocery story or DMV) in the real world, and some of the terminology used when describing a queue. We then move into implementing a Queue in Go, translating everything we just talked about into something that our program can understand and work with to achieve our desired results.

This post is part of the Let's Learn Algorithms series where we learn how algorithms work, see how to implement them, and then spend some time working on practice problems to reinforce that knowledge. This particular tutorial is part of the section on basic data structures where we discuss things like linked lists, queues, and stacks.

Historically these articles have all been text based, with video coming afterwards when I find time to record. In the data structures section and later posts I tried a slightly different approach; there aren’t any text articles, and instead there are only videos. If anyone is willing to help transcribe these I’d happily work with them to get the transcriptions published with the post, but I unfortunately haven’t been able to do this on my own lately.

• 0:00 - welcome to let's learn algorithms in
• 0:02 - this video we're going to talk about
• 0:04 - queues and then in the next video we're
• 0:06 - going to talk about stacks which are
• 0:08 - similar to queues but new there are some
• 0:10 - subtle differences between the two that
• 0:11 - will sort of change how you use the menu
• 0:14 - when you use them so to get started
• 0:17 - we're just going to sort of cover what a
• 0:18 - queue is and to do this I'm going to try
• 0:20 - to use real-world examples because I
• 0:22 - feel like they're a lot easier to
• 0:23 - understand if you just think of them
• 0:25 - like the you know the real-world
• 0:26 - representation of what they're meant to
• 0:28 - cover so I'm going to leave fullscreen
• 0:30 - here I just want to you know actually be
• 0:33 - able to move these things around and
• 0:34 - show you a queue is like a line at the
• 0:37 - DMV or a line at the grocery store or
• 0:39 - really any sort of line that you can
• 0:41 - think of where people enter the back of
• 0:43 - the line and you know they move towards
• 0:45 - the front so whenever people enter the
• 0:49 - you know if you're the first person
• 0:50 - enter the line you move to the front of
• 0:51 - the line for the second person you're
• 0:52 - the second person in line third person's
• 0:54 - third in line and you know continues on
• 0:56 - like that so the way a key works from
• 0:59 - there is that whenever you know somebody
• 1:01 - is ready to process something from the
• 1:03 - queue so for example in the DMV you
• 1:05 - might have the receptionist and he or
• 1:07 - she might be ready to call the next
• 1:09 - person when they do that they call the
• 1:11 - next person from the front of the line
• 1:13 - so this yellow person here would move
• 1:15 - out of the line and they would go up to
• 1:17 - whoever you know whoever's ready for the
• 1:18 - next person so now this purple person is
• 1:21 - the next person in line and then we've
• 1:23 - got the red person and you know we might
• 1:24 - have more people come into the line and
• 1:26 - they'll always join at the back of the
• 1:27 - line so whenever a new an item gets put
• 1:31 - into a queue it always waits until
• 1:33 - everything before it has been processed
• 1:35 - before it actually it's processed so you
• 1:37 - know where I was pulling from the front
• 1:39 - and putting things into the back
• 1:41 - you
• 1:44 - so now that I've sort of covered what
• 1:47 - what a queue is I want to just talk
• 1:49 - about two common terms you're going to
• 1:51 - see and they're not confusing or
• 1:53 - anything but I just want you to
• 1:54 - understand what they are so that if you
• 1:55 - hear me say them or somebody else say
• 1:57 - them you know what they mean
• 1:58 - the first is to in queue something which
• 2:00 - means to an add an item to the back of
• 2:02 - the queue so that's like if we took this
• 2:04 - blue person data to the back of the
• 2:06 - queue D queuing is removing an item from
• 2:09 - the front of the queue so that's when we
• 2:11 - take this first person in the queue and
• 2:12 - we pull them out that's where D queuing
• 2:14 - that person
• 2:18 - so now that you have a rough idea of
• 2:20 - what a queue is we're going to look at
• 2:22 - how to implement a queue and go
• 2:26 - so there are a lot of ways to implement
• 2:28 - queue and I'm just going to go back to
• 2:31 - full screen for the time being there are
• 2:33 - a lotta different ways to implement a
• 2:34 - queue and you can use all sorts of
• 2:36 - different data structures to represent
• 2:38 - the items in your queue so I don't want
• 2:40 - you to really get caught up on this I'm
• 2:42 - just sort of letting you know that you
• 2:44 - can use like linked lists slices a fixed
• 2:47 - size array or if you're in another
• 2:49 - language like Java you might use an
• 2:50 - ArrayList of you sort of build on top of
• 2:52 - that it really depends on what makes the
• 2:55 - most sense for you and you can also do
• 2:58 - optional things like setting a maximum
• 2:59 - capacity you might have a queue that
• 3:01 - says we can have it most five people in
• 3:03 - this queue right now or five items
• 3:05 - whatever they happen to be so all of
• 3:08 - those are optional things that you can
• 3:09 - do we won't be really covering you know
• 3:12 - capacity and that sort of stuff because
• 3:13 - truthfully it's relatively specific
• 3:17 - needs whenever you have to do stuff like
• 3:18 - that
• 3:19 - so the more general use case is just a
• 3:21 - queue that you know allows for any
• 3:23 - number of items and we can use something
• 3:25 - like a slice to store it so as I said
• 3:28 - we're going to use a slice and that's
• 3:30 - mostly just to keep things simple slices
• 3:32 - are easy to work with because you know
• 3:34 - they can dynamically change in size and
• 3:36 - you might you might come back and say
• 3:39 - like oh using that slice means it's
• 3:41 - going to have to resize more often and
• 3:42 - it's going to be a little bit slower so
• 3:44 - I just want to warn you now that you
• 3:46 - really shouldn't get caught up in those
• 3:47 - minor details right now for the most
• 3:49 - part you just want to understand how it
• 3:51 - works and then when you do get to a
• 3:52 - point if you find out that your queue
• 3:54 - implementation is really slowing things
• 3:56 - down you can tweak it but you know
• 3:58 - whenever you're just getting started
• 3:59 - these are such minor details and the
• 4:01 - minor speed improvements that they're
• 4:02 - not worried you know they're not worth
• 4:04 - focusing on the last thing is we're
• 4:07 - going to sort integer arc integers in
• 4:09 - our queue for now you can replace with
• 4:11 - this with other data types and you can
• 4:13 - use things like interfaces to you know
• 4:15 - kind of make it more generic but because
• 4:18 - go does not have generics you can't
• 4:20 - write one queue implementation and go
• 4:22 - that works for every data type at least
• 4:24 - not as well as it would with generics
• 4:29 - so the last thing that I want to sort of
• 4:31 - cover is just a rough overview of how
• 4:34 - we're going to do this implementation so
• 4:35 - before we even jump into the code I want
• 4:37 - to say that our slice the length of our
• 4:40 - slice will always have a length equal to
• 4:42 - the size of our queue so if our queue
• 4:44 - has zero items in it our slice is going
• 4:46 - to have a length of zero if our queue
• 4:48 - has four items in it our slice is going
• 4:50 - to have a length of four now the
• 4:51 - capacity of our slice you know the total
• 4:54 - number of memory allocated spots for it
• 4:56 - is is going to be something that might
• 4:58 - change but the length of the slice the
• 5:00 - actual used slots will always be exactly
• 5:02 - the same as the number of items in our
• 5:04 - queue
• 5:06 - and then the next thing is that our
• 5:08 - indices are going to go from the front
• 5:10 - of the queue to the back of the queue
• 5:12 - meaning that the index 0 is going to
• 5:15 - represent the front of our queue and the
• 5:17 - index 3 or 4 or whatever the highest
• 5:20 - index is is going to represent the back
• 5:21 - of the queue so below I have two
• 5:24 - visualizations and they're the same
• 5:26 - example the only thing I'm sort of
• 5:28 - showing you here is that it doesn't
• 5:30 - matter if you you put the front and the
• 5:32 - back on the left or the right
• 5:33 - the indices always map so that zero is
• 5:36 - at the front and you know whatever the
• 5:37 - highest number is is at the back
• 5:42 - so I should have covered this earlier
• 5:45 - the one thing that I do want to say is
• 5:47 - that we won't be going over a ton of the
• 5:49 - uses for queue right now but the most
• 5:51 - common one is a BFS and if you want to
• 5:55 - see that you know in action I do have
• 5:56 - another video where we're sort of
• 5:58 - covering graph theory and some of the
• 6:00 - graph algorithms so I should have one
• 6:02 - covering BFS shortly but I had to make
• 6:04 - this first because I wanted to explain
• 6:05 - what a queue was before I actually went
• 6:07 - to those videos
• 6:09 - all right so now we're going to move on
• 6:11 - to coding so I'm going to go here to my
• 6:15 - code and I've got Q dot go is in just a
• 6:20 - file that I created you can see that
• 6:22 - well let me get this up so you can see Q
• 6:27 - dot go is it all it says is package main
• 6:29 - right now doesn't have anything else in
• 6:30 - it and it's just here so we can create
• 6:32 - our Q so to get started the first thing
• 6:35 - we're going to do is we want to create
• 6:37 - some sort of type that's going to you
• 6:40 - know contain our Q so i've already said
• 6:42 - before that we're going to be using a
• 6:43 - slice to store the nothing of the values
• 6:45 - in our Q and we're going to be storing
• 6:47 - integers in this Q just to make it
• 6:49 - simple so to get started let's just go
• 6:52 - ahead and start off with that type we'll
• 6:54 - call it a Q and its underlying type will
• 6:57 - be a struct and then inside of that
• 6:58 - struck there'll be a slice of integers
• 7:01 - so that slice of integers is going to
• 7:04 - you know be what stores are actual items
• 7:07 - inside the Q now with different
• 7:10 - implementations people might keep track
• 7:12 - of things such as you know which index
• 7:14 - is the front of the queue which index is
• 7:15 - the back of the queue and things like
• 7:16 - that but because slices can be resized
• 7:19 - dynamically we actually don't need to
• 7:21 - keep track of that we can just assume
• 7:22 - that index 0 is the front of the queue
• 7:25 - and we can assume that you know whatever
• 7:27 - the last spot in the slice is is the
• 7:29 - back of the queue
• 7:31 - so the next thing we need to do is we
• 7:34 - need to write functions that help us and
• 7:36 - Q and D Q items so we're going to need
• 7:38 - func
• 7:40 - will go NQ first and this will take in
• 7:44 - an integer and it will just add it to
• 7:47 - the queue add I to the queue so we'll
• 7:52 - just go ahead and write a comment of
• 7:53 - your NQ adds the integer provided to the
• 7:57 - back of the queue
• 8:03 - and we'll make this it to do and then
• 8:07 - we're going to need to also write a DQ
• 8:10 - function and this is not going to take
• 8:13 - any arguments but it's just going to
• 8:14 - return an integer which is the front so
• 8:18 - we're going to say DQ returns the first
• 8:21 - item in the queue
• 8:26 - or panics if there isn't one
• 8:31 - so this last bit the panicking part I'm
• 8:35 - not going to put any error checks in
• 8:36 - this so if you try to DQ from a queue
• 8:39 - that doesn't have any more items you're
• 8:41 - going to get an index out of bounds
• 8:42 - error and it's going to panic in your
• 8:44 - program will crash so one way to fix
• 8:46 - that would be to change its return type
• 8:48 - from int to int comma error and to
• 8:51 - return an error when that happens but we
• 8:53 - won't be doing that now because I just
• 8:54 - want to sort of explain how this works
• 8:56 - so you can see it and then you can sort
• 8:58 - of add that stuff as you go to do return
• 9:02 - the first item in the queue I need to
• 9:06 - change this definition so it returns the
• 9:08 - first item in the queue and removes that
• 9:11 - item from the queue all right so return
• 9:17 - the first item from the queue then we
• 9:18 - need another to remove the first item
• 9:21 - from the queue so this DQ is gonna have
• 9:24 - to do two different things return the
• 9:26 - first item and remove it so you could
• 9:28 - technically consider that the same thing
• 9:30 - but you know it's nice to sort of
• 9:32 - separate them into two little tasks that
• 9:33 - we have to accomplish
• 9:36 - all right so we don't have a return
• 9:38 - statement here so let's what we'll come
• 9:41 - back to that for now we're just going to
• 9:42 - put return zero just so we get rid of
• 9:45 - the air now we're going to go up to the
• 9:47 - NQ function and this is the first one
• 9:49 - we're going to cover so whenever we want
• 9:51 - to add a new item to our queue we know
• 9:53 - we want to add it to the back of the
• 9:55 - queue the upside to this is that Q dot
• 9:58 - slice allows us to access the slice that
• 10:00 - we're using and one thing that's really
• 10:03 - nice about this is that when you call a
• 10:04 - pend with a slice as the first argument
• 10:06 - and a value is the second argument it
• 10:08 - always adds that value to the end of the
• 10:10 - queue or to the end of the slice sorry
• 10:13 - so in this case we can actually use Q
• 10:15 - dot slice equals append Q dot slice
• 10:17 - comma I and this will add the new item
• 10:20 - to the back of our slice which is also
• 10:21 - the back of our queue so that's all we
• 10:24 - actually have to write you know to add
• 10:26 - this new item to our slice so that makes
• 10:29 - things really easy and it also means
• 10:31 - that when we're adding items to this
• 10:32 - slice that we aren't going to have to
• 10:34 - rearrange everything inside of our slice
• 10:36 - and we don't run into this order n
• 10:38 - complexity whenever we're adding two
• 10:39 - items
• 10:42 - the next thing we want to do is DQ which
• 10:45 - is two steps first we need to return the
• 10:47 - first item in the queue so let's just
• 10:48 - handle that first so we'll say of our
• 10:51 - rat and so rat is going to be the value
• 10:54 - or returning and we're going to say it
• 10:56 - equals Q dot slice and we want
• 10:59 - whatever's at index zero because the
• 11:01 - front of our slice is the front of our
• 11:02 - queue
• 11:04 - so that's all we need to do and
• 11:06 - technically you could do ret : equals
• 11:08 - and that would do the same thing
• 11:12 - so we've got this now we just need to
• 11:15 - make sure that we return ret at the end
• 11:16 - of our code so we we've got this to do
• 11:20 - done we are getting the first item in
• 11:22 - our slice and then we're returning it so
• 11:24 - I do want to also mention that I'm
• 11:26 - getting the value up here before I
• 11:28 - remove the item because it's a lot
• 11:30 - easier to get the value out of the slice
• 11:31 - before it's removed from the slice and
• 11:34 - then we return it at the very end so the
• 11:36 - next thing we need to do is we need to
• 11:38 - remove the first item from the queue so
• 11:41 - we need to do Q dot slice equals now we
• 11:44 - want the slice from index 1 to however
• 11:47 - long it was
• 11:50 - so to do that you do Q dot slice 1 : Len
• 11:56 - of Q dot slice -1
• 12:03 - actually I'm take that back if you want
• 12:07 - length of the slice or length minus one
• 12:08 - but we'll just test it this way then we
• 12:10 - can move from there
• 12:12 - pretty sure we want this
• 12:16 - all right so now we just need to test
• 12:19 - this there are different ways to test it
• 12:20 - we could write a test we could write a
• 12:22 - main function you know whatever sort of
• 12:25 - makes the most sense to you I'm going to
• 12:27 - just use a main function for now because
• 12:29 - we are inside of you know a main package
• 12:33 - and it's just easier to just sort of let
• 12:35 - you see all the code right now so I'm
• 12:37 - going to say VAR q q equals new q and
• 12:44 - we're going to Q dot n q will add one
• 12:48 - two three
• 12:49 - and the mole sorry will DQ it and we'll
• 12:58 - also print out the Q so we're going to
• 13:01 - in Q an item print out the Q and then
• 13:03 - print out whatever the value we get back
• 13:04 - from D queuing is so let's just run that
• 13:07 - first and see what happens
• 13:11 - all right so you can see here that it
• 13:14 - looks like it's working correctly when
• 13:16 - we print out the Q we're getting this
• 13:18 - line here and that looks a little bit
• 13:20 - weird the reason you're getting that is
• 13:22 - because we've got a struct a pointer to
• 13:23 - our struct and then inside of that is a
• 13:25 - slice so one way to sort of clean that
• 13:27 - up
• 13:28 - is to write a string function so we'll
• 13:35 - do format s print and we'll do Q dot
• 13:38 - slice so we're just basically telling it
• 13:40 - to use you know whatever you'd normally
• 13:42 - print out for a slice that's what we're
• 13:44 - going to go ahead and print out for this
• 13:45 - entire Q structure so it'll just make
• 13:47 - things a little bit nice when we run our
• 13:49 - code you can see here that this looks
• 13:51 - like an array now or a slice and you
• 13:53 - know we've got the one two three is the
• 13:55 - value that's being DQ'd so let's just go
• 13:58 - ahead and add a couple in Q's
• 14:03 - we'll add 43 wide 99 so now we want to
• 14:10 - just go ahead and DQ a couple items and
• 14:13 - maybe we'll you know ink you another one
• 14:14 - in the middle of here just to sort of
• 14:16 - see how that works
• 14:18 - all right and then we'll go ahead and
• 14:20 - run this so we've got 123 $43.99 so we
• 14:24 - in queued 123 we include 43 and we
• 14:27 - include 99 so that order looks to be
• 14:29 - correct the left-hand side is the front
• 14:31 - of our queue and this mewling this
• 14:33 - output and then when we DQ we get the
• 14:35 - front item that's the 1 2 3 so that's
• 14:37 - the second line here on 34 so that's
• 14:40 - correct and then we print out the entire
• 14:43 - queue we've got 43 and 99 left and that
• 14:45 - looks like it's correct so it looks like
• 14:46 - our DQ function was actually correct we
• 14:48 - wanted the length of the slice here you
• 14:51 - can see what happens if we were to
• 14:52 - change this you can see here that it's
• 14:55 - pulling two of it we're losing that last
• 14:57 - item in the slice whenever we do minus
• 14:59 - one so that wasn't actually correct and
• 15:01 - it also eventually leads to a runtime
• 15:03 - error so we definitely don't want the
• 15:05 - minus one that we want the slice from 1
• 15:07 - to whatever the length of the queue is
• 15:12 - so going back to running this um you can
• 15:16 - see here we've got 43 99 then we DQ 43
• 15:18 - then we NQ 101 and then we print out the
• 15:21 - Q that's why you're seeing the 101
• 15:23 - suddenly and then we DQ the 99 so
• 15:26 - there's still a 101 left on that Q
• 15:28 - because we never DQ'd it but then our
• 15:30 - program exits all right so that's
• 15:32 - everything we needed for Q you know I
• 15:36 - don't want to go into too much other
• 15:37 - details about it but that should give
• 15:39 - you a rough idea of how Q works and how
• 15:41 - to code it the last thing I'm going to
• 15:44 - talk about is something that I don't
• 15:46 - want to go into too much detail but if
• 15:48 - you've ever heard somebody talk about
• 15:49 - generics and how go doesn't have them
• 15:52 - what they're referring to is structures
• 15:54 - like a queue in other languages like
• 15:56 - Java there'd be a way to do something
• 15:58 - like a T here and then you could use a T
• 16:03 - here so this looks really weird at first
• 16:05 - so I'm going to go ahead and explain
• 16:06 - that whenever this happens usually
• 16:09 - what's happening is you're saying that
• 16:10 - you want like a Q equals new Q and then
• 16:14 - you might say it or even if you did
• 16:17 - integer or something like that so what
• 16:18 - you're saying is that you can
• 16:19 - dynamically define this datatype for the
• 16:22 - nested type so this T type is dynamic
• 16:24 - and that's you know that's usually where
• 16:27 - generics come into play is they're
• 16:28 - really nice for writing a cue structure
• 16:30 - once and then being able to use it with
• 16:32 - any single data type so this is not
• 16:35 - valid code code so I'm just going to put
• 16:36 - this not valid go code um but basically
• 16:42 - I wanted to show you this because this
• 16:44 - is one of those cases where it would be
• 16:47 - nice to have generics like this and I'm
• 16:48 - not advocating for them and go I get why
• 16:50 - they're not there but whenever people
• 16:52 - talk about it it's because they don't
• 16:54 - want to have to rewrite this Q
• 16:55 - implementation for every different data
• 16:57 - type but since Co does not have generics
• 16:59 - instead what we need to do is write aq
• 17:02 - for different types of data and you so
• 17:06 - this one right here only works for
• 17:07 - integers and then you might write
• 17:08 - another one for another data type or the
• 17:11 - other thing you could do is make this an
• 17:13 - interface a slice of interfaces and then
• 17:16 - for all of these values we could just
• 17:18 - say interface
• 17:20 - and you know down here this is going to
• 17:23 - return an interface so the downside of
• 17:26 - this is that we then have to you know
• 17:27 - turn our values back into the right type
• 17:29 - and you know we have to do a little bit
• 17:31 - of type checking and stuff like that
• 17:33 - which is kind of annoying so that's why
• 17:35 - you know people generally like the type
• 17:37 - safe version
• 17:41 - so enough of the downsides of of you
• 17:45 - know go and how generics would be
• 17:47 - helpful I don't want to sort of bog you
• 17:48 - down with that I just wanted to sort of
• 17:50 - mention it because it's something that I
• 17:51 - do think will come up here when people
• 17:53 - are asking you know do I have to write
• 17:55 - this for every single time you know for
• 17:57 - every single data type that I want to
• 17:58 - use and the short answer is I would
• 18:00 - suggest just going ahead and writing
• 18:02 - this it's not a lot of code it's only
• 18:04 - like 20 lines of code and you could
• 18:06 - easily you know put these into packages
• 18:08 - so you can have a cue package so let's
• 18:10 - say we made this the cue package and
• 18:12 - then we could name this the instruct so
• 18:14 - whenever you want to use it let me go
• 18:17 - ahead and grab all these
• 18:23 - so whenever you want to use this the way
• 18:26 - you would normally use it in this
• 18:27 - package we don't have to do it because
• 18:28 - we're inside of the same package but
• 18:30 - let's say we were inside of a different
• 18:31 - package you might do something like
• 18:33 - queue int and you know that that's what
• 18:36 - you're making is this is your new type
• 18:37 - so while it seems we were to call it int
• 18:40 - calling it Q dot n makes it a little bit
• 18:42 - more clear that you know it's from the Q
• 18:44 - package so the int type from the Q
• 18:45 - package is probably an integer Q so
• 18:48 - that's why you'll sometimes see data
• 18:50 - types named things like this it's
• 18:52 - because whenever you stick them inside
• 18:53 - of a package like you it becomes pretty
• 18:55 - clear in the context what it's for if
• 18:59 - you enjoyed this video and you want to
• 19:01 - check out some of my other work you can
• 19:03 - find pretty much everything that I work
• 19:05 - on @ww Calhoun CO and if you join my
• 19:09 - mailing list I will send you an email
• 19:10 - probably about once a week that just
• 19:12 - sort of lets you know what new stuff I'm
• 19:14 - publishing and you know you can just
• 19:16 - keep in touch with new content that I'm
• 19:17 - creating I also have a course that
• 19:20 - teaches web development let go you can
• 19:22 - find that at wwu s Galang com
• 19:25 - so if you could check this two out I'd
• 19:26 - really appreciate it