⚡ Embedded Modern C++ Section 12 • #12.06
Portal Home / Section 12 / Project 12.06: LinkedQueueProject
Project 12.06 Section 12 ⚡ Embedded Relevance: Medium LinkedQueue FIFO Pointer Chasing

12.06 Front & Rear Pointer Manipulation vs Cache Inefficiencies

Executive Summary: Implementing a node-based FIFO queue with front and rear pointers, contrasting its memory footprint with array ring buffers.

💻 1. Annotated Source Code 

#ifndef QUEUE_H
#define QUEUE_H

class Queue {
	public:
		virtual void enqueue(int newEntry) = 0;
		virtual int dequeue() = 0;
		virtual int peekFront() const = 0;
		virtual bool isEmpty() const = 0;
		virtual void makeEmpty() = 0;

		virtual ~Queue() = default;
};

#endif 
#ifndef LINKED_QUEUE_H
#define LINKED_QUEUE_H

#include "Queue.h"
#include <iostream>
using namespace std;

// Doubly linked Node
class Node {
public:
    Node(int data, Node* next = nullptr, Node* prev = nullptr)
        : data(data), next(next), previous(prev) {
    }

    int getData() const { return data; }
    void setData(int val) { data = val; }

    Node* getNext() const { return next; }
    void setNext(Node* n) { next = n; }

    Node* getPrevious() const { return previous; }
    void setPrevious(Node* p) { previous = p; }

private:
    int data;
    Node* next;
    Node* previous;
};

class LinkedQueue : public Queue {


    public:
        LinkedQueue() : front(nullptr), back(nullptr) {}
        //end ctor

        virtual ~LinkedQueue() {
            makeEmpty();
        }//end dtor

        void enqueue(int newEntry) override {
            Node* newNode = new Node(newEntry);
            
            if (isEmpty()) {
                front = back = newNode;
            }
            else {
                back->setNext(newNode);
                newNode->setPrevious(back);
                back = newNode;
            }
        }//end enqueue

        int dequeue() override {
            if (isEmpty()) {
                cout << "You cannot dequeue from an empty queue." << endl;
                return 0;
            }

            Node* temp = front;
            int data = temp->getData();
            front = front->getNext();

            if (front == nullptr) {
                back = nullptr;  //queue is now empty
            }
            else {
                front->setPrevious(nullptr);
            }

            delete temp;
            return data;
        }//end dequeue

        int peekFront() const override {
            if (!isEmpty()) {
                return front->getData();
            }
            else {
                cout << "You cannot peek the front of an empty queue!" << endl;
                return 0;
            }
        }//end peekFront

        bool isEmpty() const override {
            return front == nullptr;
        }//end isEmpty

        void makeEmpty() override {
            while (!isEmpty()) {
                dequeue();
            }
        }//end makeEmpty

    private:
        Node* front;
        Node* back;

};


#endif 
#include <iostream>
#include "LinkedQueue.h"
using namespace std;

int main() {
	LinkedQueue queue;

	cout << "Enqueuing values..." << endl;
	for (int i = 1; i <= 10; i++) {
		cout << "Enqueueing " << (i * 100) << endl;
		queue.enqueue(i * 100);
	}//end for

	queue.enqueue(1234);

	cout << "Dequeuing values..." << endl;
	while (!queue.isEmpty()) {
		cout << queue.dequeue() << endl;
	}

	queue.dequeue();

	return 0;
}

📐 2. Architecture & UML Class Model

📐 LinkedQueue FIFO Pointer Queue with Head & Tail Pointers
+ Public - Private # Protected
<<struct>> QueueNode<T> Queue Node
Attributes / Data Members
+item : T
+next : QueueNode<T>*
<<template class>> LinkedQueue<T> FIFO Linked Queue
Attributes / Data Members
-frontPtr : QueueNode<T>*
-backPtr : QueueNode<T>*
Operations / Methods
+LinkedQueue()
+~LinkedQueue()
+enqueue(newEntry: const T&) : bool[O(1)]
+dequeue() : bool[O(1)]
+peekFront() : T const[O(1)]
+isEmpty() : bool const
🔗 Architectural Relationships & Hierarchy
LinkedQueue<T> ◆── enqueues & dequeues ◆── QueueNode<T>

📚 3. Core C++ Concepts Deep-Dive

Two-Pointer Queue Mechanics

Maintains head and tail pointers for $O(1)$ push and pop.

⚡ 4. Embedded Systems & Hardware Reality

Heap Allocation Overhead

Every enqueue calls new Node, creating dynamic allocation jitter in embedded environments.

💡 5. Production-Ready Embedded Refactoring

💡 Production-Ready Refactor 
// Prefer ArrayQueue / RingBuffer for embedded queues

📝 Knowledge Verification Quiz

Test your understanding of the C++ concepts and embedded microcontroller trade-offs covered in this guide. Click any option for instant feedback.

Q1. What is the main drawback of LinkedQueue in interrupt handlers?
A Enqueuing requires dynamic memory allocation (new), which is unsafe in ISRs.
B It is too fast.
C It cannot store structures.
D It uses too few registers.
Detailed Explanation: Dynamic memory allocation inside an interrupt service routine is non-reentrant and causes system crashes.