Реализация стека с использованием массива

Question

Я только что реализовал стек, используя массив, и мне любопытно, почему люди начинают свои топы с -1. Разве неэффективно начинать с 0? У меня есть программирование для реализации стека, который выполняет основные функции c, и я попытался сделать это самостоятельно.

После того, как я заставил его работать, я оглянулся, чтобы увидеть другие реализации. Большинство людей начинают свои вершины с -1. Есть ли польза от этого? Это неправильно начинать с 0?

вот мой рабочий код:

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:

#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();
    }
}

он успешно всплывает / толкает. Это не круговое, так что это не эффективно или очень полезно ... но я должен был написать это для школы.

Answer 1

Использование начальной вершины -1 позволяет вам реализовать push с помощью всего лишь:

    stackArray[++stackTop] = x;

Тем не менее, для начальной вершины 0 просто потребуется такой же эффективный, если немного больше многословный двухслойный:

    stackArray[stackTop] = x;
    ++stackTop;

или чтобы сохранить его однострочным:

    stackArray[stackTop++] = x;

, где последний идеально подходит до тех пор, пока вершина является примитивным типом (для пользовательских классов постинкремент значительно менее эффективен, так как он обязательно включает в себя полную копию состояния; некоторые люди избегают постинкремента в C ++ в целом, чтобы развить привычки, которые не вызывают проблем у пользователя -определенные классы).

Дело в том, что нет особых преимуществ для -1 против 0; в коде, который вы просматриваете, могут быть общие соглашения, но все это работает.