Implement a Stack in C#

<<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);
    }
}

Advertisements

Remove Duplicates from an Unsorted single linked list

void SLList::removeDuplicates()
{
    if(header)
    {
        Node *temp, *curChkNode, *last;
        temp=curChkNode=header;
        int curVal=0, length=0, counter=0;
        length=sllLength();
        cout<<"\nThe length of the list is:\t"<<length;
        while(counter!=length && curChkNode)
        {
            temp=curChkNode->next;
            curVal=curChkNode->data;
            while(temp)
            {
                if(curVal==temp->data)
                {
                    cout<<"\nA DUPLICATE IS PRESENT FOR:\t"<<curVal;
                    last->next=temp->next;
                }
                last=temp;
                temp=temp->next;
            }
            curChkNode=curChkNode->next;
            counter++;
        }   
    }
    else
    {
        cout<<"\nThe list is empty\n";
    }
    return;
}

C++ Compilation Error: error C2470: ‘SLList’ : looks like a function definition, but there is no parameter list; skipping apparent body

The compiler showed the error:

error C2470: ‘SLList’ : looks like a function definition, but there is no parameter list; skipping apparent body

I had coded this snippet using a notepad and hence after lots of head banging figured out that the issue was a stupid missed (:):

 

class SLList
{
    private:
        Node *header;
    public:
        SLList()
        {
            header=NULL;
        }
        void createList();
        void displayList();
        int sllLength();
        void removeDuplicates();
};

:::::::::::::

:::::::::::::::

int SLList:sllLength()
{
    int counter=0;
    if(header)
    {
        Node *temp;
        temp=header;
        while(temp)
        {
            counter++;
        }
        delete temp;
    }
    return counter;
}

 

should have been:

int SLList::sllLength()
{
    int counter=0;
    if(header)
    {
        Node *temp;
        temp=header;
        while(temp)
        {
            counter++;
        }
        delete temp;
    }
    return counter;
}

Design a doubly linked list and perform the following operations: 1)Add nodes to both front and rear 2)Display the list, 3)Delete nodes at front.tail and nth position

#include

using namespace std;

class Node
{
    public:
    int data;
    Node *prev, *next;
    Node()
    {
        data=NULL;
        prev=NULL;
        next=NULL;
    }   
};

class dll
{
    private:
        Node *header;
    public:
        dll(){
            header=NULL;
        }
        void createList();
        void displayList();
        void insertEnd();
        void deleteFirstNode();
        void deleteLastNode();
        void deleteNthNode();
};

void dll::deleteFirstNode()
{
    if(header)
    {
        Node *temp;
        temp=header;
        header=temp->next;
        header->prev=NULL;
        delete temp;
    }
    else
    {cout<<"\nThe list is empty!\n";}
    return;
}

void dll::deleteLastNode()
{
    if(header)
    {
        Node *temp, *last;
        temp=header;
        while(temp)
        {
            last=temp;
            temp=temp->next;
        }
        last->prev->next=NULL;
        delete last;
        delete temp;       
    }
    else
    {cout<<"\nThe list is empty!\n";}
    return;
}

void dll::deleteNthNode()
{
    if(header)
    {
        Node *temp, *last;
        temp=header;
        int position=0, counter=0;
        cout<<"Enter the node position that you want to delete: \t";
        cin>>position;
        if(position>=0)
        {
            while(counter!=position && temp)
            {
                last=temp;           
                temp=temp->next;
                counter++;
            }
            if(temp)
            {
            cout<<"\nThe node that you want to delete has value:\t\n"<data;
            last->prev->next=temp;
            temp->prev=last->prev;
            delete last;           
            }
            else{cout<<"\nThe list does not contain that many elements\n";}
        }
    }
    return;
}

void dll::insertEnd()
{
    if(header==NULL)
    {
        createList();
    }
    else
    {
        Node *newNode, *temp, *last;
        newNode=new Node;
        cout<<"Enter the value for the node:\t";
        cin>>newNode->data;
        temp=header;
        while(temp)
        {
            last=temp;
            temp=temp->next;
        }
        newNode->next=NULL; //newNode is the new last node
        newNode->prev=last;
        newNode->prev->next=newNode;           
    }
    return;
}

void dll::createList()
{
    int in_val;
    Node *temp;
    temp=new Node;
    cout<<"Enter the value for the node:\t";
    cin>>temp->data;
    if(header == NULL)
    {
        //This is the first node in the double linked list
        temp->next=NULL;
        temp->prev=NULL;       
    }
    else
    {
        //If this is a new node at the front of an already populated linkedlist
        temp->next=header;
        temp->next->prev=temp;
        header=temp;
    }
    header=temp;
    return;
}

void dll::displayList()
{
    Node *temp, *last;
    temp=header;
    cout<<"Display the list from first to last using the NEXT pointer.\n";
    while(temp)
    {   
        cout<data<<"\t"<<endl;
        last=temp;
        temp=temp->next;
    }
    /*if(last)
    {
        cout<<"Display the list from last to last using the PREV pointer.\n";
        while(last)
        {
            cout<data<<"\t"<<endl;
            last=last->prev;       
        }
    }*/
}

void main()
{
    cout<<"******This is a Doubly Linked List Demo******"<<endl;
    int choice=0;
    dll objDLL;
    do{
        cout<<"Enter the opration you want to perform: ";
        cout<<"\n1). Add a node at front of the list";
        cout<<"\n2). Display a node";
        cout<<"\n3). Add a node at end of the list";
        cout<<"\n4). Delete the node at head of the list";
        cout<<"\n5). Delete the node at tail of the list";
        cout<<"\n6). Delete the node at nth position of the list";
        cout<<"\n7). Exit\t";
    cin>>choice;
    switch(choice)
    {
        case 1: objDLL.createList(); break;
        case 2: objDLL.displayList(); break;
        case 3: objDLL.insertEnd(); break;
        case 4: objDLL.deleteFirstNode();break;
        case 5: objDLL.deleteLastNode();break;
        case 6: objDLL.deleteNthNode();break;
        case 7: exit(0);
        default: cout<<"\n Invalid operation/input detected. Please try again later.";
    }   
    }while(choice!=7);
}   

Creating a Stack using Linked List.

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();
    }   
}

Create/Delete/Insert – Single Linked List

#include

using namespace std;

struct node{int data; struct node *next;};

struct node* createlist()
{
    node *temp, *firstNodePtr, *last;
    int intNumOfNodes=0;
    firstNodePtr = (node*)malloc(sizeof(node));
    temp=firstNodePtr;
    cout<<"Enter the number of nodes you want in the list: ";
    cin>>intNumOfNodes;
    if(intNumOfNodes!=0)
    {
        while(intNumOfNodes!=0)
        {
            temp->next = (node*)malloc(sizeof(node));
            cin>>temp->data;
            last=temp;
            temp=temp->next;
            intNumOfNodes–;
        }
        last->next=NULL;
        delete(temp);       
    }
    else
    {
        firstNodePtr = NULL;
    }
    return(firstNodePtr);
}

void display(struct node *header)
{
    node *ptr = header;
    cout<<endl<<"The list is: " ;
    while(ptr !=NULL)
    {
        cout<data<<" ";
        ptr=ptr->next;
    }
}

void deleteHeader(struct node **ptrHeader)
{
    node *current,*temp;
    current=*ptrHeader;
    temp=current->next;
    *ptrHeader = temp;
    current=NULL;
    display(*ptrHeader);           
}

void deleteTail(struct node **ptrHeader)
{
    node *last, *temp;
    temp=*ptrHeader;
    while(temp->next)
    {
        last=temp;
        temp=temp->next;
    }
    last->next=NULL;
    temp=NULL;
    display(*ptrHeader);   
}

void deleteANode(struct node **header, char choice)
{
    if(choice == ‘h’)
    {
        cout<<"You have chosen to delete the header node!!!"<<endl;
        deleteHeader(header);
    }
    else if(choice == ‘l’)
    {
        cout<<"You have chosen to delete the last node!!!"<<endl;
        deleteTail(header);
    }
    else
    {
        node *temp, *last;
        int counter=0, intPos=0;
        temp=*header;
        cout<<"Enter the position of the node that you want to delete."<<endl;
        cin>>intPos;
        while(counter!=intPos)
        {
            last=temp;
            temp=temp->next;
            counter++;
        }   
        last->next = temp->next;
        delete(temp);
        display(*header);       
    }
}

void main()
{
    node *headerPtr;
    node **ptrHeaderPtr;
    char choice;
    headerPtr = createlist();
    if(headerPtr)
    {
        ptrHeaderPtr = &headerPtr;
        display(headerPtr);
        cout<<"Which node do you want to delete? (h/p/l): ";
        cin>>choice;
        deleteANode(ptrHeaderPtr, choice);
        //display(headerPtr);
    }
    else {cout<<"You enterd a 0 value for list size. Exiting…";}
}