Need Some Help Understanding Stack Implementation of Linked Lists

[leo255]

Hi guys,

Not sure if this should be in the beginner section. Perhaps it should be.

I have this code that I need to memorize for my final. Memorizing code is easy for me, but I'm trying pretty hard to fundamentally understand the functions, and what they are doing (even using pen and paper, to draw and trace).

I understand what linked lists do and what they are, but some parts of the code kind of confuse me. For example, in the push function below, I understand everything, except why I'm setting ptr = p. I feel like p should be equal to NULL, then the next node I push should be equal to p, etc.

Stack & Stack::push(double x)
{

    Node * p = NULL;

    try
    {
        p = new Node;
    }

    catch(const bad_alloc &)
    {
        die("Stack::push: Alloc. failure");
    }

    p->data = x;
    p->next = ptr;

    ptr = p;

    return *this;
}

The next function I'm trying to understand is the pop function. We are returning a double. I'm confused as to why we need to create a temporary Node * p, and then delete it.

double Stack::pop()
{
    if (ptr == NULL) die("Stack::pop: underflow");

    Node * p = ptr;
    double x = ptr->data;
    ptr = ptr->next;
    delete p;

    return x;

}

Also, are LL Queues that hard to implement once you can do them w/stacks - That will probably be something I have to code for my final, as well.

Below is the full code for my Stack class.

Thanks.

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

using namespace std;

class Stack
{

public:

    Stack();
    ~Stack();
    Stack & push(double x);
    double pop();
    double top() const;
    const Stack & show() const;
    unsigned size() const;

private:

    struct Node
    {
        double data;
        Node * next;
    };

    Node * ptr;

};

void die(const string & msg);

int main()
{

    Stack s;

    s.push(2.2).push(3.3).push(4.4);

    s.show();
    s.pop();

    cout << endl;

    s.show();

    return 0;
}

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

Stack::~Stack()
{
    for (Node * p; ptr; ptr = p)
    p = ptr->next;

    delete ptr;
}

Stack & Stack::push(double x)
{

    Node * p = NULL;

    try
    {
        p = new Node;
    }

    catch(const bad_alloc &)
    {
        die("Stack::push: Alloc. failure");
    }

    p->data = x;
    p->next = ptr;

    ptr = p;

    return *this;
}

double Stack::top() const
{
    if (ptr == NULL) die("Stack::top: underflow");
    return ptr->data;
}

double Stack::pop()
{
    if (ptr == NULL) die("Stack::pop: underflow");

    Node * p = ptr;
    double x = ptr->data;
    ptr = ptr->next;
    delete p;

    return x;

}

unsigned Stack::size() const
{

    unsigned count = 0;
    for (Node * p = ptr; ptr != NULL; p = p->next)

    count++;

    return count;

}

const Stack & Stack::show() const
{

    for(  Node * p = ptr;  p != NULL;  p = p->next  ){
    cout  << p->data << endl;

    }
    return *this;
}

void die(const string & msg)
{
    cerr << "Fatal error: " << msg;
    exit(EXIT_FAILURE);
}

[helios]

except why I'm setting ptr = p. I feel like p should be equal to NULL, then the next node I push should be equal to p, etc.

I suggest you make this change and step the code through a debugger.

I'm confused as to why we need to create a temporary Node * p, and then delete it.

What would be the alternative?

Also, are LL Queues that hard to implement once you can do them w/stacks

You have it backwards. You're not implementing a stack-based list. You're implementing a list-based stack.
List-based queues are pretty much the same as stacks, only you also keep a pointer to the tail, which turns tail insertions into O(1) operations, rather than O(n).