Implementing a Queue as a Linked Structure

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

Recently Viewed Presentations

  • Chapter 43 Review A. Deponent Verbs  Passive in

    Chapter 43 Review A. Deponent Verbs Passive in

    Semi-deponent verbs - regular active forms with active meanings in the present, imperfect, and future tenses but have passive forms with active meanings in the perfect, pluperfect and future perfect.. audeo, aud─ôre, ausus sum + infinitive - to dare. gaudeo,...
  • Media Player Accessibility: Insights from Interviews and ...

    Media Player Accessibility: Insights from Interviews and ...

    Able Player users can already drag and resize the sign language window, but they should also be able to crop it and/or resize it . without . preserving the aspect ratio. The video window itself should also be draggable and...
  • The Math Review Game Show - Denton ISD

    The Math Review Game Show - Denton ISD

    The Physical Science Game Show. Author: Amy Bramhall Created Date: 10/07/2002 09:29:06 Title: The Math Review Game Show Subject: SchoolKit.com Inc. Description
  • Learning Strategies Walk nTalk Time Line Doodles Colour

    Learning Strategies Walk nTalk Time Line Doodles Colour

    Wants Macbeth to be King Lady Macbeth puts pressure on Macbeth Malcolm and Donalbain flee for safety Macbeth fears Banquo Banquo suspects Macbeth Mind Map Non-Renewable? Waste products? Available ? Clean ? Renewable ? Industries that use them. Environmentally friendly...
  • Formation SPIP Nevers mai juin 2008 Animation en

    Formation SPIP Nevers mai juin 2008 Animation en

    Formation SPIP Nevers mai juin 2008 Animation en groupe de parole des auteurs de violences conjugales L'ANIMATION DE GROUPE DE PAROLE
  • The Exam: ReviewReviewing for the AP exam by creating a "band"

    The Exam: ReviewReviewing for the AP exam by creating a "band"

    Basics of the Band Project Review. Students will be in teams of 3-4. They will create a "band" as a way of reviewing for the AP Test focusing on one unit of the course. Note: with the earlier test date...
  • BOSCH GROUP IN INDIA - Resumos.net

    BOSCH GROUP IN INDIA - Resumos.net

    Bosch Group in India. The Head of the Division has to report to the MD of Bosch in India and to a person in the Asia region. The importance of command is no longer there. Strong and assertive personalities dominate...
  • Deeper Christian Life Ministry The Netherlands SEARCH THE

    Deeper Christian Life Ministry The Netherlands SEARCH THE

    What do we learn from Paul's admonition to restore believers overtaken in a fault? - Gal 6:1,2. THE POSSIBILITY OF BACKSLIDINGGalatians 6:1; 1 Corinthians 10:5-12. The fact that a believer can "be overtaken in a fault" or backslide cancels the...