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

f o r ( i n t i =0; i <10; i ++) { q . enqueue ( I n t e g e r . va lueOf ( i ) ) ; } whi le ( ! q . i sEmpty ( ) ) { System . out . p r i n t l n ( q . dequeue ( ) ) ; } } } Prints? 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. 7 54 q = new LinkedQueue(); q.enqueue(a); q.enqueue(b); q.enqueue(c); q.dequeue(); -> a
q.dequeue();
-> b
q.enqueue(d);
q.dequeue();
-> c
q.dequeue();
-> d

The elements are processed in the same order as they were inserted in the queue,
here the element a is the first to join the queue and it is also the first to leave the
queue (first-come first-serve).

Implementation

Implementation

Like stacks, there are two families of implementations:
Linked lists;
With the help of an array.

9 54

Implementation using linked elements

pub l i c c l a s s LinkedQueue implements Queue {

pub l i c boolean i sEmpty ( ) { . . . }
pub l i c vo id enqueue (E o ) { . . . }
pub l i c E dequeue ( ) { . . . }

}

10 54

Implementation

Elem

Implementation using linked elements

pub l i c c l a s s LinkedQueue implements Queue {

p r i v a t e s t a t i c c l a s s Elem {
p r i v a t e T v a l u e ;
p r i v a t e Elem next ;
p r i v a t e Elem (T 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 boolean i sEmpty ( ) { . . . }
pub l i c vo id enqueue (E o ) { . . . }
pub l i c E dequeue ( ) { . . . }

}

11 54

Implementation

Instance variables

Implementation using linked elements

pub l i c c l a s s LinkedQueue implements Queue {

p r i v a t e s t a t i c c l a s s Elem {
p r i v a t e T v a l u e ;
p r i v a t e Elem next ;
p r i v a t e Elem (T 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 ;

}
}

p r i v a t e Elem f r o n t ; // r e a r ?

pub l i c boolean i sEmpty ( ) { . . . }
pub l i c vo id enqueue (E o ) { . . . }
pub l i c E dequeue ( ) { . . . }

}

12 54

Implementation using linked elements

Which representation do you think is preferable and why?

front

DB CA

rear

AC BD

13 54

Discussion

If we choose the first implementation, then the removal of an element will be easy
(and fast) but the adding at the rear of the queue will be difficult (and slow).
The other implementation just reverses the situation, the removal becomes costly
while adding is fast.
Is it a dead end?
What is needed to facilitate removal?
What is needed to facilitate adding?

14 54

Implementation using linked elements

15 54

Implementation using linked elements
Will these two implementations be equally efficient?

rear

AC BD

front

front

DB CA

rear

16 54

Discussion

What will be the impact of this change?
The amount of extra memory is negligible.
The implementation of the methods will be more complex.

17 54

Implementation

Methodology

Methodology

Identify the general case as well as the special case.
General case, consider a sufficient number of elements so that it represents the
majority of the cases.
Special cases are cases where the strategy employed for the general case would not
work.
Queues, stacks, and lists that are empty or that have an element are often the
special cases.

18 54

Adding an element (general case)

front

B CA

rear

19 54

Adding an element (general case)

front

B CA

rear

newElem

The use of a local variable will make the job easier.

20 54

Adding an element (general case)

front

DB CA

rear

newElem

21 54

Adding an element (general case)

front

DB CA

rear

newElem

22 54

Adding an element (general case)

front

DB CA

rear

newElem

23 54

Adding an element (general case)

front

DB CA

rear

newElem

24 54

Adding an element (general case)

front

DB CA

rear

25 54

Adding an element (special case)

Draw the memory diagram representing the empty queue.

What expression is used to identify the empty queue?

26 54

Adding an element (special case)

front

rear

newElem

27 54

Adding an element (special case)

front

A

rear

newElem

28 54

Adding an element (special case)

front

A

rear

newElem

29 54

Adding an element (special case)

front

A

rear

newElem

30 54

Adding an element (special case)

front

A

rear

newElem

31 54

Adding an element (special case)

front

A

rear

32 54

Methodology: removing an element

Identify the general case as well as the special case(s).
Is the empty queue a special case?

No, this is a illegal case, for which we’ll need to throw an exception.
The queue containing only one element is the special case.

33 54

Removal of an element (general case)

front

DB CA

rear

first second

saved

34 54

Removal of an element (general case)

front

DB CA

rear

first second

saved

35 54

Removal of an element (general case)

front

DB C

A

rear

first second

saved

36 54

Removal of an element (general case)

front

DB C

A

rear

first second

saved

37 54

Removal of an element (general case)

front

DB C

A

rear

first second

saved

38 54

Removal of an element (general case)

front

DB C

A

rear

first second

saved

39 54

Removal of an element (general case)

front

DB C

A

rear

first second

saved

40 54

Removal of an element (general case)

front

DB C

rear

41 54

Removal of an element (special case)

front

D

rear

first

saved

What expression can be used to recognize a queue containing only one element?
what do you think of the following?

f r o n t == r e a r

42 54

Removal of an element (special case)

43 54

Removal of an element (special case)

front

D

rear

first

saved

44 54

Removal of an element (special case)

front

D

rear

first

saved

45 54

Removal of an element (special case)

front

D

rear

first

saved

46 54

Removal of an element (special case)

front

D

rear

first

saved

47 54

Removal of an element (special case)

front

D

rear

first

saved

48 54

Removal of an element (special case)

front

D

rear

first

saved

49 54

Piège

Pitfall!

front

D

rear

Here’s a common problem. The link to the rear element hasn’t been severed.
What kinds of problems might arise?
What will happen if we use the following expression to detect the empty queue?
front == null && rear == null.

50 54

Prologue

Summary

A queue is a linear abstract data type such that adding data is done at one end,
the rear of the queue, and removing at the other, the front.
The linked implementation requires a reference to the front element as well as the
rear element.

51 54

Next module

Queue : applications

52 54

References I

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

53 54

Marcel Turcotte
Marcel.

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

54 / 54

Marcel.

Preamble
Overview
Learning objectives
Plan

Definitions
Implementation
Elem
Instance variables
Methodology

Pi[Please insert \PrerenderUnicode{è} into preamble]ge
Prologue