1 of 70

Dynamic Data Structures (Pt.3)

C. Papachristos

Robotic Workers Lab

University of Nevada, Reno

CS-202

2 of 70

Course , Projects , Labs:

​

​

​

​

Your 8th Project Deadline is this Wednesday 4/15.

​

  • PASS Sessions held as announced, get all the help you need!

  • 24-hrs delay after Project Deadline incurs 20% grade penalty.
  • Past that, NO Project accepted. Better send what you have in time!

Monday

Tuesday

Wednesday

Thursday

Friday

​

Sunday

 

 

 

Lab (8 Sections)

 

​

​

 

CLASS

PASS

Session

CLASS

 

​

​

PASS

Session

​

Project DEADLINE

NEW Project

 PASS

Session

​

 PASS

Session

Course Week

CS-202 C. Papachristos

3 of 70

Today’s Topics

CS-202 C. Papachristos

Dynamic Data Structures

​

“Container Adaptors”

​

Queues(s)

​

  • Array-based
  • Node-based

​

​

4 of 70

Queue(s)

CS-202 C. Papachristos

The Basics

​

A Dynamic Data Structure type, with its own semantics.

  • “Adapts” the interface of a Container used for its backend.

​

An ordered group of homogeneous items.

  • Has two ends, a front and a back.

​

Operational semantics:

  • Elements are added at the back (rear).
  • Elements are removed from the front (start).
  • Middle elements are inaccessible.

5 of 70

Queue(s)

CS-202 C. Papachristos

The Basics

​

A Dynamic Data Structure type, with its own semantics.

​

Operational semantics (continued):

  • First-In, First-Out (FIFO) property.
  • The first element added first, is the first to be removed.

6 of 70

Queue(s)

CS-202 C. Papachristos

Applications

​

Queues are appropriate to handle for many real-world situations:

  • Example: Waiting lists.

In bureaucracy - A line to be served at the DMV.

​

Queues have numerous computer (science)-related applications:

  • Example: Access to shared resources.

For a CPU – Concurrent programming (Note: Not the same as Multi-threading)

For a printer – Serving a request to print a document.

​

Cross-field simulations & case-studies:

7 of 70

Queue(s)

CS-202 C. Papachristos

Queue Operations

​

A complete Queue-based ADT implementation has to support the following functionalities:

  • Creation of an empty Queue.
  • Destroying a Queue.
  • Determining whether a Queue is empty.
  • Adding (at the back) a new element to the Queue.
  • Removal (from the front) of the item that was added earliest.
  • Retrieval of the earliest added item (at the front).

​

8 of 70

Queue empty()

​

bool empty() const;

/** Determines whether the queue is empty.

* @return True if the queue is empty, otherwise false.

*/

​

​

Queue Operations

CS-202 C. Papachristos

?

?

?

?

Data

…

…

Next

…

Data

…

…

Next

# 0

Data

…

…

Next

# N

Non-empty Queue: false

Empty Queue: true

Back

Front

Back

Front

N/A

N/A

N/A

?

9 of 70

Queue Operations

CS-202 C. Papachristos

Queue push()-ing

​

When a new element needs to be added to the queue:

  • New people enter at the end of the line.
  • New service requests made to a server.

​

Called an “enqueue” operation (also push, append, etc.)

Data

…

…

Next

# N

Data

…

…

Next

# N-1

Data

…

…

Next

…

Data

…

…

Next

# 0

Data

…

…

Next

?

Back

N/A

Front

10 of 70

Queue Operations

CS-202 C. Papachristos

Queue push()-ing

​

void push(const DataType & value);

/** Inserts an element at the back of a queue.

* @param value The value of the element to be inserted.

* @post If the insertion is successful, a new DataType element of value is at the back of the queue.

*/

Data

…

…

Next

# N-1

Data

…

…

Next

# N-2

Data

…

…

Next

…

Data

…

…

Next

# 0

Data

…

…

Next

# N

Back

N/A

Front

11 of 70

Queue Operations

CS-202 C. Papachristos

Queue pop()-ping

​

When an element needs to be removed from the queue:

  • Front-of-line person goes away.
  • A service request has been completed.

​

Called an “dequeue” operation (also pop, remove, etc.)

Data

…

…

Next

# N-1

Data

…

…

Next

…

Data

…

…

Next

# 1

Data

…

…

Next

# 0

Data

…

…

Next

Front

Back

N/A

# N

12 of 70

Queue pop()-ing

​

void pop();

/** Dequeues the front of a queue.

* @post If the queue is not empty, the element that was added to the queue earliest is deleted.

*/

Queue Operations

CS-202 C. Papachristos

Data

…

…

Next

# N-1

Data

…

…

Next

…

Data

…

…

Next

# 0

?

?

?

?

Data

…

…

Next

Front

N/A

Back

?

# N

13 of 70

Queue Operations

CS-202 C. Papachristos

Queue front()

​

When the front element needs to be accessed:

  • Get front-of-line person to teller.
  • Acquire service request to forward for execution.

​

Called an “getFront” operation (also front, first etc.)

Data

…

…

Next

# N-1

Data

…

…

Next

…

Data

…

…

Next

# 1

Data

…

…

Next

# 0

Data

…

…

Next

# N

N/A

Front

Back

14 of 70

Queue front()

​

DataType & front();

const DataType & front() const;

/** Retrieves the element at the front of a queue

* @pre The queue is not empty.

* @return If the queue is not empty, the return value is a (const) reference to the earliest added element. Otherwise result is undefined.

*/

Queue Operations

CS-202 C. Papachristos

Data

…

…

Next

# N-1

Data

…

…

Next

…

Data

…

…

Next

# 1

Data

…

…

Next

# 0

Data

…

…

Next

# N

N/A

Front

Back

15 of 70

Queue front()

​

DataType & front();

const DataType & front() const;

/** Retrieves the element at the front of a queue

* @pre The queue is not empty.

* @return If the queue is not empty, the return value is a (const) reference to the earliest added element. Otherwise result in undefined.

*/

Queue Operations

CS-202 C. Papachristos

?

?

?

?

Remember: From the C++11 standard:

[dcl.ref] [...] a NULL reference cannot exist in a well-defined program, because the only way to create such a reference would be to bind it to the “object” obtained by dereferencing a NULL pointer, which causes �undefined behavior.

  • Have to return a valid Object reference.
  • Have to first check that the queue is not empty!

N/A

Front

?

16 of 70

Queue Operations

CS-202 C. Papachristos

Queue back() (outside of specifications)

​

When the last element needs to be accessed:

  • Get last-in-line person’s details.
  • Peek at the expected load of the last-in-line service request.

​

Called an “getBack” operation (also back, last, etc.)

Data

…

…

Next

# N

Data

…

…

Next

…

Data

…

…

Next

# 1

Data

…

…

Next

# 0

Data

…

…

Next

# N-1

Front

Back

N/A

17 of 70

Queue back() (outside of specifications)

​

DataType & back();

const DataType & back() const;

/** Retrieves the element at the end of a queue

* @pre The queue is not empty.

* @return If the queue is not empty, the return value is a (const) reference to the earliest added element. Otherwise result is undefined.

*/

Queue Operations

CS-202 C. Papachristos

Data

…

…

Next

# N

Data

…

…

Next

…

Data

…

…

Next

# 1

Data

…

…

Next

# 0

Data

…

…

Next

# N-1

Front

Back

N/A

18 of 70

Queue back() (outside of specifications)

​

DataType & back();

const DataType & back() const;

/** Retrieves the element at the end of a queue

* @pre The queue is not empty.

* @return If the queue is not empty, the return value is a (const) reference to the last added element. Otherwise result is undefined.

*/

Queue Operations

CS-202 C. Papachristos

Remember: From the C++11 standard:

[dcl.ref] [...] a NULL reference cannot exist in a well-defined program, because the only way to create such a reference would be to bind it to the “object” obtained by dereferencing a NULL pointer, which causes undefined behavior.

  • Have to return a valid Object reference.
  • Have to first check that the queue is not empty!

?

?

?

?

Back

?

19 of 70

Queue Implementations

CS-202 C. Papachristos

“Standard” Implementations

​

A complete Queue-based ADT implementation encompasses a subset of “Sequential Container” ADT functionalities.

  • A Queue is a “Container Adaptor” and can have :

  • A pointer to the front element.
  • A pointer to the back element.
  • An Array-based backend / implementation.
  • A List (Node)-based backend / implementation.

A Linked-List with two-ended access :

20 of 70

Circular Array-based Queue(s)

CS-202 C. Papachristos

Circular Array Implementation(s)

​

A Queue can be implemented with an array, as shown here.

​

  • An array of ints to hold an represent a Queue of ints.

​

  • This Queue contains the integers 4 (at the front), 8 and 6 (at the rear).

​

  • We do not care about any elements other than those three.

​

​

The “valid” array elements subset.

These array elements do not concern the program at this point.

int

4

int

8

int

6

m_arr [0]

m_arr [1]

m_arr [2]

int

…

m_arr […]

int

…

m_arr [3]

int

…

m_arr [98]

int

…

m_arr [99]

21 of 70

Circular Array-based Queue(s)

CS-202 C. Papachristos

Circular Array Implementation(s)

​

A Queue can be implemented with an array, as shown here.

​

The “easiest” implementation keeps track of:

  • The number of elements in the Queue.
  • The index of the front (first) element.
  • The index of the back (last) element.

And “remembers”:

  • The underlying container’s (the array’s) total capacity.

​

m_size := 3

​

m_front := 0

​

m_back := 2

m_capacity := 100

int

4

int

8

int

6

int

…

m_arr [0]

m_arr [1]

m_arr [2]

m_arr [98]

int

…

m_arr [99]

int

…

m_arr […]

int

…

m_arr [3]

22 of 70

m_size := 2

​

m_front := 1

​

m_back := 2

m_capcaity := 100

Circular Array-based Queue(s)

CS-202 C. Papachristos

Circular Array Implementation(s)

​

A Queue pop() (dequeue) operation – Naïve approach.

​

When an element is removed from the Queue:

  • The size is decremented.
  • The front is changed.

​

int

4

int

8

int

6

m_arr [0]

m_arr [1]

m_arr [2]

int

…

m_arr […]

int

…

m_arr [3]

Note:

pop() does not clear contents, it only updates the�Queue values that keep track of its state.

int

…

m_arr [98]

int

…

m_arr [99]

23 of 70

m_size := 3

​

m_front := 1

​

m_back := 3

m_capacity := 100

Circular Array-based Queue(s)

CS-202 C. Papachristos

Circular Array Implementation(s)

​

A Queue push() (enqueue) operation – Naïve approach.

​

When an element is pushed to the Queue:

  • The size is incremented.
  • The back is changed.

​

int

4

int

8

int

6

m_arr [0]

m_arr [1]

m_arr [2]

int

…

m_arr […]

int

9

m_arr [3]

Note:

push(…) overwrites contents, and also updates the�Queue values that keep track of its state.

int

…

m_arr [98]

int

…

m_arr [99]

24 of 70

Circular Array-based Queue(s)

CS-202 C. Papachristos

Circular Array Implementation(s)

​

Queue Naïve approach issues.

​

For a sequence of operations: ADADADADADADADADA... (A:Add, D: Delete)

int

4

int

8

int

6

m_arr [0]

m_arr [1]

m_arr [2]

int

…

m_arr [4]

int

9

m_arr [3]

int

…

m_arr […]

int

…

m_arr [99]

int

4

int

8

int

6

m_arr [0]

m_arr [1]

m_arr [2]

int

…

m_arr [4]

int

9

m_arr [3]

int

…

m_arr […]

int

…

m_arr [99]

int

4

int

8

int

6

m_arr [0]

m_arr [1]

m_arr [2]

int

13

m_arr [4]

int

9

m_arr [3]

int

…

m_arr […]

int

…

m_arr [99]

25 of 70

Circular Array-based Queue(s)

CS-202 C. Papachristos

Circular Array Implementation(s)

​

Queue Naïve approach issues.

​

For a sequence of operations: ADADADADADADADADA... (A:Add, D: Delete)

int

4

int

8

int

…

m_arr [0]

m_arr [1]

m_arr […]

int

11

m_arr [97]

int

2

m_arr [96]

int

5

m_arr [98]

int

…

m_arr [99]

int

4

int

8

int

…

m_arr [0]

m_arr [1]

m_arr […]

int

11

m_arr [97]

int

2

m_arr [96]

int

5

m_arr [98]

int

…

m_arr [99]

int

4

int

8

int

…

m_arr [0]

m_arr [1]

m_arr […]

int

11

m_arr [97]

int

2

m_arr [96]

int

5

m_arr [98]

int

1

m_arr [99]

26 of 70

Circular Array-based Queue(s)

CS-202 C. Papachristos

Circular Array Implementation(s)

​

Queue Naïve approach issues.

​

  • Eventually m_back index points to last array position m_capacity-1.
  • Looks like the underlying array space is up (can’t push(…) more elements).
  • In reality: Queue only has two or three elements, array is empty in front.

int

4

int

8

int

…

m_arr [0]

m_arr [1]

m_arr […]

int

11

m_arr [97]

int

2

m_arr [96]

int

5

m_arr [98]

int

1

m_arr [99]

???

m_size := 3

​

m_front := 97

​

m_back := 99

m_capacity := 100

27 of 70

Circular Array-based Queue(s)

CS-202 C. Papachristos

Circular Array Implementation(s)

​

A “simple” solution – Upon condition of Queue rear overflow:

  • Check value of front, and if there is room,
  • Slide all queue elements toward first array position.
  • Works best with small Queue sizes.

​

int

11

int

5

int

1

m_arr [0]

m_arr [1]

m_arr [2]

int

11

m_arr [97]

int

2

m_arr […]

int

5

m_arr [98]

int

1

m_arr [99]

int

4

int

8

int

…

m_arr [0]

m_arr [1]

m_arr […]

int

11

m_arr [97]

int

2

m_arr [96]

int

5

m_arr [98]

int

1

m_arr [99]

28 of 70

Circular Array-based Queue(s)

CS-202 C. Papachristos

Circular Array Implementation(s)

​

An “elegant” solution – The circular buffer paradigm:

​

char

…

m_arr […]

char

A

m_arr [97]

char

…

m_arr [96]

char

B

m_arr [98]

char

C

m_arr [99]

char

…

char

…

m_arr [0]

m_arr [1]

m_size := 3 m_front := 97

m_capacity := 100 m_back := 99

???

charQueue.push('D');

[99]

[0]

[98]

[1]

[97]

[2]

[…]

[…]

Advance m_back to next circular array position !

m_back = (m_back + 1) % m_capacity;

29 of 70

Circular Array-based Queue(s)

CS-202 C. Papachristos

Circular Array Implementation(s)

​

An “elegant” solution – The circular buffer paradigm:

​

char

…

m_arr […]

char

A

m_arr [97]

char

…

m_arr [96]

char

B

m_arr [98]

char

C

m_arr [99]

char

D

char

…

m_arr [0]

m_arr [1]

char

…

m_arr […]

char

A

m_arr [97]

char

…

m_arr [96]

char

B

m_arr [98]

char

C

m_arr [99]

char

…

char

…

m_arr [0]

m_arr [1]

m_size := 4 m_front := 97

m_capacity := 100 m_back := 0

charQueue.push('D');

[99]

[0]

[98]

[1]

[97]

[2]

[…]

[…]

30 of 70

Circular Array-based Queue(s)

CS-202 C. Papachristos

Circular Array Implementation(s)

​

An “elegant” solution – The circular buffer paradigm:

​

[99]

[0]

[98]

[1]

[97]

[2]

[…]

[…]

Advance m_front to next circular array position !

m_front = (m_front + 1) % m_capacity;

char

A

m_arr [99]

char

B

char

C

char

D

m_arr [0]

m_arr [1]

m_arr [2]

char

???

m_arr [97]

char

???

m_arr […]

char

???

m_arr [98]

m_size := 4 m_front := 99

m_capacity := 100 m_back := 2

???

charQueue.pop();

31 of 70

char

???

Circular Array-based Queue(s)

CS-202 C. Papachristos

Circular Array Implementation(s)

​

An “elegant” solution – The circular buffer paradigm:

​

m_size := 3 m_front := 0

m_capacity := 100 m_back := 2

charQueue.pop();

[99]

[0]

[98]

[1]

[97]

[2]

[…]

[…]

char

A

m_arr [99]

char

B

char

C

char

D

m_arr [0]

m_arr [1]

m_arr [2]

char

???

m_arr [97]

char

???

m_arr […]

char

???

m_arr [98]

m_arr [99]

char

B

char

C

char

D

m_arr [0]

m_arr [1]

m_arr [2]

char

???

m_arr [97]

char

???

m_arr […]

char

???

m_arr [98]

32 of 70

Circular Array-based Queue(s)

CS-202 C. Papachristos

Circular Array Implementation(s)

​

The circular buffer:

​

  • Eliminates issue of rightward drift.

​

​

But:

​

  • Values of m_front and m_back can�no longer directly distinguish alone between�the full-Queue and empty-Queue conditions!

​

​

[99]

[0]

[98]

[1]

[97]

[2]

[…]

[…]

[99]

[0]

[98]

[1]

[97]

[2]

[…]

[…]

[99]

[0]

[98]

[1]

[97]

[2]

[…]

[…]

front

back

front

back

back

front

33 of 70

Circular Array-based Queue(s)

CS-202 C. Papachristos

Circular Array Implementation(s)

​

Circular array issues (continued):

  • Cases with identical front & back index values.

An empty Queue, after a dequeue operation:

m_front := 97 m_back := 97

intQueue.pop();

int

…

int

…

int

…

m_arr [0]

m_arr [1]

m_arr […]

int

11

m_arr [97]

int

…

m_arr [96]

int

…

m_arr [98]

int

…

m_arr [99]

m_front := 98 m_back := 97

int

…

int

…

int

…

m_arr [0]

m_arr [1]

m_arr […]

int

11

m_arr [97]

int

…

m_arr [96]

int

…

m_arr [98]

int

…

m_arr [99]

34 of 70

Circular Array-based Queue(s)

CS-202 C. Papachristos

Circular Array Implementation(s)

​

Circular array issues (continued):

  • Cases with identical front & back index values.

A full Queue, after an enqueue operation:

m_front := 98 m_back := 96

intQueue.push(9);

m_front := 98 m_back := 97

int

11

int

5

int

…

m_arr [0]

m_arr [1]

m_arr […]

int

9

m_arr [97]

int

2

m_arr [96]

int

5

m_arr [98]

int

1

m_arr [99]

int

11

int

5

int

…

m_arr [0]

m_arr [1]

m_arr […]

int

…

m_arr [97]

int

2

m_arr [96]

int

5

m_arr [98]

int

1

m_arr [99]

35 of 70

Circular Array-based Queue(s)

CS-202 C. Papachristos

Circular Array Implementation(s)

​

Circular buffer specifications to detect �full-Queue & empty-Queue conditions:

  • Keep a count of the queue elements (m_size).
  • Increment when new element push’ed.
  • Decrement when element pop’ped.

​

Queue Initialization:

  • Set m_front to 0.
  • Set m_back to m_capacity-1.
  • Set m_size to 0.

[99]

[0]

[98]

[1]

[97]

[2]

[…]

[…]

36 of 70

Circular Array-based Queue(s)

CS-202 C. Papachristos

Circular Array Implementation(s)

​

Queue Insertion (at the back):

if ( !full() ) {

m_back = (m_back+1) % m_capacity;

​

m_arr[m_back] = newElement;

​

++m_size;

}

Queue Removal (from the front):

if ( !empty() ) {

m_front = (m_front+1) % m_capacity;

​

--m_size;

}

Keeping track of Queue size via a helper element-counting variable.

Advancing back & front indexes in the array as data are push’ed & pop’ped.

37 of 70

Circular Array-based Queue(s)

CS-202 C. Papachristos

Circular Array Implementation(s)

​

class ArrayQueue{

public:

ArrayQueue();

ArrayQueue(size_t count, const DataType & val);

ArrayQueue(const ArrayQueue & other);

~ArrayQueue();

​

ArrayQueue & operator=(const ArrayQueue & other);

bool empty() const;

size_t size() const;

void push(const DataType & value);

void pop();

void clear();

DataType & front();

DataType & back();

private:

void resize(size_t count);

DataType * m_arr;

size_t m_front, m_back;

size_t m_size, m_capacity;

};

typedef some-pod-or-class-or-struct-type DataType;

38 of 70

Forward List-based Queue(s)

CS-202 C. Papachristos

List-based Implementation(s)

​

A Queue can be implemented with a Linked List, as shown here.

​

  • a) A Linked–List with 2 (Head & Tail) Pointers: front & back

​

Data

…

…

m_next

0x…

Node 1

Data

…

…

m_next

0x…

Node 0

m_front

Data

…

…

m_next

0x…

Node n

Data

…

…

m_next

0x…

Node …

NULL

m_back

39 of 70

Forward List-based Queue(s)

CS-202 C. Papachristos

List-based Implementation(s) – Uncommon Case

​

A Queue can be implemented with a Linked List, as shown here.

​

  • b) A Circular Linked–List with 1 Pointer: back.

​

Data

…

…

m_next

0x…

Node 1

Data

…

…

m_next

0x…

Node 0

Data

…

…

m_next

0x…

Node n

Data

…

…

m_next

0x…

Node …

m_back

40 of 70

Forward List-based Queue(s)

CS-202 C. Papachristos

List-based Implementation(s)

​

A Queue push() (enqueue) operation.

​

Elements are exclusively pushed to the back of the Queue.

DataType

…

…

m_next

0x…

Node 1

DataType

…

…

m_next

0x…

Node 0

m_front

DataType

…

…

m_next

0x…

Node n

DataType

…

…

m_next

0x…

Node …

NULL

m_back

DataType

…

…

m_next

0x…

Node ?

41 of 70

Forward List-based Queue(s)

CS-202 C. Papachristos

List-based Implementation(s)

​

A Queue push() (enqueue) operation.

​

Elements are exclusively pushed to the back of the Queue.

DataType

…

…

m_next

0x…

Node 1

DataType

…

…

m_next

0x…

Node 0

m_front

DataType

…

…

m_next

0x…

Node n-1

DataType

…

…

m_next

0x…

Node …

NULL

m_back

DataType

…

…

m_next

0x…

Node k

2)

3)

1)

1) Node * newNode_Pt = new Node(Data(…), nullptr);

2) m_back->m_next = newNode_Pt;

3) m_back = newNode_Pt;

42 of 70

Forward List-based Queue(s)

CS-202 C. Papachristos

List-based Implementation(s) – Uncommon Case

​

A Queue push() (enqueue) operation.

​

Elements are exclusively pushed to the back of the Queue.

DataType

…

…

m_next

0x…

Node 1

DataType

…

…

m_next

0x…

Node 0

DataType

…

…

m_next

0x…

Node n-1

DataType

…

…

m_next

0x…

Node …

m_back

DataType

…

…

m_next

0x…

Node ?

DataType

…

…

m_next

0x…

Node n

43 of 70

Forward List-based Queue(s)

CS-202 C. Papachristos

List-based Implementation(s) – Uncommon Case

​

A Queue push() (enqueue) operation.

​

Elements are exclusively pushed to the back of the Queue.

DataType

…

…

m_next

0x…

Node 1

DataType

…

…

m_next

0x…

Node 0

DataType

…

…

m_next

0x…

Node n-1

DataType

…

…

m_next

0x…

Node …

DataType

…

…

m_next

0x…

Node k

DataType

…

…

m_next

0x…

Node n

1) Node * newNode_Pt = new Node(Data(…), m_back->m_next);

2) m_back->m_next = newNode_Pt;

3) m_back = newNode_Pt;

2)

3)

1)

m_back

44 of 70

Forward List-based Queue(s)

CS-202 C. Papachristos

List-based Implementation(s)

​

A Queue push() (enqueue) operation.

​

An originally empty Queue.

NULL

m_front

m_back

DataType

…

…

m_next

0x…

Node n

45 of 70

Forward List-based Queue(s)

CS-202 C. Papachristos

List-based Implementation(s)

​

A Queue push() (enqueue) operation.

​

An originally empty Queue.

NULL

m_front

m_back

DataType

…

…

m_next

0x…

Node n

1) Node * newNode_Pt =� new Node(Data(…), nullptr);

2) m_back = newNode_Pt;

3) m_front = newNode_Pt;

m_back

DataType

…

…

m_next

0x…

Node n

1) Node * newNode_Pt = new Node(Data(…));

2) newNode_Pt->m_next = newNode_Pt;

3) m_back = newNode_Pt;

Uncommon Case

46 of 70

Forward List-based Queue(s)

CS-202 C. Papachristos

List-based Implementation(s)

​

A Queue pop() (dequeue) operation.

​

Elements are exclusively popped from the front of the Queue.

DataType

…

…

m_next

0x…

Node 1

DataType

…

…

m_next

0x…

Node 0

m_front

DataType

…

…

m_next

0x…

Node n

DataType

…

…

m_next

0x…

Node …

NULL

m_back

47 of 70

Forward List-based Queue(s)

CS-202 C. Papachristos

List-based Implementation(s)

​

A Queue pop() (dequeue) operation.

​

Elements are exclusively popped from the front of the Queue.

DataType

…

…

m_next

0x…

Node 1

DataType

…

…

m_next

0x…

Node 0

m_front

DataType

…

…

m_next

0x…

Node n

DataType

…

…

m_next

0x…

Node …

NULL

m_back

del_pt

1) Node * del_pt = m_front;

2) m_front = m_front->m_next;

3) delete del_pt;

2)

3)

1)

48 of 70

Forward List-based Queue(s)

CS-202 C. Papachristos

List-based Implementation(s) – Uncommon Case

​

A Queue pop() (dequeue) operation.

​

Elements are exclusively popped from the front of the Queue.

DataType

…

…

m_next

0x…

Node 1

DataType

…

…

m_next

0x…

Node 0

DataType

…

…

m_next

0x…

Node n

DataType

…

…

m_next

0x…

Node …

m_back

49 of 70

Forward List-based Queue(s)

CS-202 C. Papachristos

List-based Implementation(s) – Uncommon Case

​

A Queue pop() (dequeue) operation.

​

Elements are exclusively popped from the front of the Queue.

DataType

…

…

m_next

0x…

Node 1

DataType

…

…

m_next

0x…

Node 0

DataType

…

…

m_next

0x…

Node n

DataType

…

…

m_next

0x…

Node …

m_back

1) Node * del_pt = m_back->m_next;

2) m_back->m_next = del_pt->m_next;

3) delete del_pt;

DataType

…

…

m_next

0x…

Node 0

del_pt

1)

2)

3)

50 of 70

Forward List-based Queue(s)

CS-202 C. Papachristos

List-based Implementation(s)

​

class ListQueue {

public:

ListQueue();

ListQueue(size_t count, const DataType & val);

ListQueue(const ListQueue & other);

~ListQueue();

​

ListQueue & operator=(const ListQueue & other);

bool empty() const;

size_t size() const;

void push(const DataType & value);

void pop();

void clear();

DataType & front();

DataType & back();

​

private:

Node * m_front;

Node * m_back;

size_t m_size; //tentative

};

typedef some-od-or-class-or-struct-type DataType;

class Node {

friend class ListQueue;

​

public:

Node()

: m_next(nullptr)

{ }

Node(const DataType & data,

Node * next = nullptr)

: m_next(next)

, m_data(data)

{ }

Node(const Node & other)

: m_next(other.m_next)

, m_data(other.m_data)

{ }

​

DataType & data(){

return m_data;

}

const DataType & data() const{

return m_data;

}

private:

Node * m_next;

DataType m_data;

};

51 of 70

Advanced: Queue(s) as Container Adaptors

CS-202 C. Papachristos

Queue Implementation(s)

​

class ArrayQueue{

​

public:

ArrayQueue();

ArrayQueue(size_t count, const DataType & val);

ArrayQueue(const ArrayQueue & other);

~ArrayQueue();

​

ArrayQueue & operator=(const ArrayQueue & other);

bool empty() const;

size_t size() const;

void push(const DataType & value);

void pop();

void clear();

DataType & head();

DataType & tail();

​

​

private:

void resize(size_t count);

DataType * m_arr;

size_t m_head, m_tail;

size_t m_size, m_capacity;

};

class ListQueue {

​

public:

ListQueue();

ListQueue(size_t count, const DataType & val);

ListQueue(const ListQueue & other);

~ListQueue();

​

ListQueue & operator=(const ListQueue & other);

bool empty() const;

size_t size() const;

void push(const DataType & value);

void pop();

void clear();

DataType & front();

DataType & back();

​

​

private:

Node * m_front;

Node * m_back;

size_t m_size; //tentative

};

Difference lies not in�public Interface, but�in private�Implementation !

52 of 70

Advanced: Queue(s) as Container Adaptors

CS-202 C. Papachristos

2 Ways to Refactor to acquire a class Queue

​

Since the public Interface is common, we can design a common�class Queue that leverages Implementation mechanics differently!

​

​

How?�A) Refactor our class to have a common m_container member which can be a � Dynamic Container of Different Types !

  1. Refactor public methods to use m_container’s public Interface (its methods) to Adapt its functionalities to achieve the ends of class Queue.

C) For some arbitrary Dynamic Container class to be “compatible” with class Queue, it should “support” all the functionalities invoked in the public Interface of Queue.

​

​

53 of 70

Advanced: Queue(s) as Container Adaptors

CS-202 C. Papachristos

1st Way to Refactor: Run-time Construction & Dispatch

class IContainer {

​

// just a collection of pure virtual methods, in order to enforce that� // every derived class from IContainer will have these implemented,

// i.e., will have the same public interface

public:

virtual bool empty() const = 0;

virtual size_t size() const = 0;

virtual Node * insertAfter(const Node * pos, DataType & value) = 0;

virtual Node * eraseAfter(const Node * pos) = 0;

virtual void clear() = 0;

virtual Node * head() = 0;

virtual Node * tail() = 0;

...

private:

// no members necessary, just an "interface" class

};

#ifndef QUEUE_H_

#define QUEUE_H_

​

#include <Container/ IContainer.h >

​

class Queue{

public:

Queue(std::string type="forwardlist");

Queue(size_t count, const DataType & val,

std::string type="forwardlist");

Queue(const Queue & other,

std::string type="forwardlist");

~Queue();

​

Queue & operator=(const Queue & other);

bool empty() const;

size_t size() const;

void push(const DataType & value);

void pop();

void clear();

DataType & front();

DataType & back();

​

​

private:

IContainer * m_container;

};

​

#endif

“Common” Header File: Queue.h

Remember:�Abstract classes as “unifying” Interface classes to derive from:

Any class that is-an IContainer (i.e., Derives from and Implements it)�is “compatible” to be used for m_container !

54 of 70

Advanced: Queue(s) as Container Adaptors

CS-202 C. Papachristos

1st Way to Refactor: Run-time Construction & Dispatch

#ifndef QUEUE_H_

#define QUEUE_H_

​

#include <Container/ IContainer.h >

​

class Queue{

public:

Queue(std::string type="forwardlist");

Queue(size_t count, const DataType & val,

std::string type="forwardlist");

Queue(const Queue & other,

std::string type="forwardlist");

~Queue();

​

Queue & operator=(const Queue & other);

bool empty() const;

size_t size() const;

void push(const DataType & value);

void pop();

void clear();

DataType & front();

DataType & back();

​

​

private:

IContainer * m_container;

};

​

#endif

“Common” Header File: Queue.h

Remember:�Virtual methods are dynamically dispatched at run-time:

class ForwardListContainer : public IContainer {

public:

ForwardListContainer();

ForwarListContainer(size_t count, const DataType & val);

ForwardListContainer(const ForwardlistContainer & other);

~ForwardListContainer();

​

ForwardListContainer & operator=(const ForwardListContainer & other);

virtual bool empty() const override;

virtual size_t size() const override;

virtual Node * insertAfter(const Node * pos, DataType & value) override;

virtual Node * eraseAfter(const Node * pos) override;

virtual void clear() override;

virtual Node * head() override;

virtual Node * tail() override;

...

private:

Node * m_head;

Node * m_tail;

};

Note: Also necessary to have

class Node { … };

55 of 70

Advanced: Queue(s) as Container Adaptors

CS-202 C. Papachristos

1st Way to Refactor: Run-time Construction & Dispatch

#ifndef QUEUE_H_

#define QUEUE_H_

​

#include <Container/ IContainer.h >

​

class Queue{

public:

Queue(std::string type="forwardlist");

Queue(size_t count, const DataType & val,

std::string type="forwardlist");

Queue(const Queue & other,

std::string type="forwardlist");

~Queue();

​

Queue & operator=(const Queue & other);

bool empty() const;

size_t size() const;

void push(const DataType & value);

void pop();

void clear();

DataType & front();

DataType & back();

​

​

private:

IContainer * m_container;

};

​

#endif

“Common” Header File: Queue.h

class ForwardListContainer : public IContainer {

public:

...

virtual Node * insertAfter(const Node * pos, DataType & value) override{

Node * newNode_pt = new Node(value, pos->m_next);

if empty() { m_head = m_tail = newNode_pt; }

else { pos->m_next = newNode_pt; }

return newNode_pt;

}

virtual Node * tail() override{

return m_tail;

}

​

private:

Node * m_head, * m_tail;

};

​

​

void Queue::push(const DataType & value){

​

m_container-> insertAfter (m_container-> tail() ,

value);

​

}

If the Queue code is in terms of the IContainer public Interface, the appropriate method is called in at run-time!

56 of 70

Advanced: Queue(s) as Container Adaptors

CS-202 C. Papachristos

1st Way to Refactor: Run-time Construction & Dispatch

#ifndef QUEUE_H_

#define QUEUE_H_

​

#include <Container/ IContainer.h >

​

class Queue{

public:

Queue(std::string type="forwardlist");

Queue(size_t count, const DataType & val,

std::string type="forwardlist");

Queue(const Queue & other,

std::string type="forwardlist");

~Queue();

​

Queue & operator=(const Queue & other);

bool empty() const;

size_t size() const;

void push(const DataType & value);

void pop();

void clear();

DataType & front();

DataType & back();

​

​

private:

IContainer * m_container;

};

​

#endif

“Common” Header File: Queue.h

Remember:�Virtual methods are dynamically dispatched at run-time:

class ListContainer : public IContainer {

public:

ListContainer();

ListContainer(size_t count, const DataType & val);

ListContainer(const ListContainer & other);

~ListContainer();

​

ListContainer & operator=(const ListContainer & other);

virtual bool empty() const override;

virtual size_t size() const override;

virtual Node * insertAfter(const Node * pos, DataType & value) override;

virtual Node * eraseAfter(const Node * pos) override;

virtual void clear() override;

virtual Node * head() override;

virtual Node * tail() override;

...

private:

Node * m_head;

Node * m_tail;

};

Note: Also necessary to have

class Node { … };

57 of 70

Advanced: Queue(s) as Container Adaptors

CS-202 C. Papachristos

1st Way to Refactor: Run-time Construction & Dispatch

#ifndef QUEUE_H_

#define QUEUE_H_

​

#include <Container/ IContainer.h >

​

class Queue{

public:

Queue(std::string type="forwardlist");

Queue(size_t count, const DataType & val,

std::string type="forwardlist");

Queue(const Queue & other,

std::string type="forwardlist");

~Queue();

​

Queue & operator=(const Queue & other);

bool empty() const;

size_t size() const;

void push(const DataType & value);

void pop();

void clear();

DataType & front();

DataType & back();

​

​

private:

IContainer * m_container;

};

​

#endif

“Common” Header File: Queue.h

If the Queue code is in terms of the IContainer public Interface, the appropriate method is called in at run-time!

class ListContainer : public IContainer {

public:

...

virtual Node * insertAfter(const Node * pos, DataType & value) override{

Node * newNode_pt = new Node(value, pos->m_next, pos);

if empty() { m_head = m_tail = newNode_pt; }

else { pos->m_next = newNode_pt; newNode_pt->m_next->m_prev = newNode_pt;}

return newNode_pt;

}

virtual Node * tail() override{

return m_tail;

}

​

private:

Node * m_head, * m_tail;

};

​

​

void Queue::push(const DataType & value){

​

m_container-> insertAfter (m_container-> tail() ,

value);

​

}

58 of 70

Advanced: Queue(s) as Container Adaptors

CS-202 C. Papachristos

1st Way to Refactor: Run-time Construction & Dispatch

#ifndef QUEUE_H_

#define QUEUE_H_

​

#include <Container/ IContainer.h >

​

class Queue{

public:

Queue(std::string type="forwardlist");

Queue(size_t count, const DataType & val,

std::string type="forwardlist");

Queue(const Queue & other,

std::string type="forwardlist");

~Queue();

​

Queue & operator=(const Queue & other);

bool empty() const;

size_t size() const;

void push(const DataType & value);

void pop();

void clear();

DataType & front();

DataType & back();

​

​

private:

IContainer * m_container;

};

​

#endif

“Common” Header File: Queue.h

BUT (Limitations)

A) Construction of a Queue requires to instantiate the m_container-pointed object as well.

​

  • Since the type is deferred to be decided at run-time, our Queue constructor will need access to an extra parameter to instantiate the correct Derived class, e.g.:

​

Queue::Queue( std::string type )

{

if (type == "forwardlist")

m_container = new ForwardListContainer();

else if (type == "list")

m_container = new ListContainer();

else

throw std::runtime_error(type + " is not supported");

}

59 of 70

Advanced: Queue(s) as Container Adaptors

CS-202 C. Papachristos

1st Way to Refactor: Run-time Construction & Dispatch

#ifndef QUEUE_H_

#define QUEUE_H_

​

#include <Container/ IContainer.h >

​

class Queue{

public:

Queue(std::string type="forwardlist");

Queue(size_t count, const DataType & val,

std::string type="forwardlist");

Queue(const Queue & other,

std::string type="forwardlist");

~Queue();

​

Queue & operator=(const Queue & other);

bool empty() const;

size_t size() const;

void push(const DataType & value);

void pop();

void clear();

DataType & front();

DataType & back();

​

​

private:

IContainer * m_container;

};

​

#endif

“Common” Header File: Queue.h

BUT (Limitations)

B) Dynamic Type Compatibility is restrictive.

​

  • When we create a Dynamic Container class, it has to�Derive from the IContainer Interface class in order to�be usable in the context of the Queue Adaptor class.

​

class ListContainer : public IContainer {

...

private:

Node * m_head;

Node * m_tail;

};

​

class ForwardListContainer : public IContainer {

...

private:

Node * m_head;

Node * m_tail;

};

60 of 70

Advanced: Queue(s) as Container Adaptors

CS-202 C. Papachristos

1st Way to Refactor: Run-time Construction & Dispatch

#ifndef QUEUE_H_

#define QUEUE_H_

​

#include <Container/ IContainer.h >

​

class Queue{

public:

Queue(std::string type="forwardlist");

Queue(size_t count, const DataType & val,

std::string type="forwardlist");

Queue(const Queue & other,

std::string type="forwardlist");

~Queue();

​

Queue & operator=(const Queue & other);

bool empty() const;

size_t size() const;

void push(const DataType & value);

void pop();

void clear();

DataType & front();

DataType & back();

​

​

private:

IContainer * m_container;

};

​

#endif

“Common” Header File: Queue.h

BUT (Limitations)

C) Dynamic Type Compatibility is very restrictive.

​

  • Both Derived classes have to use the same Node class as per their declaration and implementation (can also be redundant).

class ListContainer … { … private: Node * m_head, * m_tail; };

Node * ListContainer::insertAfter(const Node * pos,

DataType & value){

Node * newNode_pt = new Node(value, pos->m_next, pos);

…

}

​

class ForwardListContainer … { … private: Node * m_head, * m_tail; };

​

Node * ForwardListContainer::insertAfter(const Node * pos,

DataType & value){

Node * newNode_pt = new Node(value, pos->m_next);

…

}

Doubly-Linked requires Node to support both prev & next!

But, Singly-Linked could do with a Node with just next!

Note: Could perhaps introduce an INode interface class, but this creates further�complication with more interface designs & dynamic dispatch obscurity!

61 of 70

Advanced: Queue(s) as Container Adaptors

CS-202 C. Papachristos

1st Way to Refactor: Run-time Construction & Dispatch

#ifndef QUEUE_H_

#define QUEUE_H_

​

#include <Container/ IContainer.h >

​

class Queue{

public:

Queue(std::string type="forwardlist");

Queue(size_t count, const DataType & val,

std::string type="forwardlist");

Queue(const Queue & other,

std::string type="forwardlist");

~Queue();

​

Queue & operator=(const Queue & other);

bool empty() const;

size_t size() const;

void push(const DataType & value);

void pop();

void clear();

DataType & front();

DataType & back();

​

​

private:

IContainer * m_container;

};

​

#endif

“Common” Header File: Queue.h

BUT (Limitations)

D) Dynamic Type Compatibility is too restrictive.

​

  • If it’s not just the Interface that differs, we’re in big trouble.

class CircArrayContainer : public IContainer {

public:

CircArrayContainer();

CircArrayContainer(size_t count, const DataType & val);

CircArrayContainer(const CircArrayContainer & other);

~CircArrayContainer();

​

CircArrayContainer & operator=(const CircArrayContainer & other);

virtual bool empty() const override;

virtual size_t size() const override;

virtual Node * insertAfter(const Node * pos, DataType & value) override;

virtual Node * eraseAfter(const Node * pos) override;

virtual void clear() override;

virtual Node * head() override;

virtual Node * tail() override;

...

private:

void resize(size_t count);

DataType * m_arr;

size_t m_head, m_tail;

size_t m_size, m_capacity;

};

How can we specify via a Node *�the element in the array of DataType

objects ?

This has become infeasible / un-necessarily complicated …

62 of 70

Advanced: Queue(s) as Container Adaptors

CS-202 C. Papachristos

2nd Way to Refactor: Compile-time Determined Composition

​

#ifndef QUEUE_H_

#define QUEUE_H_

​

class Queue{

public:

Queue();

Queue(size_t count, const DataType & val);

Queue(const Queue & other);

~Queue();

​

Queue & operator=(const Queue & other);

bool empty() const;

size_t size() const;

void push(const DataType & value);

void pop();

void clear();

DataType & front();

DataType & back();

​

​

private:

Container m_container;

};

​

#endif

1st Header File: CircularArrayQueue.h

#ifndef CIRCULAR_ARRAY_QUEUE_H_

#define CIRCULAR_ARRAY_QUEUE_H_

​

#include <CircularArray/CircularArray.h>

​

// When we say: "Container" the compiler will understand

// it as an alias for "CircularArray" which is a class

typedef CircularArray Container;

​

#include <Queue/Queue.h> //Dependent on "Container"

​

#endif

2nd Header File: ForwardListQueue.h

#ifndef FORWARD_LIST_QUEUE_H_

#define FORWARD_LIST_QUEUE_H_

​

#include <ForwardList/ForwardList.h>

​

// When we say: "Container" the compiler will understand

// it as an alias for "ForwardList" which is a class

typedef ForwardList Container;

​

#include <Queue/Queue.h> //Dependent on "Container"

​

#endif

OR

“Common” Header File: Queue.h

63 of 70

Advanced: Queue(s) as Container Adaptors

CS-202 C. Papachristos

2nd Way to Refactor: Compile-time Determined Composition

​

#ifndef QUEUE_H_

#define QUEUE_H_

​

class Queue{

public:

Queue();

Queue(size_t count, const DataType & val);

Queue(const Queue & other);

~Queue();

​

Queue & operator=(const Queue & other);

bool empty() const;

size_t size() const;

void push(const DataType & value);

void pop();

void clear();

DataType & front();

DataType & back();

​

​

private:

Container m_container;

};

​

#endif

class ForwardList {

public:

ForwardList();

ForwardList(size_t count, const DataType & val);

ForwardList(const ForwardList & other);

~ForwardList();

​

ForwardList & operator=(const ForwardList & other);

bool empty() const;

size_t size() const;

Node * insertAfter(const Node * pos, DataType & value);

Node * eraseAfter(const Node * pos);

void clear();

Node * head();

Node * tail();

...

private:

Node * m_head;

Node * m_tail;

};

​

​

​

Queue::Queue() : m_container() { }

​

void Queue::push(const DataType & value){

​

m_container. insertAfter (m_container. tail() , value);

​

}

“Common” Header File: Queue.h

Now things should make sense when compiling (or not at all)

64 of 70

Advanced: Queue(s) as Container Adaptors

CS-202 C. Papachristos

2nd Way to Refactor: Compile-time Determined Composition

​

#ifndef QUEUE_H_

#define QUEUE_H_

​

class Queue{

public:

Queue();

Queue(size_t count, const DataType & val);

Queue(const Queue & other);

~Queue();

​

Queue & operator=(const Queue & other);

bool empty() const;

size_t size() const;

void push(const DataType & value);

void pop();

void clear();

DataType & front();

DataType & back();

​

​

private:

Container m_container;

};

​

#endif

class CircularArray {

public:

CircularArray();

CircularArray(size_t count, const DataType & val);

CircularArray(const CircularArray & other);

~CircularArray();

​

CircularArray & operator=(const CircularArray & other);

bool empty() const;

size_t size() const;

DataType * insertAfter(const DataType * pos, DataType & value);

DataType * eraseAfter(const DataType * pos);

void clear();

DataType * head();

DataType * tail();

...

private:

void resize(size_t count);

DataType * m_arr;

size_t m_head, m_tail;

size_t m_size, m_capacity;

};

​

Queue::Queue() : m_container() { }

​

void Queue::push(const DataType & value){

​

m_container. insertAfter (m_container. tail() , value);

​

}

“Common” Header File: Queue.h

Now things should make sense when compiling (or not at all)

65 of 70

Advanced: Queue(s) as Container Adaptors

CS-202 C. Papachristos

2nd Way to Refactor: Compile-time Determined Composition

​

#ifndef QUEUE_H_

#define QUEUE_H_

​

class Queue{

public:

Queue();

Queue(size_t count, const DataType & val);

Queue(const Queue & other);

~Queue();

​

Queue & operator=(const Queue & other);

bool empty() const;

size_t size() const;

void push(const DataType & value);

void pop();

void clear();

DataType & front();

DataType & back();

​

​

private:

Container m_container;

};

​

#endif

#include <Queue/CircularArrayQueue.h>

​

int main() {

Queue queue;

queue.push_back(DataType(…));

​

return 0;

}

“Common” Header File: Queue.h

We have to #include the appropriate header:

A) An implementation using Circular Array container-based Queues

#include <Queue/ForwardListQueue.h>

​

int main() {

Queue queue;

queue.push_back(DataType(…));

​

return 0;

}

B) An implementation using Forward List container-based Queues

#include <Queue/CircularArrayQueue.h>

#include <Queue/ForwardListQueue.h>

​

int main() {

Queue ??? circulararray_queue;

Queue ??? forwardlist_queue;

}

C) BUT Can we do both in the same Translation Unit ?

66 of 70

Advanced: Queue(s) as Container Adaptors

CS-202 C. Papachristos

2nd Way to Refactor: Compile-time Determined Composition

​

#define CONCAT_HELPER(a,b) a ## b

#define CONCAT(a,b) CONCAT_HELPER(a,b)

#define CLASSNAME CONCAT(__CONTAINER__,Queue)

​

class CLASSNAME{

public:

CLASSNAME();

CLASSNAME(size_t count, const DataType & val);

CLASSNAME(const CLASSNAME & other);

~CLASSNAME();

​

CLASSNAME & operator=(const CLASSNAME & other);

bool empty() const;

size_t size() const;

void push(const DataType & value);

void pop();

void clear();

DataType & front();

DataType & back();

​

​

private:

__CONTAINER__ m_container;

};

​

“Common” Header File: Queue.h

1st Header File: CircularArrayQueue.h

#ifndef CIRCULAR_ARRAY_QUEUE_H_

#define CIRCULAR_ARRAY_QUEUE_H_

​

#include <CircularArray/CircularArray.h>

​

#define __CONTAINER__ CircularArray

#include <Queue/Queue.h> //Dependent on "__CONTAINER__"

#undef __CONTAINER__

​

#endif

2nd Header File: ForwardListQueue.h

#ifndef FORWARD_LIST_QUEUE_H_

#define FORWARD_LIST_QUEUE_H_

​

#include <ForwardList/ForwardList.h>

​

#define __CONTAINER__ ForwardList

#include <Queue/Queue.h> //Dependent on "__CONTAINER__"

#undef __CONTAINER__

​

#endif

We have to create 2 different Queue classes …

Or we can pass the task�to the preprocessor !

​

Coming soon: C++ enables us to do this much more elegantly!

67 of 70

Advanced: Queue(s) as Container Adaptors

CS-202 C. Papachristos

2nd Way to Refactor: Compile-time Determined Composition

​

#define CONCAT_HELPER(a,b) a ## b

#define CONCAT(a,b) CONCAT_HELPER(a,b)

#define CLASSNAME CONCAT(__CONTAINER__,Queue)

​

class CLASSNAME{

public:

CLASSNAME();

CLASSNAME(size_t count, const DataType & val);

CLASSNAME(const CLASSNAME & other);

~CLASSNAME();

​

CLASSNAME & operator=(const CLASSNAME & other);

bool empty() const;

size_t size() const;

void push(const DataType & value);

void pop();

void clear();

DataType & front();

DataType & back();

​

​

private:

__CONTAINER__ m_container;

};

​

“Common” Header File: Queue.h

#include <Queue/CircularArrayQueue.h>

#include <Queue/ForwardListQueue.h>

​

int main() {

​

CircularArrayQueue circulararray_queue;

​

ForwardListQueue forwardlist_queue;

​

circulararray_queue. push_back (DataType(…));

​

forwardlist_queue. push_back (DataType(…));

​

return 0;

​

}

And now we in fact have 2 different�(__CONTAINER__Queue)classes …

​

  • Their public Interface looks exactly the same,�it is even determined in a “common” Queue.h file.
  • But their internal mechanics are vastly different, as they Adapt the interface of different Container classes!

68 of 70

Queue(s)

CS-202 C. Papachristos

Queue Applications

​

A “Simulation”

​

  • A technique for modeling the behavior of both natural and human-made systems.

​

Goal

​

  • Generate statistics that summarize the performance of an existing system.
  • Predict the performance of a proposed system.

​

69 of 70

Queue(s)

CS-202 C. Papachristos

Queue Applications

​

A Discrete–Event “Simulation” – example:

​

  • A simulation of the behavior of a bank.

​

As customers arrive, they go to the back of the line:

​

  • Use a Queue to represent the line of customers arriving at the bank.
  • Each customer’s request has a separate required service time.
  • Only the customer who is at the front of the queue can be served.
  • This customer is followingly removed from the system.

70 of 70

Time for Questions !

CS-202

CS-202 C. Papachristos