Lab46 Wiki

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).

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.

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.

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.

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);
  }

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.