模板堆栈和LIFO C ++ [英] Template Stack and LIFO C++

问题描述

所以我想学习的模板和Fifo和Lifo堆栈的东西。我一直在玩一些代码来处理这个，我可以获得int数据做我想要的测试，但我不能为我的生活找出如何使用一个字符串。
我的代码不断崩溃对我，但不给我任何错误的方式，所以我想我会在这里流行，看看是否有人可以告诉我，我做错了。这是我的代码：

So I'm trying to learn about Templates and the Fifo and Lifo stack stuff. I've been playing around with some code that deals with this, and I can get the int data to do what I want for testing but I can't for the life of me figure out how to get this to work with a string. The way I have the code keeps crashing on me, but doesn't give me any errors, so I thought I'd pop in here and see if anybody could tell me what I'm doing wrong. Here's my code:

-----------//my header//---------------------

#include <stdlib.h>
#include <iostream>
#include <string>

#ifndef STACK_H_
#define STACK_H_

template<class T> 
class StackTest
{

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

public:
StackTest(int size){
    stackData = new T[size];//to hold the T ‌type data items 
    top = -1;//no items on the stack
    maxSize = size;//set maximum size that stack can hold
}

virtual ~StackTest(){}

int count(){
    return top + 1;
}

bool isEmpty(){
    return top == -1 ? true : false;
}

bool isFull(){
    return top == maxSize - 1 ? true : false;
}

T* peek(){
    if(!isEmpty())//check for empty
        return &stackData[top - 1];
}

T* pop(){
    if(!isEmpty()){
        top -= 1;//decrease the top by 1 to indicate the delete
        return &stackData[top];//return deleted item
    }
    return NULL;
}

void push(T* item){
    stackData[top++] = *item;//insert to data array and increase the top by one 
}
};


#endif /* STACK_H_ */

-----------//my main//---------------

#include <iostream>
#include <string>
#include "Pair.h"

using namespace std;

int main() {

int dataTest;
string strTest;
StackTest<int> intStack(10);
StackTest<string> stringStack(50);

//Insert data into the stack
dataTest = 3;
intStack.push(&dataTest);
dataTest = 4;
intStack.push(&dataTest);
dataTest = 5;
intStack.push(&dataTest);
dataTest = 6;
intStack.push(&dataTest);
strTest = "test";
stringStack.push(&strTest);

//Show the top item
cout << *intStack.peek() << endl;
cout << *stringStack.peek() << endl;

//Pull the top item out (twice)
intStack.pop();
intStack.pop();

//Show the new top item
cout << *intStack.peek() << endl;

return 0;
}

所以如果有人觉得给我一些指针，我会真的很感激，谢谢。

So if anyone feels like giving me some pointers I would really appreciate it, thanks.

推荐答案

您的实现有一些问题。其中最微妙的是 push（）成员函数：

There are a few issues with your implementation. One of the most subtle is in the push() member function:

void push(T* item){
    stackData[top++] = *item; //insert to data array and increase the top by one
    //           ^^
    //           You want pre-increment here!
}

这是增加 top old 值作为 stackData 的索引。因为 top 是 -1 ，当堆栈为空时，您的程序实际上是：

This is incrementing top and using the old value as an index into stackData. Since top is -1 when the stack is empty, your program is actually doing:

stackData[-1] = *item;
top = 0;

不用说，第一次赋值会导致未定义的行为。

Needless to say that the first assignment results in undefined behavior.

另一个未定义行为的来源是 peek（）成员函数，空：

Another source of undefined behavior is the peek() member function, which does not return anything when the stack is empty:

T* peek(){
    if(!isEmpty())//check for empty
        return &stackData[top - 1];
}

根据C ++ 11标准的第6.6.3 / / p>

Per paragraph 6.6.3/2 of the C++11 Standard:

[...]流出函数的末尾相当于没有值的返回;这导致在一个值返回函数中未定义的
行为。

[...] Flowing off the end of a function is equivalent to a return with no value; this results in undefined behavior in a value-returning function.

但这不是唯一的问题：可以访问 stackData ：

But that's not the only issue: the other problem is with the access of stackData:

return &stackData[top - 1];

当 top 不等于或大于这也会导致未定义的行为，因为您将获取位于数组中负数地址的（非）对象的地址。

When top is not equal to or greater than one, this will also result in undefined behavior, since you would be taking the address of a (non-)object located at a negative address in the array.

此外， ，我建议重写 isEmpty（）和 isFull（）如下：

Also, I suggest to rewrite isEmpty() and isFull() as follows:

bool isEmpty(){
    return (top == -1);
}

bool isFull(){
   return (top == maxSize - 1);
}

作为一般建议，请不要使用值 -1 为 top 。 正如Ben Voigt在评论中提到的，这将引导您前往很多一对一的错误。

As a general advice, consider not using the value -1 for top when the stack is empty. As Ben Voigt mentions in the comments, this is leading you to a lot of off-by-one errors.

此外，正如DyP 指出的，你的析构函数并不释放在构造函数中分配的内存，所以你的 StackTest 对象泄漏内存。在这之后，由于我们在它，你可能想看看所谓的 Rule of Three ，您的程序将违反。

Also, as pointed out by DyP, your destructor is not freeing the memory allocated in the constructor, so your StackTest object is leaking memory. And after doing that, since we're at it, you may want to have a look at the so-called Rule of Three, that your program would be violating.

这篇关于模板堆栈和LIFO C ++的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！