c++ - 将通用堆栈容器实现为适配器类模板

Question

我在数据结构 (cop 4530) 类(class)中遇到了一些问题。我需要“将通用 Stack 容器实现为适配器类模板”。我的模板和实现位于两个不同的文件 stack.h 和 stack.hpp (这是必需的)。 我想将这个 Stack 设置为一个数组，但如果我没记错的话，我的老师似乎将其设置为一个链表？？ 我只是对如何开始将堆栈设置为数组感到困惑 如果有人可以向我解释(我们有一本非常无用的书)。我真正需要的是有人向我解释我实现 Stack 代码的“.hpp”中的少数函数。特别是复制/移动功能。 (如果我用不同的方式比我尝试的更好或更容易，请分享)

这是 Stack.h；这些都是我们需要包含的“Stack class Template”的接口(interface)

#include <iostream>
#define MAX_SIZE 100

namespace cop4530{

template<typename T>
class Stack{

 private:
 int A[MAX_SIZE];
 int top;

 public:

 Stack();
 ~Stack();
 Stack (const Stack<T>&);
 Stack(Stack<T> &&);
 Stack<T>& operator= (const Stack <T>&);
 Stack<T> & operator=(Stack<T> &&);
 bool empty() const;
 void clear();
 void push(const T& x);
 void push(T && x);
 void pop();
 T& top();
 const T& top() const;
 int size() const;
 void print(std::ostream& os, char ofc = ' ') const;  

}

 //non-member global functions
 std::ostream& operator<< (std::ostream& os, const Stack<T>& a);
 bool operator== (const Stack<T>&, const Stack <T>&);
 bool operator!= (const Stack<T>&, const Stack <T>&);
 bool operator< (const Stack<T>& a, const Stack <T>& b); 

 #include "Stack.hpp"

}

#endif

这里是单独的“Stack.hpp”文件，其中包含其中一些的实现。

#include "stack.h"
#include <iostream>

namespace cop4530{

template<typename T>
Stack<T>::Stack(){
//zero argument constructor
}

template<typename T>
Stack<T>::~Stack(){ //destructor
    clear();
}

template<typename T>
Stack<T>::Stack(const Stack<T>&){ //copy constructor

}

template<typename T>
Stack<T>::Stack(Stack<T> &&){ //move constructor

}

template<typename T>
Stack<T>::Stack<T> & Stack<T>::operator=(const Stack<T> &){
    //copy assignment operator=
}

template<typename T>
Stack<T>::Stack<T> & Stack<T>::operator=(Stack<T> &&){
    //move assignment operator=
}

/*does this look right? I don't think so...*/
template<typename T>
void Stack<T>::push(const T& x){ //adds x to the stack, copy version
    insert(begin(), x);
}

template<typename T>
void Stack<T>::push(T && x){ // adds x to the stack, move version
    insert(begin(), std::move(val));
}

Answer 1

要将堆栈实现为数组的适配器类，您应该真正从堆栈的基本功能开始。让我们考虑一些基础知识:

• 构造函数 - 创建一个空堆栈

• isFull/isEmpty - 根据堆栈中的可用空间大小返回 true/false。

• push - 在队列顶部添加一个元素

• pop - 从队列顶部移除第一个元素

让我们从构造函数开始:您可以说当top == -1 时您的堆栈是空的。由于您的数组是静态分配的(您可以考虑在构造函数中为数组动态分配内存)，您需要做的就是 top =-1 并且您自己有一个空堆栈.

isFull/isEmpty 现在变得很明显了:

• isEmpty: 返回顶部 == -1

• 已满:返回顶部 == MAX_SIZE

PUSH:向栈顶添加一个元素:

    if (!isFull)
    {
       top++;
       A[top] = new_element;
    }

我会让你想出剩下的；这个想法是更新 stack pointer top 并始终关注您有多少可用空间。