So, I am relatively new to C and trying to implement a Queue using Linked Lists. Here is some code I wrote with help from the internet.

#include <stdio.h>
#include <stdlib.h>
#define pscan(prompt, x) printf(prompt); scanf("%d", &x)
#define nl() printf("\n");

typedef struct Node {
    int data;
    struct Node* next;
} Node;

typedef struct LinkedList {
    Node* head;
    Node* tail;
    int size;
    int (*add) (struct LinkedList*, int, int);
    int (*append) (struct LinkedList*, int);
    int (*get) (struct LinkedList*, int);
    int (*remove) (struct LinkedList*, int);
    void (*display_list) (struct LinkedList*);
    Node* (*createNode) (int);
} LinkedList;

int add (LinkedList* self, int data, int position);
int append (LinkedList* self, int data);
int get (LinkedList* self, int position);
int rmv (LinkedList* self, int position);
void display_list (LinkedList* self);
LinkedList createLinkedList ();
Node* createNode (int data);

int add(LinkedList* self, int data, int position)
{
    if (position > self->size || position < 0)
    {
        printf("Index out of bounds\n");
        return 0;
    }
    Node* newNode = self->createNode(data);
    Node* head = self->head;
    Node* tail = self->tail;

    if (position == 0)
    {
        if (head == NULL) self->head = newNode;
        else
        {
            if (tail == NULL) tail = head;
            newNode->next = head;
            self->head = newNode;
        }
        self->size  ;
    }
    else if (position == self->size)
    {
        if (head == NULL) self->head = newNode;
        else
        {
            if (tail == NULL) tail = head;
            tail->next = newNode;
            self->tail = newNode;
        }
        self->size  ;
    }
    else
    {
        Node* prev = head;
        for(int i = 0; i < position-1; i  )
        {
            prev = prev->next;
        }
        Node* node = prev->next;

        prev->next = newNode;
        newNode->next = node;

        self->size  ;
    }
    return 0;
}

int append(LinkedList* self, int data)
{
    return self->add(self, data, self->size);
}

int get(LinkedList* self, int position)
{
    if (self->size == 0)
    {
        printf("The list is empty.");
        return 0;
    }
    else if (position >= self->size || position < 0)
    {
        printf("Index out of bound.");
        return 0;
    }

    if (position == 0) return self->head->data;
    else if (position 1 == self->size) return self->tail->data;
    else
    {
        Node* node = self->head;
        for(int i = 0; i < position; i  ) node = node->next;
        return node->data;
    }
}

int rmv (LinkedList* self, int position)
{
    int dt;
    if (self->size == 0)
    {
        printf("The list is empty.");
        return 0;
    }
    else if (position >= self->size || position < 0)
    {
        printf("Index out of bound");
        return 0;
    }

    if (position == 0)
    {
        Node* head = self->head;
        Node* next = head->next;
        self->head = next;
        dt = head->data;
        free(head);
        self->size--;
    }
    else if (position 1 == self->size)
    {
        Node* node = self->head;
        Node* tail = self->tail;
        for(int i = 0; i < self->size-2; i  ) node = node->next;

        node->next = NULL;
        self->tail = node;
        dt = tail->data;
        free(tail);
        self->size--;
    }
    else
    {
        Node* prev = self->head;
        Node* next;
        Node* node;
        for(int i = 0; i < position-1; i  ) prev = prev->next;
        node = prev->next;
        next = node->next;

        prev->next = next;
        dt = node->data;
        free(node);
        self->size--;
    }
    return dt;
}

void display_list(LinkedList* self)
{
    if (self->size == 0) printf("This list is empty.\n\n");
    else
    {
        Node* node = self->head;

        printf("[");
        for (int i = 0; i < self->size; i  )
        {
            if (i > 0) printf(", ");
            printf("%d", node->data);
            node = node->next;
        }
        printf("]\n\n");
    }
}

Node* createNode (int data)
{
    Node* node = (Node*) malloc(sizeof(Node));
    node->data = data;
    node->next = NULL;
    return node;
}

LinkedList createLinkedList ()
{
    LinkedList l;
    l.head = NULL;
    l.tail = NULL;
    l.add = &add;
    l.append = &append;
    l.get = &get;
    l.remove = &rmv;
    l.display_list = &display_list;
    l.createNode = &createNode;
    l.size = 0;
    return l;
}

typedef struct queue
{
    LinkedList items;
    int *size;

    int (*enqueue) (struct queue*, int);
    int (*dequeue) (struct queue*);
    int (*peek) (struct queue*, int);
    void (*display) (struct queue*);

} Queue;

Queue CreateQueue();

int enqueue(Queue* self, int item);
int dequeue(Queue* self);
int peek(Queue* self, int pos);
void display(Queue* self);

Queue CreateQueue()
{
    Queue q;
    q.items = createLinkedList();
    q.size = &(q.items.size);
    q.enqueue = &enqueue;
    q.dequeue = &dequeue;
    q.peek = &peek;
    q.display = &display;
    return q;
}

int enqueue(Queue* self, int item)
{
    self->items.append(&(self->items), item);
    return 1;
}

int dequeue(Queue* self)
{
    return self->items.remove(&(self->items), 0);
}

int peek(Queue* self, int pos)
{
    return self->items.get(&(self->items), pos);
}

void display(Queue* self)
{
    printf("%d items in queue.\n", *(self->size));
    self->items.display_list(&(self->items));
}

void main()
{
    Queue q = CreateQueue();
    q.enqueue(&q, 3);
    q.enqueue(&q, 7);
    q.enqueue(&q, 4);
    q.display(&q);
    int item = q.dequeue(&q);
    printf("Dequeued: %d\n", item);
    q.display(&q);
    q.enqueue(&q, 14);
    q.display(&q);
}

The part I'm having an issue with is making the Queue's size pointer point to the LinkedList's size integer and then accessing that value.

On compiling and running, I get this: Output from the above code

Thanks in advance.

CodePudding user response：

The problem is in createQueue:

Queue CreateQueue()
{
    Queue q;
    q.items = createLinkedList();
    q.size = &(q.items.size);
    q.enqueue = &enqueue;
    q.dequeue = &dequeue;
    q.peek = &peek;
    q.display = &display;
    return q;
}

You set q.size to point to q.items.size. This is a pointer to a local variable. You then return a copy of q, but the size member now points to a local that doesn't exist. Dereferencing a pointer to a variable whose lifetime has ended triggers undefined behavior.

There's no need for the size element in Queue. Just access the size element of the items member directly.