User Tools

Site Tools


notes:data:spring2024:projects:waq0

This is an old revision of the document!


WAQ0

Doubly Linked Queue

A doubly linked queue is another form of doubly linked list that allows for adding and removing elements, like a stack. However, unlike a stack, where elements are added and removed from the top of the stack, in a queue elements are added to the top of the queue, and removed from the bottom.

FIFO

Function to Create a Queue

Here is what the pseudocode for creating a basic doubly linked queue would look like:

struct/class Obj:
    Data Obj will contain

    prevElement pointer to previous Obj in queue
    nextElement pointer to next Obj in queue

struct/class Queue:
    firstElement pointer to bottom of queue
    lastElement pointer to top of queue

Initialize prevObj
Initialize nextObj

add function (Obj* obj):
    Set prevObj and nextObj to obj's previous element and next element, respectively
    
    if queue is empty:
        Set queue's first element and last element to obj
        Set obj's prev element to NULL
        
    else:
        Set obj's previous element to queue's last element
        Set queue's last element's next element to obj
        Set queue's last element to obj

    Set obj's next element to NULL
    
    Point prevObj and nextObj to each other
    
remove function:
    Grab queue's first element
    Set nextObj to this obj's next element (second in queue)
    
    Set queue's first element to nextObj
    Set nextObj's previous element to NULL
    Set obj's next element to NULL
    
    return obj
    
Main Code:
    Initialize Queue
    
    Initialize elements
    
    Use add and remove functions throughout code   
    
notes/data/spring2024/projects/waq0.1713290029.txt.gz · Last modified: 2024/04/16 13:53 by rspringe