Stacks – Random Thoughtz

<<This is stupid to write my own implementation of stack when .Net framework provides inbuilt structures to do the same. But just checking if things can be done the C++ way.>>

The steps will be like this:

1. Create a class, structNode, that will represent the linked list node that will be the stack item. The node should have containers for data as well as pointers to the next item in the stack.

2. Create a second class that will define the PUSH and the POP methods. The PUSH method will create the new node and add the node to the front of the linked list. Note that in a stack the last item added is the first item removed. Also make sure that the PUSH method updates the NEXT field of the class structNode as follows:

i. if the node is the first item in the stack then NEXT==NULL

ii. if the node is added to a stack that already contains items then make sure that the NEXT field is updated to point to the CURRENT top node; that is the node that was the top node before we added this node.

3. The second class should also contain the Pop() method to return/display the stack item that is currently at the top. You should ensure that a check for an empty stack is done before you try to pop a value. In this operation also the NEXT item needs to be updated as below:

i. set tempObjNode = currentTopNode;

ii. set currentTopNode = currentTopNode.NEXT;

iii.return tempObj;

A sample code will look like:

using System;
using System.IO;

public class structNode
{
protected int data;

protected structNode nextNode;

    public structNode NextNode
    {
        set{nextNode = value;}
        get{return nextNode;}
    }

    public int NodeData
    {
        set{data=value;}
        get{return data;}
    }

    public structNode(structNode nextStackNode, int stackData)
    {
        NodeData=stackData;
        NextNode = nextStackNode;
    }
}

public class NStack
{
public structNode Push(structNode objNode, int data)
{

        Console.WriteLine(“Create a new Node for the stack.\n”);
        structNode _elementN = new structNode(null, 0);
        _elementN.NodeData = data;
        Console.WriteLine(“The node is now ready. Check if this is the first node in the stack Linked list.\n”);
        if(objNode == null)
        {
            Console.WriteLine(“Yes. This is the first node of the stack Linked list.\n”);
            _elementN.NextNode = null;
            return _elementN;
        }
        else
        {
            Console.WriteLine(“Inserting the new node.\n”);
            _elementN.NextNode = objNode;
            Console.WriteLine(“Node inserted successfully!!!!!”);
            return _elementN;
        }

}

    public structNode Pop(structNode objNode)
    {
        Console.WriteLine(“In Pop Method. Check if the stack is empty…”);
        if(objNode == null)
        {
            throw new InvalidOperationException(“The stack is empty!”);
        }
        if(objNode.NextNode == null)
        {
            Console.WriteLine(“This is the last node of the stack\n”);
            Console.WriteLine(“:{0}”, objNode.NodeData);
            objNode = null;
        }
        else
        {
            Console.WriteLine(“:{0}”, objNode.NodeData);
            objNode = objNode.NextNode;
        }
        return objNode;
    }

}

class mainController
{
    static void Main()
    {
        NStack objNStack = new NStack();
        structNode objstructNode = null;
        int intChoice = 0;
        do
        {
            Console.WriteLine(“Enter the Choice.\n”);
            intChoice = Convert.ToInt32(Console.ReadLine());
            switch(intChoice)
            {
            case 1:
                Console.WriteLine(“Enter Stack Data:\t”);
                int intCounter = Convert.ToInt32(Console.ReadLine());
                objstructNode = objNStack.Push(objstructNode, intCounter); break;

            case 2: if(objstructNode != null)
                {
                    objstructNode = objNStack.Pop(objstructNode);
                }
                break;
            case 3: break;
            }
        }while(intChoice!=3);
    }
}

The operations to be supported:

1. PUSH

2. POP

3. Check if Empty

4. Check if Full

//I have just created the skeleton. Exception handling is not put in yet.

#include
using namespace std;

class stack
{
    public:
        stack();
        ~stack();
        void Push(int inData);
        int Pop();
        void display();
        bool IsEmpty();
    protected:
        typedef struct nodeT
        {
            int data;
            struct nodeT *next;
        }node;
        node *firstElement;
};

//Class method implementation now
stack::stack()
{
firstElement = NULL;
return;
}

stack::~stack()
{
    node *next;
    while(firstElement)
    {
        next=firstElement->next;
        delete firstElement;
        firstElement=firstElement->next;
    }
    return;
}

void stack::Push(int inData)
{
    node *newNode = new node;
    newNode->data=inData;
    newNode->next=firstElement;
    firstElement = newNode;
    return;
}

//Note that the Pop operation is intended to return the data stored in the top most node and free

//that space in the stack
int stack::Pop()
{
    node *nodeToPop;
    int data;
    nodeToPop=firstElement;
    firstElement=firstElement->next;
    data=nodeToPop->data;
    delete nodeToPop;
    return data;
}

bool stack::IsEmpty()
{
if(!firstElement) return 1;
else return 0;
}

void stack::display()
{
    node *ptr;
    ptr=firstElement;
    if(ptr)
    {
        cout<<"The stack elements are: "<<endl;
        while(ptr)
        {
            cout<data<<endl;
            ptr=ptr->next;
        }
    }
    else
    {
        cout<<"There are no elements in the stack!!!!"<<endl;
    }
}

void main()
{
    stack objStack;
    int indata=0, choice=1;
    while(choice!=0)
    {
        cout<<"Stack Operations Main Menu: 1.Push 2.Pop    3.IsEmpty 4.IsFull 0.Exit"

<<endl;
        cin>>choice;
        switch(choice)
        {
            case 0:
                exit(1); //Normal program Termination
            case 1:
                cout<<"Enter the number to Push: ";
                cin>>indata;
                objStack.Push(indata);
                break;
            case 2:
                if(!objStack.IsEmpty())
                {
                cout<<"The number popped from the stack is: "<<objStack.Pop()

            <<endl;
                }
                else {cout<<"Cannot pop from an empty stack!!!"<<endl;}
                break;
            case 3:
                cout<<"Checking if the stack is empty…";
                if(objStack.IsEmpty())
                {
                    cout<<"The stack is empty."<<endl;
                }
                else
                {
                    cout<<"The stack is not empty"<<endl;;
                }
                break;
            case 4:
                //TO Do
            default:
                cout<<"Illegal Action. Please try again!!!"<<endl;
        }
        objStack.display();
        cin.get();
    }
}

Category: Stacks

Implement a Stack in C#

Creating a Stack using Linked List.