Transcript Stacks and Queues - Computing Science

Stacks and Queues
Introduction to Computing
Science and Programming I
Data Structures


Data structures are different structures
that can be used to store data. Different
structures will organize it differently
causing differences in how the data is
accessed and changed.
The only data structure we’ve used in
Python is the list.
Abstract Data Type


We’re going to talk about a couple abstract data
types. We’re only going to look at them in a
very general, abstract way. We won’t worry
about details of how to implement the structures
in Python. We will only discuss how the data is
organized and what operations can be
performed on it.
The structures can be used in any programming
language.
Queues



A queue is a simple data structure that is
works similar to a line of people (a queue)
waiting to be helped by a cashier.
You can only add or remove items one at
a time.
It is a First In First Out, FIFO data
structure. The first item you put in will be
the first item that leaves the queue.
Queues
\ ---------------------------- /
Entrance ->
-> Exit
/ --------------------------- \

Every queue has to basic operations.



queue(Item) adds the item to the queue
dequeue() removes an item from the queue
Some operations that many queues have, but aren’t
required.



size() number of elements in the queue
isEmpty() check whether there are any items
peek() Look at the next item to be removed without removing it
Queues
\ ---------------------------- /
Entrance ->
5 10 8 -> Exit
/ --------------------------- \

This is what the queue would look like after the following
operations.




queue(8)
queue(10)
queue(5)
If the items we’re removed using the dequeue operation,
they would be returned in the order they were put it, 8,
then 10, and finally 5.
Queues


Remember that these queues and any
other structure can store numbers,
strings, or objects of any kind.
Applications of the queue have to do with
resource management and requests. For
example if you send several documents to
be printed, they will be put in a queue
before being printed one at a time in the
order they were added.
Stacks


A stack is a simple data structure that
works similarly to a stack of papers. You
can only add elements to the top and also
only remove them from the top.
This makes it a Last In First Out, LIFO,
structure because the last item added will
be the first one removed.
Stacks
Enter ->

Every stack has to basic operations.



|
|
|
|
|
|
-------
-> Exit
push(Item) adds the item to the top of the stack, “pushing” the others
down
pop() removes an item from the top of the stack
Some operations that many stacks have, but aren’t required.



size() number of elements in the stack
isEmpty() check whether there are any items
peek() Look at the next item to be removed without removing it
Stacks
Enter ->

This is what the stack would look like after the following operations.




-> Exit
| 5
|
| 10
|
| 8
|
----------
push(8)
push(10)
push(5)
If the items we’re removed using the pop operation, they would be
returned in the reverse of the order they were put it, 5, then 10,
and finally 8.
Stacks

Stacks are used in a wide array of
applications. They can be used to
evaluate equations as well as keep track
of function calls in a program that is
running.