Transcript Stacks and Queues

A data structure is a type of data
storage ….similar to an array.
There are many data structures in
Java (Stacks, Queues, LinkedList,
Sets, Maps, HashTables, Trees).
Our discussion of data structures will
be limited to Stacks and Queues.


Stack: collection of items with "last in first out"
retrieval
Queue: collection of items with "first in first
out" retrieval
 A data structure for maintaining data. Data goes in
and out of the "top."
 Has a specific set of operations that can be
performed on the data.
 Referred to as a LIFO data structure because of the
last-in, first-out organization.
 Implemented as a class. An array is one way to store
the data.

Allows insertion and removal of elements
only at one end






Traditionally called the top of the stack
New items are added to the top of the stack
Items are removed at the top of the stack
Called last in, first out or LIFO order
Traditionally, addition and removal operations
are called push and pop
Think of a stack of books
A Stack of Books
top:
Returns the last value added to the
stack
pop:
Removes and returns the last value
added to the stack
push:
Adds an item to the top of the stack
isEmpty:
Returns true when there are no items
on the stack
size:
Returns the number of items on the
stack
makeEmpty: Removes all the items on the stack





Add items to one end of the queue (the tail)
Remove items from the other end of the
queue (the head)
Queues store items in a first in, first out or
FIFO fashion
Items are removed in the same order in
which they have been added
Think of people lining up

People join the tail of the queue and wait until
they have reached the head of the queue
 A data structure for maintaining data. Data goes in
the "rear" and out the "front."
 Has a specific set of operations that can be
performed on the data.
 Referred to as a FIFO data structure because of the
First-in, first-out organization.
 Implemented as a class. An array is one way to store
the data.
front:
Returns the first value added to the
queue
dequeue:
Removes and returns the first value
added to the queue
enqueue:
Adds an item to the rear of the queue
isEmpty:
Returns true when there are no items
in the queue
size:
Returns the number of items in the
queue
makeEmpty: Removes all the items in the queue
Figure 13:
A Queue

Queue



Event queue of all events, kept by the Java GUI
system
Queue of print jobs
Stack

Run-time stack that a processor or virtual
machine keeps to organize the variables of
nested methods