User Tools

Site Tools


Sidebar

projects

pct0 (bonus; due 20230823)
wcp1 (due 20230823)
abc0 (due 20230830)
btt0 (due 20230830)
pct1 (bonus; due 20230830)
pct2 (due 20230830)
wcp2 (due 20230830)
mpg0 (due 20230906)
pct3 (bonus; due 20230906)
wcp3 (due 20230906)
pct4 (due 20230913)
ttb0 (due 20230913)
wcp4 (due 20230913)
pct5 (bonus; due 20230920)
ttb1 (due 20230920)
wcp5 (due 20230920)
dap0 (due 20230927)
gfo0 (due 20230927)
pct6 (due 20230927)
wcp6 (due 20230927)
cgf0 (due 20231004)
pct7 (bonus; due 20231004)
wcp7 (due 20231004)
bwp1 (bonus; due 20231018)
cgf1 (due 20231018)
pct8 (due 20231018)
wcp8 (due 20231018)
cgf2 (due 20231025)
pct9 (bonus; due 20231025)
wcp9 (due 20231025)
cgf3 (due 20231101)
gfo1 (due 20231101)
pctA (due 20231101)
wcpA (due 20231101)
pctB (bonus; due 20231108)
waq0 (due 20231108)
wcpB (due 20231108)
pctC (due 20231115)
waq1 (due 20231115)
wcpC (due 20231115)
bwp2 (bonus; due 20231129)
pctD (bonus; due 20231129)
wcpD (bonus; due 20231129)
gfo2 (due 20231206)
pctE (bonus; due 20231206)
wcpE (bonus; due 20231206)
EoCE (due 20231214)
haas:fall2023:data:projects:waq1

Corning Community College

CSCS2320 Data Structures

PROJECT: With A Queue, part 2 (WAQ1)

OBJECTIVE

Complete your integration of the doubly-linked queue into some interactive Vircon32 program (such as a card game or some other creation).

EDIT

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

Queue

If Stacks don't quite fit the design for what you're coding, you may want to consider a Queue instead.

Queues are similar in structure to Stacks with a different functionality. Both data structures exist overtop a List of some kind (for our instance it'll be a doubly-linked list) and act as an intermediary for the coder and the list. The goal of both Stacks and Queues is to make list management easier.

The difference between Stacks and Queues are minimal. A Stack only allows for elements to be added and removed from the top of the list (a “First In, Last Out” system). Meanwhile, a Queue only allows for elements to be added onto the bottom of the List, while they can only be removed from the top of the list (a “First In, First Out” system).

Queue Struct

Here is a simple struct you can implement for your queue structure:

struct queue {
    listnode* data;   // Pointer to the list that the queue sits on top of.
    cardnode* front;  // Pointer to the front of the queue
    cardnode* rear;   // Pointer to the rear of the queue
    int size;         // Size of the queue
};

The provided struct consists of a front and rear pointer of a queue along with a size variable. It also contains a pointer to the list struct which in and of itself holds the pointers that the list needs for navigation between its elements.

Function to initialize Queue

Once you have created your struct for your queue you can optionally create a function to call every time you want to make a queue. If you are creating the card game War(highly recommended) this is not necessary but helps clean up your program.

Here is an example of a function that creates a queue:

// Function that creates and initializes a new queue
queue* createQueue() {
    queue* newQueue = (queue*)malloc(sizeof(queue));
    newQueue->data = (list*)malloc(sizeof(list));
    newQueue->front = NULL;
    newQueue->rear = NULL;
    newQueue->size = 0;
    return newQueue;
}

This code allocates the memory for both your queue pointers, and the underlying list in which it operates on.

Function to Enqueue and Explanation

Enqueue is when you add an element to the back of a queue. In comparison when you add to a stack you are adding to the top.

Here is an example of what your enqueue function could look like:

// Function to enqueue a card to the end of a queue
void enqueue(queue* q, cardnode* card)
{
    card->next = NULL; // Sets next pointer to null
 
    // If the queue is empty then both front and rear are set to card
    if (q->front == NULL)
    {
        q->front = q->rear = card;
    }
 
    // If the queue is not empty then add new card to rear of queue
    else
    {
        q->rear->next = card;
        q->rear = card;
    }
 
    q->size++; // Increase queue size
}

Do NOT forget to “sanitize” the card before pushing it to the queue, disconnect it from the deck it was in to avoid →next or →prev issues later on

There are a couple of things to note about this example. First off, it is based on the previous struct in the section “Queue Struct”. Secondly, it uses a cardnode struct.

This function would come in handy in a card game like War. In War, two players show their cards and whoever has a higher card wins that hand. So when making this game, enqueue would be used to add the other player's card into your hand if you won and vice versa if you lost.

Shuffling the Queue

You can't shuffle a queue from within the queue itself, you would need to pop every item off of it, shuffle that, and then push them all back. It's not too bad, but it may seem counter-intuitive.

You need a loop to pull everything out of the queue, and then a shuffle function in the middle to shuffle the list you made out of the queue, and finally another loop to push it all back into the queue.

Pseudo-code of it looks like so:

  while(queue-is-not-empty){
      pop(queue);
  }
  shuffle_deck();
  while(deck-is-not-empty){
      push(queue);
  }

real-world applications of queues

In real-world applications, queues play a crucial role in managing tasks and resources. One prominent example is printer spooling. Printers have much less memory than you might think, and in a busy office environment, multiple users may send print jobs to a shared printer simultaneously. The printer spooler uses a queue to manage these print jobs, ensuring that they are processed in the order they are received. This prevents conflicts and ensures a fair and orderly distribution of printing tasks. The queue structure allows for a smooth and efficient printing process, eliminating the need for users to wait physically by the printer for their turn and promoting a seamless workflow in a shared computing environment. The versatility of the queue data structure extends beyond printer spooling, finding applications in diverse areas such as task scheduling, network management, and process control, where orderly and timely execution of tasks is essential for system efficiency.

In networking, particularly in the realm of routers, queues are pivotal for managing and prioritizing data packets as they traverse the network. Routers employ queues to temporarily hold incoming packets before forwarding them to their destination. This helps ensure that packets are processed in the order they are received, preventing data congestion and maintaining the integrity of the transmitted information. Additionally, queues play a crucial role in implementing Quality of Service (QoS) mechanisms, allowing routers to prioritize certain types of traffic over others. For instance, in video conferencing or voice call applications, queues can be configured to prioritize real-time communication packets, ensuring low latency and a seamless user experience. The queue data structure is also vital for addressing network congestion. When multiple data packets arrive at a router simultaneously, queues assist in organizing and managing the flow of information.

 

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:waq1:final tally of results (208/208)
*:waq1:doubly linked queue implemented [104/104]
*:waq1: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
haas/fall2023/data/projects/waq1.txt · Last modified: 2023/10/30 15:19 by 127.0.0.1