C++ implementations of common container types

Containers.cpp

//Author: Eshwary Mishra 2023

/**
 * This file will give implementations for common containers implemented in C++
 * 
 * For simplicity we will use int as our type
*/

#include <iostream>

/**
 * This is an array-based stack. A stack only allows retrival of the last item placed within
*/
class Stack
{
public:

    void resize(int new_capacity);

    //Pushes an item to the top of the stack
    void push(int new_element);

    //Pops the item from the top of the stack
    const int pop();

    int num_elements = 0;
    int size = 0;
    int* data = nullptr;
};

void Stack::resize(int new_capacity)
{
    //Allocate new array with the new capacity
    if (int* new_data = new int[new_capacity])
    {
        //Copy old data to new array
        for(int i = 0; i < num_elements; ++i)
            new_data[i] = data[i];
        
        delete[] data;
        data = new_data;
        size = new_capacity * sizeof(int);
    }
}

void Stack::push(int new_element)
{
    //Resize if there is not enough space. A more optimized implementation will not do this every time we push
    if(num_elements + 1 > size / sizeof(int))
        resize(num_elements + 1);
    
    data[num_elements] = new_element;
    num_elements++;
}

const int Stack::pop()
{
    //We do not need to actually remove the data, just tell the list we do not have it anymore, that way it
    //will not be used again and will eventually be overidden. It should be noted that a more optimized
    //implementation will resize the array when there is too much free space
    num_elements--;
    return data[num_elements];
}

/**
 * This is an array-based queue. A queue only allows retrival of the first item placed within
*/
class Queue
{
public:

    void resize(int new_capacity);

    //Pushes an item to the top of the queue
    void push(int new_element);

    //Pops the item from the bottom of the queue
    const int pop();

    int num_elements = 0;
    int size = 0;
    int* data = nullptr;
};

void Queue::resize(int new_capacity)
{
    //Allocate new array with the new capacity
    if (int* new_data = new int[new_capacity])
    {
        //Copy old data to new array
        for(int i = 0; i < num_elements; ++i)
            new_data[i] = data[i];
        
        delete[] data;
        data = new_data;
        size = new_capacity * sizeof(int);
    }
}

void Queue::push(int new_element)
{
    //Resize if there is not enough space. A more optimized implementation will not do this every time we push
    if(num_elements + 1 > size / sizeof(int))
        resize(num_elements + 1);
    
    data[num_elements] = new_element;
    num_elements++;
}

const int Queue::pop()
{
    int i = data[0];

    //Shift all the data over one after, this will override the original value. It should be noted
    //that a more optimized implementation will resize the array when there is too much free space
    for(int j = 0; j < num_elements - 1; ++j)
        data[j] = data[j + 1];

    num_elements--;
    return i;
}

class Node
{
public:

    int data;
    Node* next = nullptr;
};

class LinkedList
{
public:

    Node* first = nullptr;
    int num_elements = 0;

    //Inserts an element to the end of the list
    void insert(int new_element);
    //Removes element from pos index
    void remove(int pos);
};

void LinkedList::insert(int new_element)
{
    num_elements++;

    Node* new_node = new Node();
    new_node->data = new_element;

    //Made sure we have a first node
    if(!first)
    {
        first = new_node;
        return;
    }

    //Add new node to the next of the list
    Node* temp = first;
    while (temp->next != nullptr)
        temp = temp->next;
    temp->next = new_node;
}

void LinkedList::remove(int pos)
{
    //To remove we just skip the reference to the node we want to remove, then we delete the node

    //Make sure the pos we are trying to remove exists
    if(pos > num_elements)
        return;

    num_elements--;

    //The case below will not handle the first node, so we handle that manually
    if(pos == 0)
    {
        Node* temp = first;
        first = first->next;
        delete temp;
        return;
    }
    
    //Get a reference to the node before the one we want to remove
    Node* temp = first;
    int i = 0;
    while (i < pos - 1)
    {
        temp = temp->next;
        i++;
    }

    //We will store a reference to the node to be removed so we can delete it after
    Node* temp_to_be_removed = temp->next;

    //Then we set the next node of the found preceeding node to the that of the proceeding node,
    //thereby skipping the node to be removed
    temp->next = temp->next->next;

    delete temp_to_be_removed;
}

int main()
{
    LinkedList stack;
    stack.insert(2);
    stack.insert(5);
    stack.insert(7);
    stack.insert(6);
    stack.insert(9);
    stack.insert(4);
    stack.remove(1);

    Node* temp = stack.first;
    while(temp != nullptr)
    {
        std::cout << temp->data << ", ";
        temp = temp->next;
    }
    std::cout << std::endl;
}