DATA STRUCTURES AND ADVANCED PROGRAMMING
BASIC DATA STRUCTURES
CS062
DATA STRUCTURES AND ADVANCED PROGRAMMING
11: Stacks and Queues
Alexandra Papoutsaki she/her/hers
Some slides adopted from Princeton C0S226 course or Algorithms, 4th Edition
TODAY'S LECTURE IN A NUTSHELL
2
Lecture 11: Stacks and Queues
Stacks Queues Applications Java Collections
Some slides adopted from Algorithms 4th Edition and Oracle tutorials
STACKS
3
Stacks
Dynamic linear data structures. Elements are inserted and removed following the LIFO paradigm. LIFO: Last In, First Out.
Remove the most recent element. Similar to lists, there is a sequential nature to the data.
Metaphor of cafeteria plate dispenser. Want a plate? Pop the top plate. Add a plate? Push it to make it the new top. Want to see the top plate? Peek. We want to make push and pop as time ef cient as possible.
if
STACKS
4
Example of stack operations
push To be or not to - be -
- that -
-
- is
pop
to
be not
that or be
push to top pop from top
Last
to
be
not not not not not
that
In
or or or or or or or or or
First
be be be be be be be be be be
Out
To To To To To To To To To To To
be
is
To To To
STACKS
5
Implementing stacks with ArrayLists
Where should the top go to make push and pop as ef cient as
possible?
The end/rear represents the top of the stack. To push an element add(E element).
Adds at the end. Amortized O+(1).
To pop an element remove().
Removes and returns the element from the end. Amortized O+(1).
To peek get(size()-1).
Retrieves the last element. O(1).
If the front/beginning were to represent the top of the stack, then:
Push, pop would be O(n) and peek O(1).
if
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- data structures and advanced programming
- inheritance polymorphism and interfaces
- a comparative study of java obfuscators ng tang
- distribution of execution times for sorting algorithms
- chapter 9 polymorphism lab exercises
- radix sorting princeton university
- performance comparison of different sorting algorithms
- comparison sorting algorithms
- sorting umass amherst
- sorting algorithms princeton university
Related searches
- american structures and design
- brain structures and their functions
- brain structures and functions worksheet
- subcortical structures and their functions
- us government structures and institutions
- academic essay structures and format
- structures and functions of the brain
- cerebral structures and function
- market structures and their characteristics
- body structures and functions answers
- supply chain structures and relationships
- circulatory system structures and functions