Stack principle of Last In First Out (LIFO)

stack-using-unique_ptr.cc

#include "iostream"
#include "memory"

struct StackHolder {
    std::string data;
};

class Stack {
private:
    int idx = -1;

    std::unique_ptr <StackHolder[]> data;

public:
    Stack() : idx(-1), data(nullptr) {}

    void push(const std::string &str) {
        idx++;

        std::unique_ptr < StackHolder[] > new_data(new StackHolder[idx + 1]);

        std::copy(data.get(), data.get() + idx, new_data.get());

        new_data[idx].data = str;

        data.swap(new_data);
    }

    StackHolder* pop() {
        if (idx < 0)
            return nullptr;

        return &data[idx--];
    }

    bool is_empty() {
        return idx == -1;
    }
};

int main() {
    Stack stack;

    stack.is_empty() ? std::cout << "stack is empty" : std::cout << "stack is not empty";
    std::cout << std::endl;

    stack.push("Hello");
    stack.push("World");
    stack.push("Story");

    stack.is_empty() ? std::cout << "stack is empty" : std::cout << "stack is not empty";
    std::cout << std::endl;

    StackHolder *stackHolder;
    while ((stackHolder = stack.pop()) != nullptr) {
        std::cout << stackHolder->data << std::endl;
    }

    stack.is_empty() ? std::cout << "stack is empty" : std::cout << "stack is not empty";
    std::cout << std::endl;

    return 0;
}

stack-with-vector.cc

#include <iostream>
#include <vector>
#include <cstring> // for strdup
#include <memory>  // for unique_ptr
using namespace std;

class Stack {
    vector<char*> data;
public:
    void push(const string& str) {
        char* new_str = strdup(str.c_str());
        if (new_str == nullptr) {
            cerr << "Memory allocation failed." << endl;
            return;
        }
        data.push_back(new_str);
    }

    string pop() {
        if (data.empty()) {
            cerr << "Stack is empty." << endl;
            return "";
        }
        string top(data.back());
        free(data.back());
        data.pop_back();
        return top;
    }

    const char* peak() const {
        if (data.empty()) {
            cerr << "Stack is empty." << endl;
            return nullptr;
        }
        return data.back();
    }

    bool is_empty() const {
        return data.empty();
    }

    size_t size() const {
        return data.size();
    }

    ~Stack() {
        for (char* str : data) {
            free(str);
        }
    }
};

int main() {
    Stack stack;

    cout << "is_empty: " << stack.is_empty() << " size: " << stack.size() << endl;
    
    stack.push("candidate");
    stack.push("M_create");

    cout << "Top element: " << stack.peak() << endl;
    cout << "Popped element: " << stack.pop() << endl;
    cout << "Top element after pop: " << stack.peak() << endl;

    return 0;
}

stack.c

/**
* stack data structure
*/

#include "stdio.h"
#include "stdlib.h"
#include "string.h"

struct Stack {
    char **data;
    int idx;
};

int stack_size(struct Stack*);

void stack_push(struct Stack *sk, const char *str) {
    if (sk->data == NULL) {
        sk->data = (char **) malloc(1 * sizeof(char *));
    } else {
        sk->data = (char **) realloc(sk->data, (stack_size(sk) + 1) * sizeof(char *));
    }

    sk->idx++;
    sk->data[sk->idx] = strdup(str);
}

const char *stack_pop(struct Stack *sk) {

    if (sk && sk->idx > -1) {
        char *c = strdup(sk->data[sk->idx]);

        free(sk->data[sk->idx]);
        sk->data[sk->idx] = NULL;

        sk->idx--;

        return c;
    }

    return NULL;
}

const char *stack_top(struct Stack *sk) {
    return sk->data[sk->idx];
}

int stack_size(struct Stack *sk) {
    return sk->idx + 1;
}

void stack_is_empty() {

}

int main() {
    struct Stack *stack = (struct Stack *) malloc(sizeof(struct Stack));
    stack->idx = -1;
    stack->data = NULL;

    printf("size of stack %d \n", stack_size(stack));

    stack_push(stack, "Hello");
    stack_push(stack, "World");
    stack_push(stack, "World-1");
    stack_push(stack, "World-2");
    stack_push(stack, "World-4");
    stack_push(stack, "World-5");

    printf("size of stack %d \n", stack_size(stack));

    printf("%s \n", stack_top(stack));
    printf("%s \n", stack_pop(stack));
    printf("%s \n", stack_pop(stack));
    printf("%s \n", stack_pop(stack));
    printf("%s \n", stack_pop(stack));
    printf("%s \n", stack_pop(stack));
    printf("%s \n", stack_pop(stack));
    printf("%s \n", stack_pop(stack));

    printf("size of stack %d \n", stack_size(stack));

    return 0;
}

stack.cc

#include "iostream"
#include "cstring"

using namespace std;

class Stack {
private:
    int idx = -1;
    char **data = nullptr;

public:
    Stack() {
        idx = -1;
        data = nullptr;
    }

    void push(const char* str) {
        idx++;
        data = (char **) realloc(data, (idx + 1) * sizeof(char *));
        data[idx] = strdup(str);
    }

    string pop() {
        if (idx < 0)
            return "";

        string top = data[idx];

        free(data[idx]);
        data[idx] = nullptr;
        idx--;

        return top;
    }

    string peak() {
        if (idx < 0)
            return "";

        return data[idx];
    }

    bool is_empty() {
        return idx == -1;
    }

    int size() {
        return idx + 1;
    }

    ~Stack() {
        if (data) {
            for (int i = idx; i >= 0; i--)
                free(data[i]);

            free(data);
        }

        data = nullptr;
        idx = -1;
    }
};

int main() {
    Stack stack;

    cout << "is_empty: " << stack.is_empty() << " size: " << stack.size() << endl;

    stack.push("candidate");
    stack.push("M_create");

    int x = 100;
    while (--x) {
        string str = "candidate " + to_string(x);
        stack.push(str.c_str());

        if (x%3 == 0) {
            cout << stack.pop() << endl;
        }
    }

    cout << stack.peak() << endl;
    cout << stack.pop() << endl;
    cout << stack.pop() << endl;
    cout << stack.pop() << endl;

    cout << "is_empty: " << stack.is_empty() << " - size: " << stack.size() << endl;

    return 0;
}

Stack Data Structure

A stack is a linear data structure that follows the principle of Last In First Out LIFO. This means the last element inserted inside the stack is removed first.

You can think of the stack data structure as the pile of plates on top of another.

Here, you can:

• Put a new plate on top
• Remove the top plate

And, if you want the plate at the bottom, you must first remove all the plates on top. This is exactly how the stack data structure works.