PROJECT: With A Queue, part 1 (WAQ0)

OBJECTIVE

Implement a doubly-linked queue, atop the doubly-linked list.

Incorporate the queue into some interactive Vircon32 cartridge (such as some card game that makes use of a queue), or other creation.

EDIT

You will want to go here to edit and fill in the various sections of the document:

https://lab46.g7n.org/notes/data/spring2024/projects/waq0

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

FIFO stands for “First In First Out”, and it is the way that data is removed from a queue.

If the Stack can be thought of as a stack of papers, then a queue can be thought of as a line at a bank or at a grocery store checkout.

For a stack of papers, if you wanted to place a new paper on the stack, then you would put it on top of the stack. Then, if you wanted to take a sheet of paper, then you would generally take one from the top of the stack, leaving the bottom of the stack as it was.

For a line of people, anyone new who joins the line will have to stop and wait at the end of the line. Then, when the next person is called from the line, the person who is waiting at the very front of the line will go forward and leave the queue.

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

SUBMISSION

To be successful in this project, the following criteria (or their equivalent) must be met:

Project must be submit on time, by the deadline.
- Late submissions will lose 33% credit per day, with the submission window closing on the 3rd day following the deadline.
Executed programs must display in a manner similar to provided output
- output formatted, where applicable, must match that of project requirements
Processing must be correct based on input given and output requested
Output, if applicable, must be correct based on values input
Code must be nicely and consistently indented
Code must be consistently written, to strive for readability from having a consistent style throughout
Code must be commented
- Any “to be implemented” comments MUST be removed
  - these “to be implemented” comments, if still present at evaluation time, will result in points being deducted.
  - Sufficient comments explaining the point of provided logic MUST be present
No global variables (without instructor approval), no goto statements, no calling of main()!
Track/version the source code in your lab46 semester repository
Submit a copy of your source code to me using the submit tool by the deadline.

Submit Tool Usage

Let's say you have completed work on the project, and are ready to submit, you would do the following:

lab46:~/src/SEMESTER/DESIG/PROJECT$ submit DESIG PROJECT file1 file2 file3 ... fileN

You should get some sort of confirmation indicating successful submission if all went according to plan. If not, check for typos and or locational mismatches.

RUBRIC

I'll be evaluating the project based on the following criteria:

208:waq0:final tally of results (208/208)
*:waq0:doubly linked queue implemented [104/104]
*:waq0:start of incorporation of queue into something [104/104]

Pertaining to the collaborative authoring of project documentation

each class member is to participate in the contribution of relevant information and formatting of the documentation
- minimal member contributions consist of:
  - near the class average edits (a value of at least four productive edits)
  - near the average class content change average (a value of at least 1024 bytes (absolute value of data content change))
  - near the class content contribution average (a value of at least 1kiB)
  - no zero-sum commits (adding in one commit then later removing in its entirety for the sake of satisfying edit requirements)
- adding and formatting data in an organized fashion, aiming to create an informative and readable document that anyone in the class can reference
- content contributions will be factored into a documentation coefficient, a value multiplied against your actual project submission to influence the end result:
  - no contributions, co-efficient is 0.50
  - less than minimum contributions is 0.75
  - met minimum contribution threshold is 1.00

Additionally

Solutions not abiding by spirit of project will be subject to a 50% overall deduction
Solutions not utilizing descriptive why and how comments will be subject to a 25% overall deduction
Solutions not utilizing indentation to promote scope and clarity or otherwise maintaining consistency in code style and presentation will be subject to a 25% overall deduction
Solutions not organized and easy to read (assume a terminal at least 90 characters wide, 40 characters tall) are subject to a 25% overall deduction

Lab46 Wiki

Sidebar

Table of Contents

PROJECT: With A Queue, part 1 (WAQ0)

OBJECTIVE

EDIT

WAQ0

Doubly Linked Queue

FIFO

Function to Create a Queue

SUBMISSION

Submit Tool Usage

RUBRIC

Pertaining to the collaborative authoring of project documentation

Additionally

Lab46 Wiki

User Tools

Site Tools

Sidebar

Table of Contents

PROJECT: With A Queue, part 1 (WAQ0)

OBJECTIVE

EDIT

WAQ0

Doubly Linked Queue

FIFO

Function to Create a Queue

SUBMISSION

Submit Tool Usage

RUBRIC

Pertaining to the collaborative authoring of project documentation

Additionally

Page Tools