如何使用模板在 cpp 中使用 LINKED LIST 实现 STACK

Question

所以我正在尝试创建一个实现堆栈及其所有功能（push、pop、getTop 等）的 C++ 文件。我想使用模板，以便为多种数据类型制作此 Stack class。我正在使用链表来存储数据。这是我使用链表实现的一些堆栈示例。

#include<iostream>
using namespace std;

template <class T>

class Node{
public:
      T data;
      Node *next;
      Node()
      {
            next = NULL;
      }
};

class Stack
{
      Node *top;
public:
      Stack();
      int isEmpty();
      int isFull();
      void push(T data);
      T pop();
      void display();
};

Stack :: Stack()
{
      top = NULL;
}

int Stack :: isEmpty()
{
      if(top == NULL)
      {
            return 1;
      }
      else
      {
            return 0;
      }
}

int Stack :: isFull()
{
      int temp;
      Node *t = new Node;

      if(t==NULL)
      {
            temp = 1;
      }
      else
      {
            temp = 0;
      }

      delete t;
      return temp;
}

void Stack :: push(T data)
{
      Node *n;

      if(isFull())
      {
            cout<<"\nStack overflow";
      }
      else
      {
            n = new Node;
            n->data = data;
            n->next = top;
            top = n;
      }

}

int Stack :: pop()
{
      Node *t;
      T temp;

      if(isEmpty())
      {
            return temp;
      }
      else
      {
            t = top;
            top = top->next;
            temp = t->data;
            delete t;
            return temp;
      }
}

void Stack :: display()
{
      Node *p = top;
      while(p != NULL)
      {
            cout<<"\n"<<p->data;
            p = p->next;
      }
}

所以这是我正在尝试做的事情的预览，但我不想为不同的数据类型创建不同的节点和堆栈 class。我怎样才能使用模板来实现。我自己试过了，但我遇到了很多错误，而且似乎无法理解为什么。谢谢

Answer 1

你可以像下面这样实现：

#include<iostream>
using namespace std;

template <typename Type>
class Node
{
public:
    Type data;
    Node<Type> *next;
};

template <typename Type>
class Stack
{
public:
    Node<Type> *top;
    void push(Type data);
    Type pop();
};


int main()
{

}

Answer 2

我建议将 Node 变成 Stack 的内部 class。不需要用户能够看到它。

#include<iostream>
#include<utility>

template<class T>
class Stack {
    struct Node {  // inner class
        T data;
        Node *next;
    };

    Node* top = nullptr;
    size_t m_size = 0;

public:
    Stack() = default;

    // rule of five - no copying, only moving allowed
    Stack(const Stack&) = delete;
    Stack(Stack&& rhs) noexcept :
        top(std::exchange(rhs.top, nullptr)), m_size(rhs.m_size) 
    {}
    Stack& operator=(const Stack&) = delete;
    Stack& operator=(Stack&& rhs) noexcept {
        std::swap(top, rhs.top);
        m_size = rhs.m_size;
        return *this;
    }
    ~Stack() {
        while(top) {
            delete std::exchange(top, top->next);
        }
    }

    bool empty() const { return m_size == 0; }
    size_t size() const { return m_size; }

    void push(const T& data) {
        top = new Node{data, top};
        ++m_size;
    }

    T pop() {
        T rv = std::move(top->data);
        delete std::exchange(top, top->next);
        --m_size;
        return rv;
    }
};

Demo

Answer 3

用链表实现堆栈只需要简单地私下存储一个链表，并用堆栈的接口对其进行约束。约束是关键。模板参数是您存储在堆栈中的类型。

最简单的*方法是花时间实现一个链表很好，这样你只需要担心在你的堆栈中约束它class 而不是编写链表使其在堆栈中表现得像堆栈 class。这里发挥作用的原则称为关注点分离。

为简单起见，这里有一个使用 std::list 的简单示例：

template <typename T>
class Stack {
 public:
  Stack() = default;
  Stack(T val) : m_stack(val) {}
  void push(T val) { m_stack.push_front(val); }
  T& top() { return m_stack.front(); }
  void pop() {
    if (!m_stack.empty()) m_stack.pop_front();
  }
  bool empty() const { return m_stack.empty(); }

 private:
  std::list<T> m_stack{};
};

如果您希望在堆栈中抛出异常，则 pop() 函数中可能不需要 if 语句。

这是测试堆栈的main()：

int main() {
  Stack<int> s1;
  for (int i = 1; i < 11; ++i) s1.push(i);
  while (!s1.empty()) {
    std::cout << s1.top() << ' ';
    s1.pop();
  }
  std::cout << '\n';

  Stack<char> s2('A');
  for (char l = 'B'; l != 'K'; ++l) s2.push(l);
  while (!s2.empty()) {
    std::cout << s2.top() << ' ';
    s2.pop();
  }
  std::cout << '\n';
}

我只包含 <iostream> 和 <list>。输出：

10 9 8 7 6 5 4 3 2 1 
J I H G F E D C B

我可以避免很多不必要的工作，例如 5 条规则，因为 std::list 为我处理了所有这些工作。所以我对编译器提供的复制和移动构造函数和析构函数很好。

* 这说起来容易做起来难。我为这些具体问题保留了一个简单的链表，它仍然是大约 130 行代码，并且不具备适当约束以像我用 std::list 演示的那样表现得像堆栈所需的所有功能。 =23=]

如果您已经编写过链表，堆栈应该非常简单，因为成功编写链表需要展示极其广泛的 C++ 知识和编程原则。

如何使用模板在 cpp 中使用 LINKED LIST 实现 STACK

How to use template for implementing STACK using LINKEDLIST in cpp

c++

templates

linked-list

stack