COMP 250
INTRODUCTION TO COMPUTER SCIENCE
Week 7-1 : Stacks
Giulia Alberini, Fall 2020 Slides adapted from Michael Langer’s
WHAT ARE WE GOING TO DO IN THIS VIDEO?
Stacks
ABSTRACT DATA TYPE (ADT)
An ADT is a model for a data type. It defines a data type by its behavior from the user’s perspective only. It describes the possible values and the set of possible operations on the data type.
It ignores the details of the implementation.
An ADT is more abstract than a data structure. A data structure is a concrete representation of data which includes the implementation details.
LIST ADT
get(i) set(i, e) add(i, e) remove(i) remove(e)
clear() isEmpty()
size() :
// Returns the i-th element (but doesn’t remove it) // Replaces the i-th element with e
// Inserts element e into the i-th position
// Removes the i-th element from list
// Removes first occurrence of element e // from the list (if it is there)
// Empties the list.
// Returns true if empty, false if not empty. // Returns number of elements in the list
These operations can be defined abstractly, without specifying the implementation details of the data structure (e.g. arraylist, or linked list)
STACK ADT
push(element) pop( )
isEmpty( ) peek( )
A stack is a list. However, it typically does not have operations to access the list element i directly. Instead one accesses only the element at one end of the list.
HOW TO IMPLEMENT A STACK?
array list
singly linked list doubly linked list
push(e) pop ()
HOW TO IMPLEMENT A STACK?
push(e) pop ()
array list
singly linked list doubly linked list
*Java ArrayList class doesn’t have addLast and removeLast methods
addLast(e) removeLast()
HOW TO IMPLEMENT A STACK?
push(e) pop ()
array list
singly linked list doubly linked list
*Why not use addLast and removeLast with singly linked lists?
addLast(e) removeLast() addFirst(e) removeFirst()
HOW TO IMPLEMENT A STACK?
push(e) pop ()
addLast(e) removeLast() addFirst(e) removeFirst()
either row above
array list
singly linked list doubly linked list
EXAMPLE 1: STACK OF INT
push(3), push(6), push(4), push(1), pop(), push(5), pop(), pop(),…
15 44444 6666666
33333333
–
time
EXAMPLE 1: STACK OF INT
push(3), push(6), push(4), push(1), pop(), push(5), pop(), pop(),…
15 44444 6666666 3333333
-3
time
EXAMPLE 1: STACK OF INT
push(3), push(6), push(4), push(1), pop(), push(5), pop(), pop(),…
15 44444 666666 333333
6 -33
time
EXAMPLE 1: STACK OF INT
push(3), push(6), push(4), push(1), pop(), push(5), pop(), pop(),…
1 44 666 -3333
time
5 444
6666 3333
EXAMPLE 1: STACK OF INT
push(3), push(6), push(4), push(1), pop(), push(5), pop(), pop(),…
1 444
6666 -33333
time
5
44 666 333
EXAMPLE 1: STACK OF INT
push(3), push(6), push(4), push(1), pop(), push(5), pop(), pop(),…
15 4444 66666 -333333
time
4 66 33
EXAMPLE 1: STACK OF INT
push(3), push(6), push(4), push(1), pop(), push(5), pop(), pop(),…
15 44444 6666666
-33333333 time
EXAMPLE2 -BALANCINGPARENTHESES
e.g. ( ( [ ] ) ) [ ] { [ ] }
To ensure proper nesting, we traverse the list and use a stack. How?
EXAMPLE2 -BALANCINGPARENTHESES
e.g. ( ( [ ] ) ) [ ] { [ ] }
To ensure proper nesting, we traverse the list and use a stack.
How? When we reach a left parenthesis, we push it onto the stack.
When we reach a right parenthesis, we compare it to top of the stack. If it matches, then we pop, otherwise we found an error.
EXAMPLE2 -BALANCINGPARENTHESES
e.g. ( ( [ ] ) ) [ ] { [ ] }
[ (( (((
([ (([{{{
EXAMPLE2 -BALANCINGPARENTHESES
e.g. ( ( [ ] ) ) [ ] { [ ] }
[ (((
((((
[ ([{{{
EXAMPLE2 -BALANCINGPARENTHESES
e.g. ( ( [ ] ) ) [ ] { [ ] }
[ (((
(((((_
[
[ {{{
EXAMPLE2 -BALANCINGPARENTHESES
e.g. ( ( [ ] ) ) [ ] { [ ] }
[ (((
(((((_[
[ _{{{
EXAMPLE2 -BALANCINGPARENTHESES
e.g. ( ( [ ] ) ) [ ] { [ ] }
[ (((
(((((_[_
etc
[ {{{
EXAMPLE2 -BALANCINGPARENTHESES
e.g. ( ( [ ) ) ) [ ] { [ ] }
Does not match left bracket on top of stack.
[ (( (((
([ (([{{{
BALANCING PARENTHESES – PSEUDOCODE
Algorithm: decide if parentheses are matched.
while (there are more tokens) { // We refer to brackets as “tokens”. This is the token = get next token // more general term using in string parsing.
if token is a left parenthesis
push(token)
else { // token is a right parenthesis
if stack is empty return false
else {
pop left parenthesis from stack
if popped left parenthesis doesn’t match the right parenthesis
return false
} }
}
return stack.empty // true if stack is empty, false if not.
EXAMPLE 3: HTML TAGS
Supposed you’d like to write the following sentence:
I am bold. I am italic
In html, you would write:
I am bold. < i > I am italic. < /i >
HTML ELEMENTS
An HTML element starts with a start tag. An HTML element ends with an end tag.
HTML documents consist of nested HTML elements.
I am bold I am italic
These tags can be thought of as brackets.
EXAMPLE 3: HTML TAGS
Suppose you want:
What if you were to write the following ?
I am bold. I am bold and italic. I am italic.
I am bold. I am bold and italic. I am italic.
EXAMPLE 3: HTML TAGS
Suppose you want:
What if you were to write the following ?
I am bold. I am bold and italic. I am italic.
This is officially incorrect, because elements are not nested.
I am bold. I am bold and italic. I am italic.
Error: mismatch between Most web browsers will interpret it correctly, however.
____
EXAMPLE 3: HTML TAGS
Suppose you want:
The correct way to write it is:
I am bold. I am bold and italic. I am italic.
I am bold. I am bold and italic. I am italic.
< b > < b > < b > < i>
EXAMPLE 3: HTML TAGS
What problems can arise if you write it incorrectly?
Suppose you are editing a html document that contains the following:
… Hello. I am bold.
I am bold and italic. I am italic. < /i > Bla bla bla ……
Q: What happens if you delete the middle line?
EXAMPLE 3: HTML TAGS
What problems can arise if you write it incorrectly?
Suppose you are editing a html document that contains the following:
… Hello. I am bold.
I am bold and italic. I am italic. < /i > Bla bla bla ……
Q: What happens if you delete the middle line? A: … Hello. I am bold. Bla bla bla ……
EXAMPLE4: STACKSINGRAPHICS
Define a ‘programming language’ for drawing simple figures like this:
EXAMPLE4: STACKSINGRAPHICS
Define a pen position and direction 𝑥, 𝑦, 𝜃 where 𝜃 is clockwise degrees
from x axis.
𝑦
1,1,90
0,0,0
𝑥
The initial state of the pen is (0, 0, 0).
EXAMPLE4: STACKSINGRAPHICS
Let instructions be symbols :
D – draw unit length line in direction 𝜃 (changes 𝑥, 𝑦 ) R – turn right 90 degrees (changes 𝜃 )
L – turn left 90 degrees (changes 𝜃 )
[ – pushstate 𝑥,𝑦,𝜃
] – pop state, and go to that state
EXAMPLE4: STACKSINGRAPHICS
The initial state of the pen is (0, 0, 0).
D- draw
R – turnright
D D RD L D
(0, 0)
L – turn left
[ – pushstate ] – pop state
EXAMPLE4: STACKSINGRAPHICS
The initial state of the pen is (0, 0, 0).
D D RD L D
D- draw
R – turnright
(0, 0)
(2, 0)
L – turn left
[ – pushstate ] – pop state
EXAMPLE4: STACKSINGRAPHICS
The initial state of the pen is (0, 0, 0).
D- draw
R – turnright
D D RD L D
(0, 0)
(2, -1)
(2, 0)
L – turn left
[ – pushstate ] – pop state
EXAMPLE4: STACKSINGRAPHICS
The initial state of the pen is (0, 0, 0).
D- draw
R – turnright
D D RD L D
(0, 0)
(2, 0) (2, -1)
(3, -1)
L – turn left
[ – pushstate ] – pop state
The final pen state is (3, -1, 0).
EXAMPLE4: STACKSINGRAPHICS
The initial state of the pen is (0, 0, 0).
D D [ RD L D]
D- draw
R – turnright
(0, 0)
(2, -1)
(2, 0)
L – turn left
[ – pushstate ] – pop state
Q: What will be the final pen state?
(3, -1)
EXAMPLE4: STACKSINGRAPHICS
The initial state of the pen is (0, 0, 0).
D D [ RD L D]
D- draw
R – turnright
(0, 0)
(2, -1)
(2, 0)
L – turn left
[ – pushstate ] – pop state
Q: What will be the final pen state? A: (2, 0, 0)
(3, -1)
EXAMPLE4: STACKSINGRAPHICS
The initial state of the pen is (0, 0, 0). D D [ RD L D] L DR D
(0, 0)
(2, -1)
Q: What will be the final pen state?
(2, 0)
D- draw
R – turnright
L – turn left
[ – pushstate ] – pop state
(3, -1)
EXAMPLE4: STACKSINGRAPHICS
The initial state of the pen is (0, 0, 0). D D [ RD L D] L DR D
(3, 1)
(2, 0)
D- draw
R – turnright
L – turn left
[ – pushstate ] – pop state
(2, -1)
Q: What will be the final pen state? A: (3, 1, 0)
(3, -1)
(0, 0)
EXAMPLE4: STACKSINGRAPHICS
The initial state of the pen is (0, 0, 0).
(0, 0)
(2, -1)
(3, 1)
(2, 0)
(3, -1)
D- draw
R – turnright
L – turn left
[ – pushstate ] – pop state
Q: What if we add brackets at the beginning and at the end? [ D D [ R DL D] L DR D ]
EXAMPLE4: STACKSINGRAPHICS
The initial state of the pen is (0, 0, 0).
(0, 0)
(2, -1)
(3, 1)
(2, 0)
(3, -1)
D- draw
R – turnright
L – turn left
[ – pushstate ] – pop state
Q: What if we add brackets at the beginning and at the end? [ D D [ R DL D] L DR D ]
A: (0, 0, 0)
EXAMPLE5: “CALLSTACK”
class Demo {
void mA(){
mB();
mC(); }
void mB() { … }
void mC() { … }
public static void main(String[] args){
mA();
} }
EXAMPLE5: “CALLSTACK”
class Demo {
void mA(){
mB();
mC(); }
void mB() { … }
void mC() { … }
mB mC
mA mA mA mA mA
main main main main main main main
public static void main(String[] args){
mA();
} }
Eclipse debug mode
TestSLinkedList1’s main() method calls addLast() method of SLinkedList class.
breakpoint in the SLinkedList1.addLast() method
call stack
OVERFLOW AND UNDERFLOW
Stack overflow
It happens if a stack has a finite capacity, and we attempt to push.
Stack underflow
It happens if when a stack is empty we attempt to pop.
In the next video: Queues