CST211 - Data Structures: Queue (Linked List-Based)

Overview

Linked list-based queue implementation providing dynamic capacity and efficient enqueue/dequeue operations.

Course Information

• Course: CST211 - Data Structures
• Assignment: Assignment 8 - Queue Linked List
• Institution: Oregon Institute of Technology

Features

• FIFO queue using linked nodes
• No capacity constraints
• Separate head and tail pointers for O(1) operations
• Dynamic memory allocation
• No circular buffer complexity

Technical Details

Queue Class

• Base Structure: Singly or doubly-linked list
• Pointers: Head (front) and tail (rear) pointers
• Efficiency: O(1) for both enqueue and dequeue

Key Operations

• Enqueue(T) - Add to tail of list
• Dequeue() - Remove from head of list
• Front() - View head element
• isEmpty() - Check if queue is empty
• Size() - Get element count

Comparison with Array-Based Queue

• Pros: No capacity limits, simpler logic (no wraparound)
• Cons: Memory overhead per node, pointer maintenance

Learning Objectives

• Alternative queue implementations
• Linked list with tail pointer optimization
• Trade-offs in queue implementation strategies
• Dynamic vs. fixed-size data structures

Technologies

• C++
• Visual Studio
• Linked data structures