Question: This program will help you in practicing queue and linkedlists by building a queue using the linkedlist struct and functions we created in the class.
This program will help you in practicing queue and linkedlists by building a queue using the linkedlist struct and functions we created in the class. You will find with the assignment the linkedlist implementation, vector implementation, and queue implementation using a vector struct. You will need to re-implement the queue using a linkedist instead of using a vector
item.h
#ifndef ITEM_H_
#define ITEM_H_ typedef int Item;
#endif
linkedlist.c
#include #include
#include "linkedlist.h"
#include "node.h"
struct linkedlist { Node_Ptr front; int size; };
typedef struct linkedlist LinkedList, * LinkedList_Ptr;
// initializing and allocating the memory for our linkedlist LinkedList_Ptr linkedlist_init_default()
{
// allocating the memory for my linkedlist
LinkedList_Ptr pLinkedList = malloc(sizeof(LinkedList));
// check if the memory was successfully allocated
if(pLinkedList != NULL)
{
// setting the front to NULL as the linkedlist is empty
pLinkedList->front = NULL;
pLinkedList->size = 0;
}
return pLinkedList;
}
// Takes the handle to the linkedlist and the item to add to the // end of the linkedlist
Status linkedlist_push_back(LinkedList_Ptr hLinkedList, Item item)
{
// making sure that the linkedlist was allocated
if(hLinkedList == NULL)
{
return FAILURE;
}
// list is empty, allocate memory for the front node (first node)
if(hLinkedList->front == NULL)
{
hLinkedList->front = malloc(sizeof(Node));
// check if memory was allocated
if(hLinkedList->front == NULL)
{
return FAILURE;
}
// hold the input item
hLinkedList->front->data = item;
// set the next to NULL
hLinkedList->front->next = NULL;
}
else
{
Node_Ptr current = hLinkedList->front;
while(current->next != NULL)
{
current = current->next;
}
Node_Ptr temp = malloc(sizeof(Node));
if(temp == NULL)
{
return FAILURE;
}
temp->data = item;
temp->next = NULL;
current->next = temp;
}
hLinkedList->size++;
return SUCCESS;
}
// removes the last node in the linkedlist
Status linkedlist_pop_back(LinkedList_Ptr hLinkedList)
{
if(hLinkedList == NULL || hLinkedList->front == NULL)
{
return FAILURE;
} // removing the first node (the linkedlist only have one node)
if(hLinkedList->front->next == NULL)
{
free(hLinkedList->front);
hLinkedList->front = NULL;
}
else {
// Node_Ptr current = hLinkedList->front->next;
Node_Ptr previous = hLinkedList->front;
while(current->next != NULL)
{
previous = current;
current = current->next;
}
free(current);
previous->next = NULL;
}
hLinkedList->size--;
return SUCCESS;
}
Status linkedlist_push_front(LinkedList_Ptr hLinkedList, Item item)
{
if(hLinkedList == NULL)
{
return FAILURE;
}
if(hLinkedList->front == NULL)
{
hLinkedList->front = malloc(sizeof(Node));
if(hLinkedList->front == NULL)
{
return FAILURE;
}
hLinkedList->front->data = item;
hLinkedList->front->next = NULL;
hLinkedList->size++;
}
else
{
Node_Ptr pNode = malloc(sizeof(Node));
if(pNode == NULL)
{
return FAILURE;
}
pNode->data = item;
pNode->next = hLinkedList->front;
hLinkedList->front = pNode;
hLinkedList->size++;
}
return SUCCESS;
}
Status linkedlist_pop_front(LinkedList_Ptr hLinkedList)
{
if(hLinkedList == NULL || hLinkedList->front == NULL)
{
return FAILURE;
}
Node_Ptr pNode = hLinkedList->front;
hLinkedList->front = hLinkedList->front->next;
free(pNode);
hLinkedList->size--;
return SUCCESS;
}
void linkedlist_display(LinkedList_Ptr hLinkedList)
{
if(hLinkedList != NULL)
{
Node_Ptr current = hLinkedList->front;
while(current != NULL)
{
printf("%d ", current->data);
current = current->next;
}
}
}
int linkedlist_get_size(LinkedList_Ptr hLinkedList)
{
return hLinkedList->size;
}
Item* linkedlist_front(LinkedList_Ptr hLinkedList)
{
// return null if we have an empty linkedlist
if(hLinkedList == NULL || hLinkedList->front == NULL)
{
return NULL;
}
// otherwise, return the address of the data held // by the front
return &hLinkedList->front->data;
}
Item* linkedlist_back(LinkedList_Ptr hLinkedList)
{
// return NULL if linkedlist was empty
if(hLinkedList == NULL || hLinkedList->front == NULL)
{
return NULL;
} // go till the end of the linkedlist
Node_Ptr current = hLinkedList->front;
while(current->next != NULL) {
current = current->next;
}
return t->data;
}
Item* linkedlist_at(LinkedList_Ptr hLinkedList, int index)
{
if(hLinkedList == NULL || index < 0 || index >= hLinkedList->size)
{
return NULL;
}
Node_Ptr current = hLinkedList->front;
for(int i= 0 ; i < index; i++)
{
current = current->next;
}
return t->data;
}
void linkedlist_destroy(LinkedList_Ptr* phLinkedList)
{
if(*phLinkedList != NULL) {
if((*phLinkedList)->front != NULL)
{ Node_Ptr current = (*phLinkedList)->front;
Node_Ptr next = (*phLinkedList)->front->next;
while(next != NULL)
{
free(current);
current = next;
next = next->next;
}
free(current);
}
free(*phLinkedList);
*phLinkedList = NULL;
}
}
linkedlist.h
#ifndef LINKED_LIST_H_
#define LINKED_LIST_H_
#include "status.h"
#include "item.h"
typedef struct linkedlist * LinkedList_Ptr;
// initialization for the linkedlist LinkedList_Ptr linkedlist_init_default();
// add an item to the end of the linkedlist
Status linkedlist_push_back(LinkedList_Ptr hLinkedList, Item item);
// removes an item from the end of the linkedlist
Status linkedlist_pop_back(LinkedList_Ptr hLinkedList);
// adds an item to the front of the linkedlist
Status linkedlist_push_front(LinkedList_Ptr hLinkedList, Item item);
// removes an item from the front of the linkedlist
Status linkedlist_pop_front(LinkedList_Ptr hLinkedList);
// display function to see what we have inside the linkedlist
void linkedlist_display(LinkedList_Ptr hLinkedList);
int linkedlist_get_size(LinkedList_Ptr hLinkedList);
// return the address of the item at the given index
Item* linkedlist_at(LinkedList_Ptr hLinkedList, int index);
// return the item at the front of the linkedlist
Item* linkedlist_front(LinkedList_Ptr hLinkedList);
// return the item at the back of the linked list
Item* linkedlist_back(LinkedList_Ptr hLinkedList);
// destroying the complete linkedlist
void linkedlist_destroy(LinkedList_Ptr* phLinkedList);
#endif
main.c #include
#include "queue.h"
int main()
{
// Creating a queue
Queue_Ptr hQueue = queue_init_default();
// adding item to the queue
for(int i = 0 ; i < 10 ; i++)
{
queue_enqueue(hQueue, i*10);
}
// displaying the queue queue_display(hQueue);
// checking the size
printf("Checking the size: %d ", queue_get_size(hQueue));
// checking the first item in the queue
printf("When using peek: %d ", *queue_peek(hQueue));
// Size after peeking
printf("The size after peeking: %d ", queue_get_size(hQueue));
// Removing 5 items from the queue
for(int i = 0 ; i < 5 ; i++)
{
queue_dequeue(hQueue);
}
// Checking the queue afer removing
queue_display(hQueue);
queue_destroy(&hQueue);
return 0;
}
Makefile
all: queue
queue: vector.o queue.o main.o
gcc -g vector.o queue.o main.o -o queue
main.o: main.c gcc -g -c main.c -o main.o
queue.o: queue.c
gcc -g -c queue.c -o queue.o
vector.o: vector.c
gcc -g -c vector.c -o vector.o
clean: rm *.o queue
node.h
#ifndef NODE_H_
#define NODE_H_
#include "status.h"
#include "item.h"
struct node;
typedef struct node Node, * Node_Ptr;
struct node
{
Item data; Node_Ptr next;
};
#endif
// NODE_H_
queue.c
#include #include
#include "queue.h"
#include "vector.h"
struct queue
{
Vector_Ptr hVector;
};
typedef struct queue Queue, * Queue_Ptr;
Queue_Ptr queue_init_default()
{
Queue_Ptr pQueue = NULL;
pQueue = malloc(sizeof(Queue));
if(pQueue != NULL)
{
pQueue->hVector = vector_init_default();
if(pQueue->hVector == NULL)
{
free(pQueue); pQueue = NULL;
}
}
return pQueue;
}
int queue_get_size(Queue_Ptr hQueue)
{
if(hQueue == NULL)
{
return -1;
}
return vector_get_size(hQueue->hVector);
}
Status queue_dequeue(Queue_Ptr hQueue)
{
if(hQueue == NULL || hQueue->hVector == NULL)
{
return FAILURE;
}
return vector_pop_front(hQueue->hVector);
}
Boolean queue_empty(Queue_Ptr hQueue)
{
int size = vector_get_size(hQueue->hVector);
if(size == -1)
{
return FALSE;
}
if(size == 0)
{
return TRUE;
}
return FALSE;
}
Status queue_enqueue(Queue_Ptr hQueue, Item item)
{
if(hQueue == NULL || hQueue->hVector == NULL)
{
return FAILURE;
}
return vector_push_back(hQueue->hVector, item);
}
Item * queue_peek(Queue_Ptr hQueue)
{
if(hQueue == NULL)
{
return NULL;
}
return vector_front(hQueue->hVector);
}
Status queue_display(Queue_Ptr hQueue)
{
if(hQueue == NULL)
{
return FAILURE;
}
return vector_display(hQueue->hVector);
}
void queue_destroy(Queue_Ptr * phQueue)
{
if(*phQueue != NULL)
{
vector_destroy(&(*phQueue)->hVector);
free(*phQueue);
*phQueue = NULL;
}
}
queue.h
#ifndef QUEUE_H
#define QUEUE_H
#include "status.h"
#include "item.h"
typedef struct queue * Queue_Ptr;
// Precondition:
NONE //
PostCondition: a Pointer to a Queue with an allocated memory
// if there was a memory allocation problem the pointer will hold
NULL Queue_Ptr queue_init_default();
// Precondition: a Pointer to Queue which was allocated before
// Postcondition: the current size of the Queue int queue_get_size(Queue_Ptr hQueue);
// Precondition: a Pointer to a Queue which was allocated before
// Postcondition: the Queue is empty or not
// Will return false if the queue was not allocated before
Boolean queue_empty(Queue_Ptr hQueue);
// Precondition: the Queue to add an item to
// Postcondition: an item should be added to the end of the queue.
// With FALIURE if it was not added or SUCCESS if it was added.
Status queue_enqueue(Queue_Ptr hQueue, Item item);
// Precondition: the Queue to remove an item from
// Postcondition: the Queue after removing an item with FAILURE if
// the queue was empty or SUCCESS if the item was removed
Status queue_dequeue(Queue_Ptr hQueue);
// Precondition: the Queue to check its top item
// Postcondition: the item itself or null if the queue was empty
Item * queue_peek(Queue_Ptr hQueue);
// Precondition: Queue to display its items
// Postcondition: FAILURE if the queue was empty
Status queue_display(Queue_Ptr hQueue);
// Precondition: a Queue to destroy
// Postcondition: the memory was successfully freed
void queue_destroy(Queue_Ptr * phQueue);
#endif
status.h
#ifndef STATUS_H
#define STATUS_H
enum status {FAILURE, SUCCESS};
typedef enum status Status;
enum boolean {TRUE, FALSE};
typedef enum boolean Boolean;
#endif
vector.c
#include
#include
#include "vector.h"
struct vector
{
int size; int capacity; Item *data;
};
typedef struct vector Vector;
Vector_Ptr vector_init_default(void)
{
Vector_Ptr pVector;
pVector = (Vector_Ptr)malloc(sizeof(Vector));
if(pVector != NULL)
{
pVector->size = 0; /
/initially, the vector is setup to hold only one element
pVector->capacity = 1;
pVector->data = (int*)malloc(sizeof(int)*pVector->capacity);
//Check if memory correctly allocated
if(pVector->data == NULL)
{
free(pVector); pVector = NULL;
}
}
//Return the pointer to the vector (the memory address) return pVector;
}
void vector_destroy(Vector_Ptr * phVector)
{
Vector_Ptr pVector = *phVector;
if(pVector!= NULL)
{
if(pVector->data != NULL)
{
free(pVector->data);
}
//Free the memory
free(pVector);
//Set the pointer to NULL *phVector = NULL;
}
}
Status vector_push_back(Vector_Ptr hVector, Item item)
{
Item * pTemp;
int i;
//If the array is filled with elements
if(hVector->size >= hVector->capacity)
{
//doubling the capacity
int double_capacity = hVector->capacity * 2;
pTemp = malloc(sizeof(int)*double_capacity);
if(pTemp == NULL)
{
return FAILURE;
}
else {
//Copying the data from the old array to the new array
for(i = 0 ; i < hVector->size; i++)
{
pTemp[i] = hVector->data[i];
}
//Do not need the old array, free the memory
free(hVector->data);
hVector->data = pTemp;
//Increasing the capacity of the vector hVector->capacity *=2;
}
}
//Adding the item to the end of the data array
hVector->data[hVector->size] = item;
//increasing the size after adding the item
hVector->size++;
//Successfully added the item and return
return SUCCESS;
}
Item* vector_at(Vector_Ptr hVector, int index)
{
//make sure that the index is not greater than the size //or the index is -ve
if(index >= hVector->size || index < 0)
{
return NULL;
}
//return the address of the item at the given index
return &hVector->data[index];
}
//Precondition: take a pointer to the vector
//Postcondition: return the size
int vector_get_size(Vector_Ptr hVector)
{
//Make sure that the vector was allocated
if(hVector != NULL)
{
return hVector->size;
}
//
return -1 if there is something wrong and there is no vector return -1;
}
//TODO: need to move these comments into the header file
//Precondition: a pointer to the allocated vector
//Postcondition: return the capacity
int get_capacity(Vector_Ptr hVector)
{
if(hVector != NULL)
{
return hVector->capacity;
}
//Return -ve capacity if there is an error return -1;
}
//Precondition: the vector
//Postcondition: remove an element from the end of the vector
//return SUCCESS if successfuly removed, Failure otherwise
Status vector_pop_back(Vector_Ptr hVector)
{
if(hVector == NULL)
{
return FAILURE;
}
if(hVector->size <= 0)
{
return FAILURE;
}
hVector->size--; return SUCCESS;
}
//Precondition: an allocated vector
//Postcondition: true if empty, false if not
Boolean vector_empty(Vector_Ptr hVector)
{
if(hVector->size > 0)
{
return FALSE;
}
return TRUE;
}
Status vector_pop_front(Vector_Ptr hVector)
{
if(hVector == NULL)
{
return FAILURE;
}
if(hVector->size == 0)
{
return FAILURE;
}
for(int i = 0 ; i < hVector->size-1; i++)
{
hVector->data[i] = hVector->data[i+1];
}
hVector->size--; return SUCCESS;
}
Item * vector_front(Vector_Ptr hVector)
{
if(hVector == NULL || hVector->size == 0)
{
return NULL;
}
return &hVector->data[0];
}
Item * vector_back(Vector_Ptr hVector)
{
if(hVector ==NULL ||hVector->size == 0)
{
return NULL; } return &hVector->data[hVector->size-1];
}
Status vector_display(Vector_Ptr hVector)
{
if(hVector == NULL)
{
return FAILURE;
}
for(int i = 0 ; i < hVector->size ; i++)
{
printf("%d ", hVector->data[i]);
}
return SUCCESS;
}
vector.h
#ifndef VECTOR_H
#define VECTOR_H
#include "status.h"
#include "item.h"
//The definition for the struct vector is not here //a handle
typedef struct vector *Vector_Ptr;
Vector_Ptr vector_init_default(void);
void vector_destroy(Vector_Ptr * phVector);
Status vector_push_back(Vector_Ptr hVector, Item item);
Item* vector_at(Vector_Ptr hVector, int index);
int vector_get_size(Vector_Ptr hVector);
//Return the capacity,
return hVector->capacity int vector_get_capacity(Vector_Ptr hVector);
//Remove one element for the back of the array
Status vector_pop_back(Vector_Ptr hVector);
Status vector_pop_front(Vector_Ptr hVector);
//Check if the data array was empty or not (by checking the size)
//Return if size is zero or not
Boolean vector_empty(Vector_Ptr hVector);
Item * vector_front(Vector_Ptr hVector);
Item * vector_back(Vector_Ptr hVector);
Status vector_display(Vector_Ptr hVector);
#endif
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help