了解堆栈数据结构并实现它 [英] Understanding Stack Data Structure and Implementing it

问题描述

请查看以下代码

template <typename T>

class Stack
{
public:
    Stack(int number)
    {
        maxSize = number;
        top = -1;
        stackData = new T*(maxSize);
    }

    ~Stack()
    {
        delete [] stackData;
    }

    int count()
    {

    }

    bool isEmpty()
    {
        if(top==-1)
        {
            return true;
        }
        else
        {
            return false;
        }
    }

    bool isFull()
    {
        if(top== (maxSize-1))
        {
            return true;
        }
        else
        {
            return false;
        }
    }

    *T pop()
    {
        if(!isEmpty())
        {
            return stackData[top--]; // Remove Item From Stack
        }
    }

    *T peek();

    void push(T *pushValue)
    {
        if(!isFull())
        {
            stackData[++top] = pushValue;
        }
    }

private:
    int maxSize;
    T ** stackData;
    int top;
};

在上面的代码中，注释行表示从堆栈中删除项目。但实际上，它不是删除，它只是提供一个值背后的价值，对吧？在这里，我指的是删除作为完全从堆栈中销毁特定的值。

In the above code, the commented line says "Removing Item from the Stack". But actually, it is not removing, it is simply providing the value which is one value behind, right? In here, I refer removing as completely destroying that particular value from the stack.

例如：在包含数据1,2,3,4的数组中，删除'2'。所以现在是1,3,4

ex: In an array which contains data 1,2,3,4 I remove '2'. So now it is 1,3,4

其次，在peek（）方法中应该发生什么？

Second, what should happen inside the "peek()" method?

第三，有没有我没有检测到的错误？

Third, are there are any errors that I didn't detect?

请帮助！

推荐答案

在概念上，递减顶部和项目。单词remove是一个概念性抽象，用于描述堆栈中顶层项不再是堆栈中的元素的概念。

Conceptually, there is no difference between decrementing top and "removing" the top item. The word "remove" is a conceptual abstraction to describe the idea that the top item in the stack is no longer an element in the stack. The fact that it is not literally removed from that location in memory is irrelevant.

如果你想销毁顶层项目，即调用它的顶层项目析构函数和释放它，你需要考虑你的 Stack 类如何管理内存的更大的含义。如果栈应该拥有每个 T 对象的所有权，并且每个 T 对象已经使用 new ，那么你可以让 pop（）函数 delete 项目在递减 top 之前。 （但是 pop（）不能返回指向删除的元素的指针。）如果堆栈不取得每个项目的所有权，那么由 pop（）的调用者来管理元素的生存期/取消分配。

If you mean you want to "destroy" the top item, i.e. invoke it's destructor and deallocate it, you need to consider the larger implications of how your Stack class manages memory. If the stack is supposed to take ownership of each T object, and each T object has been allocated using new, then you can have your pop() function delete the top item before decrementing top. (But then pop() can't return a pointer to the deleted element.) If the stack doesn't take ownership of each item, then it is up to the caller of pop() to manage the lifetime/deallocation of the element.

下一页， peek（）方法只是返回一个指向顶层项的指针，而不从堆栈中删除。

Next, the peek() method simply returns a pointer to the top item, without removing it from the stack.

最后，你没有正确分配 T * 指针的数组。语法应为：

And finally, you are not correctly allocating the array of T* pointers. The syntax should be:

stackData = new T*[maxSize];

您发布的代码在 new 后使用括号而不是括号，这不是你想要的。

The code you posted uses parentheses after new instead of brackets, which is not what you want here.

这篇关于了解堆栈数据结构并实现它的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！