Stack-Implementierung mit verknüpfter Liste

111558
Software Engineer

Dies ist eine Implementierung des Arbeitsstapels, die eine verknüpfte Liste verwendet. Ich bin nur neugierig, ob dies eine gute Methode ist. Anregungen sind willkommen. Können wir die Anzahl der Elemente im Stapel anhand einer countim Code verwendeten Variablen verfolgen ?

#include <cstdlib>
#include<iostream>
using namespace std;

class node
{
 public:
    int data;
    node* next;
};

class StackusingList
{
public:
StackusingList(int max)
{
    top = NULL;
    maxnum = max;
    count=0;
}

void push(int element)
{
    if(count == maxnum)
            cout<<"stack is full";
    else
    {
        node *newTop = new node;
        if(top == NULL)
        {       
            newTop->data = element;
            newTop->next = NULL;
            top = newTop;
            count++;
        }
        else
        {
            newTop->data = element;
            newTop->next = top;
            top = newTop;
            count++;
        }
    }
}

void pop()
{
    if(top == NULL)
            cout<< "nothing to pop";
    else
    {
        node * old = top;
        top = top->next;
        count--;
        delete(old);
    }
}
void print()
{
    node *temp;
    temp = top;
    while(temp!=NULL)
    {
        cout<<temp->data<<",";
        temp=temp->next;
    }
}
private:
    node *top;
    int count; //head
    int maxnum;
    int stackData;      
};

int main(int argc, char** argv) {   
    StackusingList *sl = new StackusingList(5);
    sl->push(1);
    sl->push(2);
    sl->push(3);
    sl->push(4);
    sl->push(5);
    sl->push(6);

    sl->pop();
    cout<<"new stack\n";
    sl->print();

    return 0;
}
Antworten
14

2 Antworten auf die Frage

10
Jamal
  • Irgendwann würde ich empfehlen, templatehier zu verwenden. Auf diese Weise können Sie jeden Datumstyp, nicht nur ints, in Ihrer Struktur speichern .

  • Es wäre besser, nodeals ein structInnen StackusingListals zu definieren private. In Ihrer aktuellen Implementierung werden nodedie Felder nicht ausgeblendet, da sie alle erstellt wurden public.

    class LinkedList
    {
    private:
        struct Node
        {
        };
    
    public:
    
    };
    
  • Ziehen Sie es vor nullptr, NULLwenn Sie C ++ 11 verwenden.

  • StackusingList()sollte eine Initialisierungsliste sein :

    StackusingList(int max) : top(NULL), maxnum(max), count(0) {}
    
  • countsollte vom Typ sein std::size_t.

  • In beiden push()und pop(), müssen Sie, returnwenn der Stapel voll oder leer sind. Andernfalls wird die Funktion weiterhin ausgeführt, wodurch der Zweck der Prüfung missachtet wird.

  • print():

    // no data members are being modified,
    //   so make this const
    void print() const
    {
        // could just be initialized
        // the asterisk is commonly
        //   put next to the type in C++
        node* temp = top;
    
        while (temp)
        {
            cout << temp-> data << ",";
            temp = temp->next;
        }
    }
    
  • Achtung:

    StackusingList *sl = new StackusingList(5);
    

    Sie rufen Sie nicht deletemit diesem new, wodurch ein verursacht Speicherverlust ! Rufen Sie immer delete richtig mit jedem an new .

    Am Ende main()vor dem return:

    delete s1;
    

    Darüber hinaus brauchen Sie hier wirklich nicht zu verwenden new. Es ist nur bei den Knoten notwendig, die Sie bereits tun. Es ist am besten, die manuelle Zuweisung / Freigabe nur so weit wie möglich zu vermeiden.

  • stackData wird nirgendwo verwendet (und hat keine klare Bedeutung), entfernen Sie sie also einfach.

  • Ihnen fehlen einige nützliche publicElementfunktionen:

    std::size_t size() const { return count; } // put into header
    

    bool empty() const { return count == 0; } // put into header
    

    template <typename T>
    T StackusingList<T>::top() const { return top->data; }
    
  • Es gibt keinen Zerstörer! Sie Zuweisen newKnoten, so müssen Sie den destructor definieren, um richtig deletesie:

    StackusingList::~StackusingList()
    {
        node* current = top;
    
        while (current)
        {
            node* next = current->next;
            delete current;
            current = next;
        }
    
        top = NULL;
    }
    

    Mit dem Destruktor definiert, müssen Sie erfüllen die Rule of Three . Dies ist auch wichtig, da der Standardkopierkonstruktor und der Zuweisungsoperator eine flache Kopie von durchführen top. Dies bedeutet, dass der Zeiger selbst anstelle der Daten an diesem Zeiger kopiert wird . Dies führt zu Problemen, wenn Sie versuchen, Listenobjekte zu kopieren oder neue mit vorhandenen Objekten zu initialisieren.

@ Jamal schnelle Frage, warum Sie den Knoten in der privaten Klasse ausblenden? Lamar vor 5 Jahren 0
@Lamour: Es liegt daran, dass es nicht für die öffentliche Benutzeroberfläche zugänglich sein sollte. Jamal vor 5 Jahren 0
3
Martin York

I'm just curious to know if this is a good way of doing it?

No.

Any suggestions are welcome.

Hold On.

Can we keep track of the number of elements in the stack using a count variable as used in the code?

Yep.

Basically your memory management is broken.
When you push elements on you create them with new and when you pop elements off you delete them. But what happens when the stack object goes out of scope? Anything still left in the stack is now leaked.

Also the use of a maximum count in the constructor suggests that you should be allocating a single piece of storage once on construction to store all the values. The point of using a linked list is to allow the list to grow dynamically. It would be a better idea to just create a storage area and keep track of how full it is (if you are allowed to use std::vector in your assignment this does all the hard work for you).

From this:

int main(int argc, char** argv) {   
    StackusingList *sl = new StackusingList(5);

One assumes you have a Java background.
If you don't need your object to live beyond the time span of the function then you don't need use new. What you need is just create a local object.

int main(int argc, char** argv) {   
    StackusingList    sl(5);

This variable is created locally. It is destroyed when the function terminates. If you had written it correctly the destructor would then clean up any internal memory it had allocated.