1

I just implemented a stack using an array and am curious as to why people start their tops at -1. Is it more inefficient to start at 0? I have a programming assignment to implement a stack that performs basic functions, and tried doing it on my own first.

After I got it to work I looked around to see other implementations. Most people start their tops at -1. Is there a benefit to that? Is it wrong to start at 0?

here's my working code:

header file: 
#ifndef H_Stack
#define H_Stack

#include <iostream>
using namespace std;

struct nodeType
{
    int info;
    nodeType *link;
};

class arrayStack
{
private:
    int stackSize;
    int stackTop;
    int *stackArray;

public:
    arrayStack(const int &x);
    void push(const int &x);
    bool is_full();
    bool is_empty();
    int size();
    int top();
    void pop();
    ~arrayStack();
};

class linkedStack
{
private:
    nodeType *stackTop;

public:
    linkedStack();
    void push(const int &x);
    int size();
    int top();
    void pop();
    bool is_empty();
    ~linkedStack();
};

#endif

Imp file:

#include "stack.h"

#include <iostream>
#include <cassert>
using namespace std;

arrayStack::arrayStack(const int &x)
{
    if (x <= 0)
    {
        stackSize = 20;
        stackArray = new int[stackSize];
    }

    else
    {
        stackTop = 0;
        stackSize = x;
        stackArray = new int[stackSize];
    }
}

bool arrayStack::is_full()
{
    return (stackTop == stackSize);
}

void arrayStack::push(const int &x)
{
    if (!is_full())
    {
        stackArray[stackTop] = x;
        stackTop++;
    }
}

bool arrayStack::is_empty()
{
    return (stackTop == 0);
}

int arrayStack::size()
{
    return stackSize;
}

int arrayStack::top()
{
    assert(stackTop != 0);

    return stackArray[stackTop - 1];
}

void arrayStack::pop()
{
    if (!is_empty())
        stackTop--; 

    else
    {
        cout << "can't pop from an empty stack.";
    }
}

arrayStack::~arrayStack()
{
    delete[] stackArray; 
}

linkedStack::linkedStack()
{
    stackTop = nullptr;
}

void linkedStack::push(const int &x)
{
    nodeType *newNode;
    newNode = new nodeType;
    newNode->info = x;
    newNode->link = stackTop;
    stackTop = newNode;
}

int linkedStack::size()
{

    int count = 0;
    nodeType *temp;
    temp = stackTop;

    while (temp != nullptr)
    {
        temp = temp->link;
        count++;
    }

    return count;
}

int linkedStack::top()
{
    assert(stackTop != nullptr);

    return stackTop->info;
}

void linkedStack::pop()
{
    assert(!is_empty());

        nodeType *temp = stackTop;
        stackTop = stackTop->link;
        delete temp;

}

bool linkedStack::is_empty()
{
    return (stackTop == nullptr);
}

linkedStack::~linkedStack()
{
    while (stackTop != nullptr)
    {
        pop();
    }
}

it successfully pops/pushes. It is not circular so its not efficient or very useful... but I had to write it for school.

5
  • 1
    Please, remove that using namespace std; from your header file. Commented Mar 13, 2020 at 16:32
  • What's wrong with std::stack that makes you feel you need to roll your own? Commented Mar 13, 2020 at 16:33
  • @JesperJuhl I have to implement one for school. There's nothing wrong with the built in one Commented Mar 13, 2020 at 16:35
  • Having top be -1 can be an easy way of showing the stack is currently empty. leaving top at index 0 can imply to some people that index 0 is being used. But again, this is all just programming methods. If you feel more comfortable leaving top at 0 and your stack works properly, more power to you. Commented Mar 13, 2020 at 16:35
  • @izzyk2517 All right. No problem :) was just currious and missed the "for school" bit when I read your question. Commented Mar 13, 2020 at 16:37

1 Answer 1

2

Using an initial top of -1 allows you to implement push with just:

    stackArray[++stackTop] = x;

That said, an initial top of 0 would just need an equally efficient, if slightly more verbose two-liner:

    stackArray[stackTop] = x;
    ++stackTop;

or to keep it a one-liner:

    stackArray[stackTop++] = x;

where the latter is perfectly fine as long as the top is a primitive type (for user-defined classes, post-increment is significantly less efficient, as it necessarily involves a complete copy of the state; some people avoid post-increment in C++ in general to develop habits that don't cause problems for user-defined classes).

Point is, there is no special benefit to -1 vs. 0; there may be conventions shared by the code you're looking at, but all of it works.

Sign up to request clarification or add additional context in comments.

3 Comments

Thats interesting, so doing ++x is more efficient than x++. I didn't know that. I thought they both made a copy of the variable and added one to the value. How does ++c work if it doesn't do that?
It's called preincrement and post increment, there are lots of articles that go into detail on the differences, strategies, etc, that may be out of place for this comment thread! Check it out! :)
@izzyk2517: To be clear, they're both equally efficient in your code, since stackTop is a plain int. It's only class types (including stuff like iterators), with explicit overloads for operator++() and operator++(int), where the efficiency issues come in. Pre-increment can modify the instance in place, and return a reference to that instance; post-increment must make a copy of the instance, then increment itself in place, then return the copy. With int, it's fine either way, but using pre-increment by default is a good habit to have.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.