C++ Stack используя двусвязный список

Question

Я пытаюсь реализовать стек, используя двойной список. Я знаю, что функции для моего класса стека (push, pop) должны содержать вызовы функций-членов моего дважды связанного класса списка, но у меня возникают проблемы с его реализацией.

dlist.cpp:

#include <iostream> 
#include <fstream> 
#include <string> 
#include "dlist.hpp" 

using namespace std; 

void dlist::appendNodeFront(int shares, float pps){ 
    Node *n = new Node(shares, pps); 
    if(front == NULL){ 
    front = n; 
    back = n; 
    } 
    else { 
    front->prev = n; 
    n->next = front; 
    front = n; 
    } 
} 

void dlist::appendNodeBack(int shares, float pps){ 
    Node *n = new Node(shares, pps); 
    if(back == NULL){ 
    front = n; 
    back = n; 
    } 
    else { 
    back->next = n; 
    n->prev = back; 
    back = n; 
    } 
} 

void dlist::display(){ 
    Node *temp = front; 
    cout << "List contents: "; 
    while(temp != NULL){ 
    cout << temp->value << " "; 
    temp = temp->next; 
    } 
    cout << endl; 
} 

void dlist::display_reverse(){ 
    Node *temp = back; 
    cout << "List contents in reverse: "; 
    while(temp != NULL){ 
    cout << temp->value << " "; 
    temp = temp->prev; 
    } 
    cout << endl; 
} 

void dlist::destroyList(){ 
    Node *T = back; 
    while(T != NULL){ 
    Node *T2 = T; 
    T = T->prev; 
    delete T2; 
    } 
    front = NULL; 
    back = NULL; 
} 

stack.cpp:

#include <iostream> 
#include <fstream> 
#include <string> 
#include "stack.hpp" 

using namespace std; 

stack::stack(){ 
    int i; 
    for(i = 0; i < 1500; i++){ 
    shares[i] = 0; 
    pps[i] = 0; 
    } 
    first = 0; 
} 

void stack::push(int num, float price){ 
    if(first ==(1500-1)){ 
    cout << "Stack is full" << endl; 
    return; 
    } 
    first++; 
    shares[first] = num; 
    pps[first] = price; 

    return; 
} 

void stack::pop(int *num, float *price){ 
    if(first == -1){ 
    cout << "Stack is empty" << endl; 
    return; 
    } 

    num = &shares[first]; 
    price = &pps[first]; 

    cout << shares[first] << endl; 
    cout << pps[first] << endl; 
    shares[first] = 0; 
    pps[first] = 0; 
    first--; 
    return; 
} 

Если функция толчок в стеке быть в основном вызов appendNodeFront() или appendNodeback()? Любая помощь или совет приветствуются!

Answer 1

Вы можете создать класс стека, а затем использовать класс связанного списка в качестве своего контейнера. В классе связанных списков практически нет ограничений на количество элементов, поэтому вы добавляете искусственный лимит, чтобы заставить его работать как стек. В связанном списке элементы могут быть добавлены/удалены в любом месте списка, вы можете ограничить добавление/удаление хвостового узла только для того, чтобы он работал как стек. Пример ниже демонстрирует использование.

Узел, что это чисто упражнение по программированию. Стек относительно примитивен по сравнению с двойным списком. Инкапсуляция связанного списка внутри стека не имеет преимущества. Также заметьте, я объявил всем членам как public ради упрощения задачи, вы можете захотеть изменить некоторые члены к protected/private

#include <iostream> 
#include <fstream> 
#include <string> 

using std::cout; 

class Node 
{ 
public: 
    Node *prev; 
    Node *next; 
    int shares; 
    float pps; 
    Node(int vshares, float vpps) 
    { 
     shares = vshares; 
     pps = vpps; 
     prev = next = nullptr; 
    } 
}; 

class dlist 
{ 
public: 
    Node *head; 
    Node *tail; 

    dlist() 
    { 
     head = tail = nullptr; 
    } 
    ~dlist() 
    { 
     destroy(); 
    } 

    void push_back(int shares, float pps) 
    { 
     Node *node = new Node(shares, pps); 
     if (head == NULL) 
     { 
      head = tail = node; 
     } 
     else 
     { 
      tail->next = node; 
      node->prev = tail; 
      tail = node; 
     } 
    } 

    void destroy() 
    { 
     Node *walk = head; 
     while (walk) 
     { 
      Node *node = walk; 
      walk = walk->next; 
      delete node; 
     } 
     head = tail = nullptr; 
    } 
}; 

class stack 
{ 
public: 
    int maxsize; 
    int count; 
    dlist list; 
    stack(int size) 
    { 
     count = 0; 
     maxsize = size; 
    } 

    void push(int num, float price) 
    { 
     if (count < maxsize) 
     { 
      list.push_back(num, price); 
      count++; 
     } 
    } 

    void pop() 
    { 
     Node *tail = list.tail; 
     if (!tail) 
     { 
      //already empty 
      return; 
     } 

     if (tail == list.head) 
     { 
      //only one element in the list 
      delete tail; 
      list.head = list.tail = nullptr; 
      count--; 
     } 
     else 
     { 
      Node *temp = list.tail->prev; 
      delete list.tail; 
      list.tail = temp; 
      list.tail->next = nullptr; 
      count--; 
     } 
    } 

    void display() 
    { 
     Node *walk = list.head; 
     while (walk) 
     { 
      cout << "(" << walk->shares << "," << walk->pps << ") "; 
      walk = walk->next; 
     } 
     cout << "\n"; 
    } 
}; 

int main() 
{ 
    stack s(3); 
    s.push(101, 0.25f); 
    s.push(102, 0.25f); 
    s.push(103, 0.25f); 
    s.push(104, 0.25f); 
    s.display(); 
    s.pop(); 
    s.display(); 
    return 0; 
}