# Implementing a Queue as a Linked Structure Implementing a Queue as a Linked Structure CS 308 Data Structures Implementing queues using arrays Simple implementation The size of the queue must be determined

when a stack object is declared Space is wasted if we use less elements We cannot "enqueue" more elements than the array can hold Implementing queues using linked lists Allocate memory for each new element

dynamically Link the queue elements together Use two pointers, qFront and qRear, to mark the front and rear of the queue Queue class specification // forward declaration of NodeType (like function prototype) template struct NodeType; template class QueueType { public:

QueueType(); ~QueueType(); void MakeEmpty(); bool IsEmpty() const; bool IsFull() const; void Enqueue(ItemType); void Dequeue(ItemType&); private: NodeType* qFront; NodeType* qRear; };

Enqueuing (non-empty queue) Enqueuing (empty queue) We need to make qFront point to the new node also qFront = NULL New Node qRear = NULL

newNode Function Enqueue template void QueueType::Enqueue(ItemType newItem) { NodeType* newNode; newNode = new NodeType; newNode->info = newItem; newNode->next = NULL; if(qRear == NULL)

qFront = newNode; else qRear->next = newNode; qRear = newNode; } Dequeueing (the queue contains more than one element) Dequeueing (the queue contains only one element)

We need to reset qRear to NULL also qFront After dequeue: Node qRear qFront = NULL qRear = NULL Function Dequeue

template void QueueType::Dequeue(ItemType& item) { NodeType* tempPtr; tempPtr = qFront; item = qFront->info; qFront = qFront->next; if(qFront == NULL) qRear = NULL; delete tempPtr; }

qRear, qFront revisited The relative positions of qFront and qRear are important! Other Queue functions template QueueType::QueueType() { }

qFront = NULL; qRear = NULL; template void QueueType::MakeEmpty() { NodeType* tempPtr; while(qFront != NULL) { tempPtr = qFront; qFront = qFront->next;

delete tempPtr; } } qRear=NULL; Other Queue functions (cont.) template bool QueueType::IsEmpty() const { }

return(qFront == NULL); template bool QueueType::IsFull() const { NodeType* ptr; ptr = new NodeType; if(ptr == NULL) return true; else {

delete ptr; return false; } } Other Queue functions (cont.) template QueueType::~QueueType() { MakeEmpty(); }

A circular linked queue design Comparing queue implementations Memory requirements Array-based implementation Assume a queue (size: 100) of strings (80 bytes each) Assume indices take 2 bytes Total memory: (80 bytes x 101 slots) + (2 bytes x 2

indexes) = 8084 bytes Linked-list-based implementation Assume pointers take 4 bytes Total memory per node: 80 bytes + 4 bytes = 84 bytes Comparing queue implementations (cont.)

Comparing queue implementations Memory requirements (cont.) Array-based implementation Assume a queue (size: 100) of short integers (2 bytes each) Assume indices take 2 bytes Total memory: (2 bytes x 101 slots) + (2 bytes x 2 indexes) = 206 bytes

Linked-list-based implementation Assume pointers take 4 bytes Total memory per node: 2 bytes + 4 bytes = 6 bytes Comparing queue implementations (cont.) Comparing queue implementations Big-O Comparison of Queue Operations

Operation Array Linked Implementation Implementation Class constructor MakeEmpty IsFull IsEmpty Enqueue Dequeue Destructor

O(1) O(1) O(1) O(1) O(1) O(1) O(1) O(1) O(N) O(1) O(1)

O(1) O(1) O(N) Exercises 5, 6