Array and Linked List Implementation of Stack

Question

I've implemented both as follows. Could someone be kind enough to just play around with various inputs and let me know if there are any bugs?

#include <iostream>

using namespace std;

/***************************************************************************/

class AStack {
    public:
        AStack(int);
        ~AStack();
        void push(int);
        int pop();
        int top();
        bool isEmpty();
        void Flush();

    private:
        int capacity ;
        int* a;
        int index = -1; // Index of the top most element
};

AStack::AStack(int size) {
    a = new int[size];
    capacity = size;
}

AStack::~AStack() {
    delete[] a;
}

void AStack::push(int x) {
    if (index == capacity - 1) {
        cout << "\n\nThe stack is full. Couldn't insert " << x << "\n\n";
        return;
    }
    a[++index] = x;
}

int AStack::pop() {
    if (index == -1) {
        cout << "\n\nNo elements to pop\n\n";
        return -1;
    }
    return a[index--];
}

int AStack::top() {
    if (index == -1) {
        cout << "\n\nNo elements in the Stack\n\n";
        return -1;
    }
    return a[index];
}

bool AStack::isEmpty() {
    return (index == -1);
}

void AStack::Flush() {
    if (index == -1) {
        cout << "\n\nNo elements in the Stack to flush\n\n";
        return;
    }
    cout << "\n\nFlushing the Stack:  ";
    while (index != -1) {
        cout << a[index--] << "  ";
    }
    cout << endl << endl;
}

/***************************************************************************/

class LLStack {
    public:
        struct Node {
            int data;
            Node* next;
            Node(int n) {
                data = n;
                next = 0;
            }
            Node(int n, Node* node) {
                data = n;
                next = node;
            }
        };
        LLStack();
        ~LLStack();
        void push(int);
        int pop();
        int top();
        bool isEmpty();
        void Flush();

    private:
        Node* head;

};

LLStack::LLStack() {
    head = 0;
}

LLStack::~LLStack() {
    this->Flush();
}

void LLStack::push(int x) {
    if (head == 0) head = new Node(x);
    else {
        Node* temp = new Node(x, head);
        head = temp;
    }
}

int LLStack::pop() {
    if (head == 0) {
        cout << "\n\nNo elements to pop\n\n";
        return -1;
    }
    else {
        Node* temp = head;
        int n = temp->data;
        head = temp->next;
        delete temp;
        return n;
    }
}

int LLStack::top() {
    if (head == 0) {
        cout << "\n\nNo elements in the stack\n\n";
        return -1;
    }
    else {
        return head->data;
    }
}

bool LLStack::isEmpty() {
    return (head == 0);
}

void LLStack::Flush() {
    while (head != 0) {
        Node* temp = head;
        head = head->next;
        delete temp;
    }
}


/***************************************************************************/

int main() {
    // Insert code here to play around
    return 0;
}

That could imply that you haven't tested it yourself. We prefer to see that done first. — Jamal
– Jamal, Commented Mar 11, 2015 at 18:22
Apart from the bug Loki mentioned I think your code works but the question as it stands is not a very good question for code review. What you should do is write some tests and to verify that it's working and then ask for improvements. — ChrisWue
– ChrisWue, Commented Mar 11, 2015 at 19:13

Community · Accepted Answer · 2017-05-23 11:33:42Z

Don't do this:

using namespace std;

See: Why is “using namespace std;” considered bad practice?

Your class contains a RAW pointer:

int* a;

But you do not implement the rule of three.
see: What is The Rule of Three?

But basically boils down to:

int main()
{
     AStack    a(5);
     AStack    b(a);
}
// Code blow up here.
// Because you have a double delete on the pointer.

0 is not a pointer:

head = 0;

You want to use the keyword nullptr if you have C++11 or later. Failing that use the macro NULL. This at least gives you a visual clue that you are working with pointers.

Simplification:

if (head == 0) head = new Node(x);
else {
    Node* temp = new Node(x, head);
    head = temp;
}

Can this not just be simplified too:

head = new Node(x, head);

Loki Astari · Accepted Answer · 2015-03-11 23:23:55Z

Your naming conventions are a bit inconsistent. Flush is PascalCase while the other methods are camelCase. Try to be consistent as it improves readability.
Flush shouldn't dump the contents of the stack to stdout. Getting the entire content of the stack in one operation should be a separate method if it's needed. Flush should simply clear the data. I would also suggest that clear() might be a better name for it.
Why is struct Node public? The user of you class never gets exposed to the internals so why would they need to know about Node?
The constructor for node has some bad parameter names. Better would be Node(int value, Node* next)
In general your methods write error messages to stdout. If anything they should go to stderr. But logging of errors should really be a separate concern. I would even argue that in the cases where you log an error those could be considered exceptional cases violating the contract of the structure and you could throw some sort of InvalidOperationException. I'm doing mainly C# these days for production code so not sure what the general C++ recommendation is.
push() in AStack should return a bool indicating whether or not the operation succeeded. Right now someone pushing an element on the stack has no way of finding out whether it succeeded or not and they cannot check beforehand either (see below).
pop() in SStack could potentially return void. see: why does std::stack::pop() returns void
Given that AStack has a limited capacity it should provide a isFull() method and probably a capacity() method to query what the capacity is.
Your data structures should provide a size() method so users can query how many elements are currently stored.

+1: Added one more point as it fitted nicer in your list style than in my rant style. Hope you don't mind. — Loki Astari
– Loki Astari, Commented Mar 11, 2015 at 23:24

Stack Exchange Network

Array and Linked List Implementation of Stack

2 Answers 2

Don't do this:

Your class contains a RAW pointer:

0 is not a pointer:

Simplification:

You must log in to answer this question.

Hot Network Questions

Array and Linked List Implementation of Stack

2 Answers 2

Don't do this:

Your class contains a RAW pointer:

0 is not a pointer:

Simplification:

You must log in to answer this question.

Related

Hot Network Questions