CS计算机代考程序代写 prolog data structure Java ITI 1121. Introduction to Computing II – subtitle

ITI 1121. Introduction to Computing II – subtitle

ITI 1121. Introduction to Computing II
Stack: linked elements

by

Marcel Turcotte

Version February 9, 2020

Preamble

Preamble

Overview

Stack: linked elements

We implement a stack using linked elements.

General objective:
This week you will be able to implement a stack using linked elements.

Preamble

Learning objectives

Learning objectives

Implement a stack using linked elements.
Compare the implementations using arrays and linked elements of a stack.

Readings:
Pages 75-83, 157-159 of E. Koffman and P. Wolfgang.

2 38

Preamble

Plan

Plan

1 Preamble

2 Implementation using linked elements

3 Prologue

3 38

Implementation using linked elements

Implementation of a stack using
linked elements

Implementation using linked elements

Reminder

On the implementation of a stack using an
array

Access to the elements of an array is very fast, it always requires a constant
number of operations.
However, since arrays have a fixed size, there are some applications for which they
are not appropriate.
A frequently used technique to get around this limitation is to copy the elements of
the array into a new, larger array and replace the old one with the new one (dynamic
arrays).
On the other hand, this makes the insertions more expensive (compared to the
execution time because you have to copy all the elements of the old array to the new
one) and memory usage is increased because the physical size of the data structure
will generally be larger than its logical size.

5 38

Implementation using linked elements

Motivation

Linked structures

Let’s now consider an implementation always using an amount of memory proportional
to the number of elements contained in the structure.

p

13:00 14:30

These structures are efficient, in terms of execution time (for some operations),
because they avoid copying elements.
The structures considered here are linear, i.e. each element has a predecessor and a
successor (except for the first and last element).
Unlike array-based data structures, the elements in those structures are not
contiguous in memory.

6 38

Implementation using linked elements

Experimentation

The class Elem

Consider the following declaration ∗:
c l a s s Elem {

E v a l u e ;
Elem next ;

}

What’s so special about the definition of Elem?
The instance variable next is a reference to an object of the class Elem.
Is it valid?
Try it for yourself!
> javac Elem.java

Yes, it’s valid, although it does seem circular.

∗The issue of the visibility of variables will be addressed shortly..

7 38

What’s that for?

Declaring a variable of type Elem:
Elem

Create an object of the class Elem:
new Elem

8 38

What’s that for?

Save the reference in the variable p..
Elem

Notation: I will always use circles to represent the objects of the class Elem. The top
part represents the instance variable value while the bottom part represents the variable
next.

9 38

What’s the point?

p

How do we change the content of the instance variable value of the newly created
object?

p

13:00

We use the dot-notation in order to access the attributes of the object.

10 38

What’s that for?

Create a new object of the class Elem.
new Elem

13:00

p

How do you link the elements together?

11 38

What’s that for?

p

13:00

The variable next of the object designated by the reference variable p receives the
reference of the newly created object Elem.

12 38

What’s that for?

p

13:00

Change the contents of the variable value of the newly created object.

13 38

What’s that for?

Create a new object of the class Elem.
new Elem

p

13:00 14:30

How do we link this element to the others?

14 38

What’s that for?

p

14:3013:00

Change the content of the variable value of the newly created object.

15 38

What’s that for?

p

13:00 14:30 16:00

p . nex t . nex t = p ;

What does the above statement do?

16 38

What’s that for?

p . nex t . nex t = p ;

A circular structure has been created!
The last item is no longer accessible;
It’ll be picked up by the garbage collector (System.gc()).

⇒ This is the basis of the linked structures: informations (values) are linked to each
other by links (references).

17 38

Implementation using linked elements

Linked structures

Linked strutures

c l a s s Elem {
E v a l u e ;
Elem next ;

}

Linked data structures, such as this one, allow us:
to represent linear data structures, such as stacks, queues and lists;
they always use a quantity of memory proportional to the number of elements;
all this is made possible because the class declares an instance variable whose type is
a reference to an object of the same class.

⇒ When the structures are linear like these, we talk about (singly) linked lists.

18 38

Summary

Linked structures are an alternative to arrays for saving values.
They always use a quantity of memory proportional to the number of elements
saved since each element is saved in its container, an object of the class Elem. Each
container is linked to the next one by a reference variable.
For now, we limit ourselves to linear structures, but graphs or trees are also
possible.

19 38

Implementation using linked elements

Constructor

Constructor

This is the usual constructor of the class Elem:
pub l i c c l a s s Elem {

E v a l u e ;
Elem next ;

Elem (E va lue , Elem next ) {
t h i s . v a l u e = v a l u e ;
t h i s . nex t = next ;

}
}

20 38

and the usual usage,

p = new Elem(“A” , nu l l ) ;

“A”

p

q = new Elem(“B” , p ) ;

“A””B”

p

q

Implementation using linked elements

Implementing the Stack interface

Implementing a Stack using linked elements

pub l i c c l a s s LinkedStack implements Stack {

pub l i c boolean empty ( ) {

}
pub l i c vo id push (E o ) {

}
pub l i c E peek ( ) {

}
pub l i c E pop ( ) {

}
}

What are the instance variables?

22 38

Implementation using linked elements

Instance variables

What are the instance variables?

23 38

Which of the following two strategies is preferable?

top

s

63 2

bottom

s

36 2

6

2

3

Discussion

25 38

Implementation using linked elements

Nested class

Class Elem and encapsulation principle

The visibility of the instance variables is not acceptable. It is a violation of the
principle of encapsulation.

What options do we have?

26 38

pub l i c c l a s s Elem {

p r i v a t e E v a l u e ;
p r i v a t e Elem next ;

pub l i c Elem (E va lue , Elem next ) {
t h i s . v a l u e = v a l u e ;
t h i s . nex t = next ;

}
pub l i c vo id s e t V a l u e (E v a l u e ) {

t h i s . v a l u e = v a l u e ;
}
pub l i c vo id s e tNex t ( Elem next ) {

t h i s . nex t = next ;
}
pub l i c E getVa lue ( ) {

re tu rn v a l u e ;
}
pub l i c Elem getNext ( ) {

re tu rn next ;
}

}

Java: nested class

28 38

Java: nested

Elem is a nested class of the class LinkedStack.
Although the visibility of the class and its variables is private, the class LinkedStack
has access to the instance variables of the class Elem because its implementation is
nested.
For now, the nested classes will be “static”. We will use them as if they were
top-level classes except that 1) the declaration is nested and 2) the implementation is
accessible to the outside class.
Later we will see that there is a second category of nested classes.

29 38

Implementation using linked elements

Implementation of the methods

boolean isEmpty()

top

s

63 2

30 38

E peek()

top

s

63 2

31 38

void push(E value)

top

s

63 2

32 38

E pop()

top

s

63 2

33 38

Prologue

Summary

The concept of reference variable is central to linked implementations.
The class Elem has two instance variables, one of them is used to save an element of
information, the other one is used as a tether for the next element of the list.

35 38

Next module

Error handling in Java: Exception

36 38

References I

E. B. Koffman and Wolfgang P. A. T.
Data Structures: Abstraction and Design Using Java.
John Wiley & Sons, 3e edition, 2016.

37 38

Marcel Turcotte
Marcel.

School of Electrical Engineering and Computer Science (EECS)
University of Ottawa

38 / 38

Marcel.

Preamble
Overview
Learning objectives
Plan

Implementation using linked elements
Reminder
Motivation
Experimentation
Linked structures
Constructor
Implementing the Stack interface
Instance variables
Nested class
Implementation of the methods

Prologue