Tip:
Highlight text to annotate it
X
- The STL provides three distinct types of queues.
The stack object provides a last-in first-out or LIFO queue, where you push and pop items
from the same side of the queue, and items are removed in the reverse order from which
they were inserted.
The queue object provides a first-in, first-out or FIFO queue, where you push and pop from
opposite sides of the queue, and items are removed in the same order in which they were
inserted.
The double-ended queue object, pronounced deck, can push and pop from either side, allowing
you to control the order in which items are inserted and removed.
Let's take a look at how these work.
We'll start with the stack class.
Here I have a working copy of stack.cpp from chapter 10 of the exercise files.
A stack is what's called a container adapter, and it does not have iterators.
If you need iterators, you want to use the container type directly.
What a container adapter does is, it takes another container, and it adapts it for a
particular use.
And so, in this case you notice I start with a list container, and then I initialize the
stack from that list.
So, stack is a container adapter, and it's adapting that list to its own uses.
So, I'm going to go ahead and build and run this, and then we'll step through it and see
what it does.
So, you notice that my list is a list of integers, li, and my stack is a stack of integers from
that li.
And so, li has a size, and si has a size, and they're exactly the same.
And now when I pop everything from si, li still has all five of its entries, and si
has none, because si is actually making a copy of the list.
It's not using the list directly.
So, when I pop the items from the stack container, the pop method doesn't actually return the
value.
The value is returned from the top method before, and so, if I want to actually see
the things that I'm popping from it, I can use top to access that element before I pop
it, which is what I'm doing here.
And you notice that our list still has all of its entries after the stack has been emptied,
because it initialized it from a list.
I can also use the default stack, which actually uses the deque object, and we'll get to the
deque object later in this lesson.
And so, here's a stack using a default object, a default container, and it's a stack of strings,
and I add things to the stack by pushing elements on one by one.
And so, here I pushed five elements onto ss, and my size is five, right there, and then
I popped the elements, accessing them with top first.
And you notice that they come out in the opposite order that they go in.
That's because the stack is a last-in, first-out, or LIFO type of a queue.
So, that's the stack object.
We're going to go ahead and delete our working copy, and I'm going to grab the queue.cpp
instead.
I'm going to run clean and build and run.
And so, queue is a first-in, first-out, or FIFO queue.
It's also a container adapter, and so the same thing applies.
I can initialize it from a list like here, or I can use the default queue, which again
is the deque queue, and we'll get to that next.
And so, this works exactly like the stack, except that it pops the elements in the reverse
order.
Well, actually, it pops them from the end of the queue.
So, they come out in the same order that they go in.
And so, in this case you'll notice when I call pop, I'm getting the elements in the
same order that they were in the list, and when I use the string version, I push one,
two, three, four, five, and they come out one, two, three, four, five, in the same order
that I put them in.
Other than that, this works exactly the same as the stack.
So, I'm going to go ahead and delete that one, and we're going to take the deque object.
Deque stands for double-ended queue, and so it's spelled like that, but it's typically
pronounced deck.
I'm going to go ahead and clean and run.
And so, this is a double-ended queue.
And so, you can push onto the back, you can push onto the front, and you can pop from
the front, or you can pop from the back.
And so, here I'm just pushing all of these elements from the back.
And so, they're coming out in order, one, two, three, four, five, six, seven, eight,
nine, ten, and my front is one, and my back is ten.
I can access them with an iterator like that.
I can pop from the front, and when I pop from the front, you notice that one of the elements
in the front is gone.
I can pop from the back, using pop back, and one of the elements from the back is gone.
I can push front.
There's a new front.
And I can push back, and there's a new back.
And so, you can push and pop from both ends of a double-ended queue or a deque.
So, the STL stack and queue classes are container adapters.
They take an underlying container, and they adapt it to last-in, first-out or first-in,
first-out queue.
The default container that they'll use, if you don't specify one, is actually the deque
queue, and that'll be used as a default container, if you don't specify one for stack and queue.
The deque class is a complete double-ended queue with random access iterator, and it's
useful for many needs, where a LIFO or a FIFO queue is not enough.
So, let's delete this working copy, and I'll run clean to get us prepared for the next
lesson.