CS计算机代考程序代写 data structure algorithm Slide 1

Slide 1

Data Structures and Abstractions
Queues

Lecture 22

Queues
Queues are ADS that emulate, for example, a queue at the movies: you can only get on the back of the queue, and off at the front of the queue.
There are only two operations allowed on a queue: [1]
Enqueue (something on to it)
Dequeue (something off it)
Plus two query methods:
Empty ()
Full ()
Since the last thing on is the last thing off, they are known as FIFO (First In, First Out) data structures, or sometimes LILO (Last In, Last Out).

*
[1] This abstraction is different to the abstraction presented in see the Chapter on Stacks and Queues in the textbook. What is the difference? Look at the abstract class queueADT in the text.

Again as indicated when we looked at sets, there are commonly available abstractions of sets which try to be everything to everyone. To keep to the minimal and complete approach we use the abstraction shown in this slide. Also see the chapter on Elementary Data Structures in the reference book Introduction to Algorithms http://prospero.murdoch.edu.au/record=b2156975.

Queue Implementation
Queues can be implemented any way you want, the encapsulation of the container used ensures that it does not matter.
As long as it only has Enqueue, Dequeue, Empty and Full, then it is a queue.
Most commonly they are implemented using arrays, lists or an STL structure, with the STL Queue being more relevant.
However since none of these exactly fit the required minimal abstraction we are after, they should always be encapsulated.

Error Conditions for Queues
If you try to Enqueue() onto a queue that has no free memory, then you get overflow.
If you try to Dequeue() from an empty queue then you have underflow.
So Enqueue() and Dequeue() return a boolean to indicate if one of these errors has occurred.
In the animation that follows, two approaches are used.
The internal container is an array
The internal container is a linked list

Queue Example (Animation)
Array Implementation
Linked List Implementation
m_front

m_front
NULL
m_back
m_back
m_size
0

Queue Example (Animation)
Array Implementation
Linked List Implementation

m_front
NULL
m_back
m_back
Enqueue(10)
m_front
m_back
m_size
1
0

Queue Example (Animation)
Array Implementation
Linked List Implementation

10
1

m_front
NULL
m_back
m_back
Enqueue(1)
m_front
m_back
m_size
2
1

Queue Example (Animation)
Array Implementation
Linked List Implementation

10
1
23

m_front
NULL
m_back
m_back
Enqueue(23)
m_front
m_back
m_size
3
2

Queue Example (Animation)
Array Implementation
Linked List Implementation

10
1
23

m_front
NULL
m_back
Dequeue(num)
m_front
m_back
num
10
m_front
m_size
3
2

Queue Example (Animation)
Array Implementation
Linked List Implementation

1
23

m_front
NULL
m_back
Dequeue(num)
m_front
m_back
num
1
m_front
m_size
2
1

Queue Example (Animation)
Array Implementation
Linked List Implementation

m_front
NULL
m_back
Dequeue(num)
m_front
m_back
num
23
m_front
m_size
0
1
m_back
m_front

Queue Example (Animation)
Array Implementation
Linked List Implementation

m_front
NULL
m_back
Dequeue(num)
m_back
num

m_front
UNDERFLOW
m_size
0

Queue Example (Animation)
Array Implementation
Linked List Implementation

m_front
NULL
m_back
Dequeue(num)
m_back
num

m_front
m_size
0

Queue Example (Animation)
Array Implementation
Linked List Implementation
m_front

m_front
NULL
m_back
m_back
Enqueue(12)
m_front
m_back
m_size
1
0

Queue Example (Animation)
* of 41
Array Implementation
Linked List Implementation

12
45

m_front
NULL
m_back
m_back
Enqueue(45)
m_front
m_back
m_size
2
1

Queue Example (Animation)
Array Implementation
Linked List Implementation

12
45
23

m_front
NULL
m_back
m_back
Enqueue(23)
m_front
m_back
m_size
3
2

Queue Example (Animation)
Array Implementation
Linked List Implementation

12
45
23
87

m_front
NULL
m_back
m_back
Enqueue(87)
m_front
m_back
m_size
4
3

Queue Example (Animation)
Array Implementation
Linked List Implementation

12
45
23
87
9

m_front
NULL
m_back
m_back
Enqueue(9)
m_front
m_back
m_size
5
4

Queue Example (Animation)
Array Implementation
Linked List Implementation

12
45
23
87
9
63

m_front
NULL
m_back
m_back
Enqueue(63)
m_front
m_back
m_size
6
5

Queue Example (Animation)
Array Implementation
Linked List Implementation

12
45
23
87
9
63
6
m_front
NULL
m_back
m_back
Enqueue(6)
m_front
m_back
m_size
7
6

Queue Example (Animation)
Array Implementation
Linked List Implementation

12
45
23
87
9
63
6
m_front
NULL
m_back
Enqueue(22)
m_front
m_back
m_size
7
OVERFLOW

Queue Example (Animation)
Array Implementation
Linked List Implementation

12
45
23
87
9
63
6
m_front
NULL
m_back
Dequeue(num)
m_front
m_back
m_size
7
m_front
6

Queue Example (Animation)
Array Implementation
Linked List Implementation

31
45
23
87
9
63
6
m_front
NULL
m_back
Enqueue(31)
m_back
m_size
6
m_front
7
m_back
END

*
Study the array animation to see what happens when there are a series of enqueues followed by dequeues.

Array Enqueue Algorithm
ENQUEUE (DataType data): boolean
IF m_size >= ARRAY_SIZE-1
return FALSE
ELSE
Increment m_size
Increment m_back MOD ARRAY_SIZE [1]
Place data at position m_back
return TRUE
ENDIF
END Enqueue

*
[1]
What is the MOD operation doing – see the Chapter on Stacks and Queues in the textbook section on “Implementation of Queues as Arrays”. Go through the examples shown in the text where circular queues are explained.

Array Dequeue Algorithm
DEQUEUE (DataType data): boolean
IF m_size == 0
return FALSE
ELSE
data = data at position m_front
Increment m_front MOD ARRAY_SIZE
Decrement m_size
IF m_size == 0
m_front = -1
m_back = -1
ENDIF
return TRUE
ENDIF
END Dequeue

Linked List Enqueue Algorithm
ENQUEUE (DataType data): boolean
IF there is memory on the heap
Get newNode from the heap
IF m_front is NULL
m_front = newNode
m_back = newNode
ELSE
m_back.next = newNode
m_back = newNode
ENDIF
return TRUE
ELSE
return FALSE
ENDIF
END Enqueue

m_front
NULL
66
76
m_back

Linked List Dequeue Algorithm
DEQUEUE (DataType data): boolean
IF m_front == NULL
return FALSE
ELSE
data = m_front.data
oldNode = m_front
IF m_back == m_front
m_front = NULL
m_back = NULL
ENDIF
m_front = oldNode.next
release oldNode memory
oldNode = NULL
return TRUE
ENDIF
END Dequeue

m_front
NULL
66
76
m_back
oldNode

Using the STL
The other possibility is to use one of the STL structures.
If using a vector or list, then the algorithms above barely change.
However, remember that the structure must still be encapsulated in a class, otherwise it will not have just the Enqueue() and Dequeue() that it is supposed to have.
Finally, there is the STL queue class, (requiring ), which is obviously the best STL class to use.
However, even this should be encapsulated, because it does not conform to the standard queue description! [1]

*
[1] Again the abstraction is different. You join a queue and you leave a queue. See the reference book, Introduction to Algorithms section on “Stacks and Queues” in the chapter on “Elementary Data Structures” (10). You will see that how removed the STL queue is from the abstract queue. http://prospero.murdoch.edu.au/record=b2156975

Non Standard Features of the STL queue
Its Enqueue method is called push() [1]
Its Dequeue method is called pop().
Its pop() method, only removes the data, it does not pass it back to the calling method.
In fact there is a front() method which returns a reference to the front of the queue.
Neither dequeue(), front() nor enqueue() return a boolean: overflow and underflow must be checked separately.
Therefore it is best that the STL queue must be encapsulated. [2]

*
[1] Better abstractions than push and pop (stack ops) can be join and leave. You join a queue and you leave a queue.

[2] See the reference book, Introduction to Algorithms section on “Stacks and Queues” in the chapter on “Elementary Data Structures” (10). You will see that how removed the STL queue is from the abstract queue. http://prospero.murdoch.edu.au/record=b2156975

Queue Header File using STL queue
// Queue.h
//
// Queue class
//
// See actual code provided in the zip file
//——————————————-

#ifndef MY_QUEUE
#define MY_QUEUE

//——————————————-

#include // for the STL queue
#include
using namespace std;

//——————————————-

template
class Queue // minimal and complete
{
public:
Queue () {};
~Queue () {};
bool Enqueue(const T &data);
bool Dequeue (T &data);
bool Empty () const {return m_queue.empty();}
private:
queue m_queue; // encapsulates STL queue
};

* of 41

//——————————————-
// It is a template, so we have to put all the code
// in the header file
//——————————————-

template
bool Queue::Enqueue(const DataType &data)
{
bool okay = true;
try
{
m_queue.push(data); // calls STL queue method
}
catch (…)
{
okay = false;
}

return okay;
}

//——————————————-

template
bool Queue::Dequeue(DataType &data)
{
if (m_queue.size() > 0)
{
data = m_queue.front();
m_queue.pop();
return true;
}
else
{
return false;
}
}

//——————————————-

#endif

Simple (but interesting) Example of Queue Use
// IntQueueTest Program
//
// Version
// original by – Nicola Ritter
// modified by smr
//
//———————————————————

#include “Queue.h”
#include
#include
using namespace std;

//———————————————————

const int EVENT_COUNT = 20;
const int MAX_NUM = 100;

//———————————————————

typedef Queue IntQueue;
typedef Queue FloatQueue;

//———————————————————

void DoEvents ();
void AddNumber (IntQueue &aqueue);
void DeleteNumber (IntQueue &aqueue);
void TestOverflow();

//———————————————————

int main()
{
DoEvents ();

cout << endl; system("Pause"); cout << endl; TestOverflow(); cout << endl; return 0; } //--------------------------------------------------------- * void DoEvents () { IntQueue aqueue; // Seed random number generator srand (time(NULL)); for (int count = 0; count < EVENT_COUNT; count++) { // Choose a random event int event = rand() % 5; // Do something based on that event type, biasing // it towards Adding if (event <= 2) // event = 0, 1 or 2 { AddNumber (aqueue); } else // event = 3 or 4 { DeleteNumber (aqueue); } } // aqueue is local so destructor for aqueue is called when routine finishes. } //--------------------------------------------------------- * void AddNumber (IntQueue &aqueue) { // Get a random number int num = rand() % (MAX_NUM+1); // Try adding it, testing if the aqueue was full if (aqueue.Enqueue(num)) { cout.width(3); cout << num << " added to the queue" << endl; } else { cout.width(3); cout << "Overflow: could not add " << num << endl; } } //--------------------------------------------------------- * void DeleteNumber (IntQueue &aqueue) { int num; if (aqueue.Dequeue(num)) { cout.width(3); cout << num << " deleted from the queue" << endl; } else { cout << "IntQueue is empty, cannot delete" << endl; } } //--------------------------------------------------------- * void TestOverflow() { Queue mqueue;

int count = 0;

// Keeping adding numbers until we run out of space, will take //time
while (mqueue.Enqueue(count))
{
count++;
cout << "Count is " << count << endl; } } //--------------------------------------------------------- * Screen Output IntQueue is empty, cannot delete 79 added to the queue 79 deleted from the queue IntQueue is empty, cannot delete 2 added to the queue 2 deleted from the queue IntQueue is empty, cannot delete 72 added to the queue 72 deleted from the queue 88 added to the queue 88 deleted from the queue 22 added to the queue 5 added to the queue 22 deleted from the queue 37 added to the queue 46 added to the queue 74 added to the queue 58 added to the queue 5 deleted from the queue 37 deleted from the queue Press any key to continue . . . Count is 1 Count is 2 Count is 3 Count is 4 Count is 5 Count is 6 Count is 7 Count is 8 Count is 9 Count is 10 Count is 11 Count is 12 Count is 13 Count is 14 Count is 15 Count is 16 Count is 17 ... At 300,000 I stopped: it was just too boring * TestOverflow is going to take a while when adding a few bytes at a time. Advantages of Implementations It is assumed for each of the containers below, that the Queue encapsulates it in its own class. Array Linked List list/vector/deque STL queue Available in all languages. Full memory control Easy to code Easiest to code Memory ‘never’ runs out. [1] Memory ‘never’ runs out. [1] Memory ‘never’ runs out. [1] * 1 It can run out if the physical resources run out. RAM and virtual ram Disadvantages of Implementations It is assumed for each of the containers below, that the Queue encapsulates it in its own class. Array Linked List list/vector/deque STL queue Can run out of space easily. Difficult to code as it uses pointers. Excess code sitting ‘behind’ the implementation, increasing the size of the program. Excess code sitting ‘behind’ the implementation, increasing the size of the program. Messy to code, because m_back ends up in front of m_front Only available in C++. Only available in C++. * Readings Textbook: Stacks and Queues, entire section on Queues STL Queue: http://en.cppreference.com/w/cpp/container/queue For more details of Queues with some level of language independence, see the reference book, Introduction to Algorithms section on “Stacks and Queues” in the chapter on “Elementary Data Structures”. You will see that how removed the STL queue is from the abstract queue we are after.

Related Posts