c++ - 使用数组实现堆栈

Question

我只是使用数组实现了一个堆栈，并对为什么人们以-1开始他们的顶峰感到好奇。从0开始效率更低吗？我有一个编程任务来实现执行基本功能的堆栈，并尝试自己做一个。

在使它起作用之后，我环顾四周以查看其他实现。大多数人以-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

曝光文件:

#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;

只要top是原始类型，后者就可以了(对于用户定义的类，后递增的效率明显较低，因为它必然包含状态的完整副本；有些人在C++中避免了后递增通常会养成不会对用户定义的类造成问题的习惯)。

重点是， -1和 0没有什么特别的好处；您正在查看的代码可能共享一些约定，但是所有约定都可以使用。