ITI 1121. Introduction to Computing II – subtitle
ITI 1121. Introduction to Computing II
Stack: concept
by
Marcel Turcotte
Version February 3, 2020
Preamble
Preamble
Overview
Overview
Stack: concept
We’re interested in all aspects of stacks in programming. A stack is an abstract data
type similar to physical stacks. It’s a linear data structure such that the access to the
data is only from one end, called the top of the stack, and textbfone element at a time.
General objective :
This week you’ll be able to describe a stack.
1 60
Preamble
Learning objectives
Learning objectives
Describe the stack concept in computer science.
Justify the role of a stack in solving a computer problem.
Implement a stack using an array.
Readings:
Pages 147-150 of E. Koffman and P. Wolfgang.
2 60
Preamble
Plan
Plan
1 Pr[Pleaseinsertintopreamble]ambule
2 Théorie
3 Implémentation à l’aide d’un tableau
4 Prologue
3 60
Theory
Theory
Discussion
Discussion
Discuss the implementation of mechanisms to undo and redo operations in a text
editor?
What information do you need to save?
In what order is this information saved and accessed?
What do these mechanisms have in common with those of a browser software
allowing the return to a previous or already visited URL address?
4 60
Theory
Definition
Theory
A stack is an abstract data type similar to physical stacks.
Books
Plates
Trays
PEZ
The analogy with the plate dispenser found in a cafeteria is particularly interesting,
because access is limited to the top item and you have to remove the top plates
one by one in order to access the bottom ones.
5 60
Definition
A stack is a linear data structure such that the data is accessed from only one end, called
the top of the stack, and one element at a time.
This structure is often called LIFO, from “ last-in first-out ”.
“alpha” “alpha”
“bravo”
“alpha”
s = new StackImpl() s.push(“alpha”) s.push(“bravo”) s.pop()
6 60
Theory
Applications
Applications
Stacks are the data structures behind the following applications :
the development of compilers, and the analysis of formal languages in general;
the implementation of backtracking algorithms used by automatic theorem proving
systems, game algorithms and artificial intelligence;
memory management during program execution;
support “ undo ” operations in word processing programs or the “ back ” button on
your Internet browser.
7 60
Theory
Operations
Operations
The basic operations are :
push: add an item on the stack
pop: remove and return the top element
isEmpty: check that the stack is empty.
8 60
Abstract data type (ADT)
pub l i c i n t e r f a c e Stack
E push (E elem ) ;
E pop ( ) ;
E peek ( ) ;
boolean i sEmpty ( ) ;
}
As we saw in the last lesson, the interface can receive a parameter of type!
9 60
c l a s s Mystery {
pub l i c s t a t i c vo id main ( S t r i n g [ ] a r g s ) {
Stack
s t a c k = new Stack Imp lementa t ion
f o r ( i n t i =0; i s ;
s = new ArrayStack () ;
s = new DynamicArrayStack() ;
s = new LinkedStack () ;
15 60
Discussion
One of the proposed implementations uses an array, why don’t we just use an
array to design algorithms? What are the advantages?
16 60
Implementation using an array
Instance variables
Implementation using an array :
ArrayStack
What are the instance variables?
A reference to an array
What are the types of elements in this array?
A type parameter («generics»)
17 60
Implementation using an array
Strategy
Implementation using an array :
strategy
What will be the strategy for saving items in the stack?
In what order will you save the items?
Where to add a new element (push) and which element to remove (pop)?
Take a few moments to strategize.
18 60
Implementation using an array :
order of elements
In what order should the elements be added?
Is that important?
“alpha”
“bravo”
“charlie”
elems
“charlie”
“bravo”
“alpha”
0 1 2 3 4 5 6 7 elems
“alpha”
“bravo”
“charlie”
0 1 2 3 4 5 6 7
19 60
Implementation using an array :
bottom on the right
What do you think about it?
elems
“charlie”
“bravo”
“alpha”
0 1 2 3 4 5 6 7 elems
“charlie”
“bravo”
“alpha”
“delta”
0 1 2 3 4 5 6 7
20 60
Implementation using an array :
finding an empty cell
Proposal. How do you feel about that?
The method push visits each cell of the array, from left to right, and inserts the new
element in the first cell whose value is null.
The method pop visits each cell of the table, from right to left, and removes the
element in the first cell whose value is not null.
21 60
Implementation using an array :
ArrayStack
Ideally, the stack should memorize the index of the rightmost occupied cell.
In object-oriented programming, how does an object, in this case a stack, remember
a value?
22 60
Summary
We use an array to save the stack elements.
The order of the elements is important.
The top element will be the one on the more right.
We need two instance variables.
One of them is a reference to an array
The other variable allows us to determine the location of the top element.
23 60
Implementation using an array:
top
Does the variable top designate the top element or the empty cell following the top
element?
What’s the type for this variable?
elems
top
“alpha”
“bravo”
“charlie”
2
0 1 2 3 4 5 6 7
elems
top
3
0 1 2 3 4 5 6 7
“alpha”
“bravo”
“charlie”
24 60
Adding an element when top designates top
element
What are the steps for adding an element?
elems
top
“alpha”
“bravo”
“charlie”
2
0 1 2 3 4 5 6 7
25 60
The variable top contains the index to top
element.
What is the value of top if the stack is empty?
elems
top
“alpha”
“bravo”
“charlie”
2
0 1 2 3 4 5 6 7
26 60
Adding an element when top designates the
empty cell that follows the element on top
What are the steps for adding an element?
elems
top
3
0 1 2 3 4 5 6 7
“alpha”
“bravo”
“charlie”
27 60
The variable top designates the empty cell
that follows the top element
What is the value of top if the stack is empty?
elems
top
3
0 1 2 3 4 5 6 7
“alpha”
“bravo”
“charlie”
28 60
Remove an element when top designates the
number of elements
What are the steps for removing an item?
elems
top
3
0 1 2 3 4 5 6 7
“alpha”
“bravo”
“charlie”
29 60
What do you think?
elems
top
3
0 1 2 3 4 5 6 7
“alpha”
“bravo”
“charlie”
elems
top
2
0 1 2 3 4 5 6 7
“alpha”
“bravo”
“charlie”
elems
top
1
0 1 2 3 4 5 6 7
“alpha”
“bravo”
“charlie”
elems
top
0
0 1 2 3 4 5 6 7
“alpha”
“bravo”
“charlie”
30 60
Implementation using an array
Memory leaks
Memory leak
Steps for removing an element :
Decrementing the value of top
Save in a local (temporary) variable the element of the array located at the position
designated by top.
Set the value null to the position of the array designated by top.
Returning the saved value
The proposed approach leads to memory leaks!
Indeed, the garbage collector cannot reclaim the memory space associated with the
accessible objects.
What solution do you propose?
31 60
Implementation using an array
Java implementation
Designing a generic type :
ArrayStack
Examples of stack usage:
Stack
name = new ArrayStack
Stack
s1 . push ( ” a lpha ” ) ;
s2 . push (new Time ( 23 ,0 ,0 ) ) ;
S t r i n g a ;
a = s1 . pop ( ) ;
32 60
Implementation using an array :
ArrayStack
Java implementation of a stack using an array.
Here, top refers to the empty cell that follows the top element.
The implementation where top designates the top element is left as an exercise.
33 60
Implementation using an array :
ArrayStack
34 60
Implementation using an array :
ArrayStack
35 60
Give the implementation of the constructor that will produce the memory diagram below:
elems
top
0
0 1 2 3 4 5 6 7
Give the memory diagram corresponding to the execution of the constructor below:
pub l i c c l a s s ArrayStack implements Stack {
p r i v a t e E [ ] e l ement s ;
p r i v a t e i n t top ;
pub l i c ArrayStack ( i n t c a p a c i t y ) {
top = 0 ;
}
}
Arrays and generics
38 60
Arrays and generics
In order for programs to run on virtual machines of previous generations (before
1.5), we cannot create arrays with generic element types.
We still have a problem to solve.
39 60
Arrays and generics
Solution :
pub l i c c l a s s ArrayStack
p r i v a t e E [ ] e l ems ;
p r i v a t e i n t top ;
pub l i c ArrayStack ( i n t c a p a c i t y ) {
e lems = (E [ ] ) new Object [ c a p a c i t y ] ;
top = 0 ;
}
// . . .
Alas, this solution will produce a warning when compiling.
Note: ArrayStack.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
40 60
Arrays and generics
Local directives to remove a warning at compile time :
pub l i c c l a s s ArrayStack
p r i v a t e E [ ] e l ems ;
p r i v a t e i n t top ;
@SuppressWarnings ( ” unchecked ” )
pub l i c ArrayStack ( i n t c a p a c i t y ) {
e lems = (E [ ] ) new Object [ c a p a c i t y ] ;
top = 0 ;
}
// . . .
Which is preferable to global warning suppression!
> javac -Xlint:unchecked ArrayStack.java
41 60
ArrayStack
42 60
ArrayStack
43 60
ArrayStack
44 60
ArrayStack
45 60
ArrayStack : isEmpty()
46 60
ArrayStack : isEmpty() (take 2)
47 60
ArrayStack : E peek()
48 60
Implementation using an array
Dynamic arrays
Weakness of our implementation
Our implementation has a major weakness, what is it?
Its size is fixed!
Create a very large array so that it is of sufficient size for a large number of
applications.
Memory’s being wasted!
Doesn’t work for some applications!
49 60
Dynamics arrays
Some programming languages allow us to change the size of the arrays when running
programs. These languages use the technique below.
When the array is full.
Create a new, larger array
Copy the elements from the original array to the new one.
Make the reference the variable elements designate the new array
A multitude of strategies exist to determine the size of the new array, including
these:
n′ = n + c, where n′ is the size of the new array and n is the size of the old one, c is a
constant
n′ = n × c
Of course, you can also reduce the size of the array dynamically according to the
needs of the application.
50 60
Implementation using an array
Pitfall
Pitfall!
pub l i c c l a s s ArrayStack
// I n s t a n c e v a r i a b l e s
p r i v a t e E [ ] e l ems ;
p r i v a t e i n t top ;
// C o n s t r u c t o r
pub l i c ArrayStack ( i n t c a p a c i t y ) {
E [ ] e l ems = (E [ ] ) new Object [ c a p a c i t y ] ;
top = 0 ;
}
// Retu rns t r u e i f t h i s Ar rayStack i s empty
pub l i c boolean i sEmpty ( ) {
re tu rn top == 0 ;
}
// . . .
}
51 60
Pitfall
52 60
100capacity
elems
this
0
elems
top
Working memory
for ArrayStack
ArrayStack
object
formal parameter(s)
local variable(s)
100capacity
elems
this
0
elems
top
Activation Frame
for ArrayStack
ArrayStack
object
formal parameter(s)
local variable(s)
Pitfall
55 60
100capacity
elems
this
0
elems
top
Activation Frame
for ArrayStack
ArrayStack
object
formal parameter(s)
local variable(s)
Prologue
Summary
A stack is used when you want to process the elements in reverse order.
There are two main implementations : using an array and using linked elements.
57 60
Next module
Stack : applications
58 60
References I
E. B. Koffman and Wolfgang P. A. T.
Data Structures: Abstraction and Design Using Java.
John Wiley & Sons, 3e edition, 2016.
59 60
Marcel Turcotte
Marcel.
École de science informatique et de génie électrique (SIGE)
Université d’Ottawa
60 / 60
Marcel.
Preamble
Overview
Learning objectives
Plan
Theory
Discussion
Definition
Applications
Operations
Implementation using an array
Instance variables
Strategy
Memory leaks
Java implementation
Dynamic arrays
Pitfall
Prologue