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 than both front and rear are set to card
    if (q->front == NULL)
    {
        q->front = q->rear = card;
    }
 
    // If the queue is not empty than add new card to rear of queue
    else
    {
        q->rear->next = card;
        q->rear = card;
    }
 
    q->size++; // Increase queue size
}

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