Stack Implementation using Linked List in C++

Question

You have to write code to implement Stack data structure using Linked List. 

The Stack operations IsEmpty, Push, and Pop must need to be implemented. Your program will allow user to add item in the stack and remove item from the stack. Your Pop function will show the item that is removed. 

In addition, your program should have a function (i.e. PrintStack) to print all the items in the Stack.

You have to submit the code along with the output of the code in reasonable detail in a single pdf file. Your code must contain comments as required.

Answer 1

#include <string.h>

#include <stdlib.h>

//#include <stdio.h>

#ifndef _STACK

#include "stack.h"

#endif

Stack::Stack()

{

first=last=NULL;

count=0;

}

Stack::~Stack()

{

TListNode cur = first;

for (int iLoop=0; iLoop<count; iLoop++)

{

first=first->next;

if (cur!=NULL)

{

free(cur);

}

cur=first;

}

first=last=NULL;

count=0;

}

Stack::Stack(Stack&stack)

{

first=last=NULL;

count=0;

struct _TDataStr dataStr;

int N = stack.GetCount();

for (int iLoop=N-1; iLoop>=0; iLoop--)

{

stack.IndexerGetAtIndex(iLoop,&dataStr);

this->Push(&dataStr);

}

}

Stack::Stack(Stack*stack)

{

first=last=NULL;

count=0;

struct _TDataStr dataStr;

int N = stack->GetCount();

for (int iLoop=N; iLoop>=0; iLoop--)

{

stack->IndexerGetAtIndex(iLoop,&dataStr);

this->Push(&dataStr);

}

}

int Stack::Push(TDataStr dataStr)

{

TListNode newListNode = (TListNode)malloc(LISTNODE_SIZE);

memcpy(&newListNode->dataStr,dataStr,DATASTR_SIZE);

//printf("Pushing data size = %d \n",dataStr->size);

if (count==0)

{

newListNode->next = NULL;

first = last = newListNode;

}

else

{

newListNode->next=first;

first=newListNode;

}

count++;

}

int Stack::Pop(TDataStr dataStr)

{

int iReturn=0;

if (count>0)

{

memcpy(dataStr,&first->dataStr,DATASTR_SIZE);

if (count==1)

{

free(first);

first=last=NULL;

count=0;

}

else

{

TListNode head = first;

first = first->next;

memcpy(dataStr,&head->dataStr,DATASTR_SIZE);

free(head);

count--;

}

}

else //pops empty stack..no can do

{

iReturn=-1;

}

return(iReturn);

}

int Stack::IndexerGetAtIndex(int iIndexPos, TDataStr dataStr)

{

int iReturn=0;

if (iIndexPos>=0 && iIndexPos<count)

{

TListNode cur = first;

for (int iLoop=0; iLoop<iIndexPos; iLoop++)

{

cur=cur->next;

}

memcpy(dataStr,&cur->dataStr,DATASTR_SIZE);

}

else

{

iReturn=-1;

}

return(iReturn);

}

#include <string.h>

#include <stdlib.h>

//#include <stdio.h>

#ifndef _QUEUE

#include "queue.h"

#endif

Queue::Queue()

{

first=last=NULL;

count=0;

}

Queue::~Queue()

{

TListNode cur = first;

for (int iLoop=0; iLoop<count; iLoop++)

{

first=first->next;

if (cur!=NULL)

{

free(cur);

}

cur=first;

}

first=last=NULL;

count=0;

}

Queue::Queue(Queue& queue)

{

first=last=NULL;

count=0;

struct _TDataStr dataStr;

int N = queue.GetCount();

for (int iLoop=0; iLoop<N; iLoop++)

{

queue.IndexerGetAtIndex(iLoop,&dataStr);

this->Push(&dataStr);

}

}

Queue::Queue(Queue*queue)

{

first=last=NULL;

count=0;

struct _TDataStr dataStr;

int N = queue->GetCount();

for (int iLoop=N; iLoop>=0; iLoop--)

{

queue->IndexerGetAtIndex(iLoop,&dataStr);

this->Push(&dataStr);

}

}

int Queue::Push(TDataStr dataStr)

{

TListNode newListNode = (TListNode)malloc(LISTNODE_SIZE);

memcpy(&newListNode->dataStr,dataStr,DATASTR_SIZE);

//printf("Pushing data size = %d \n",dataStr->size);

if (count==0)

{

newListNode->next = NULL;

first = last = newListNode;

}

else

{

newListNode->next=first;

first=newListNode;

}

count++;

}

int Queue::Pop(TDataStr dataStr)

{

int iReturn=0;

if (count>0)

{

memcpy(dataStr,&first->dataStr,DATASTR_SIZE);

if (count==1)

{

free(first);

first=last=NULL;

count=0;

}

else

{

TListNode head = first;

first = first->next;

memcpy(dataStr,&head->dataStr,DATASTR_SIZE);

free(head);

count--;

}

}

else //pops empty stack..no can do

{

iReturn=-1;

}

return(iReturn);

}

int Queue::IndexerGetAtIndex(int iIndexPos, TDataStr dataStr)

{

int iReturn=0;

if (iIndexPos>=0 && iIndexPos<count)

{

TListNode cur = first;

for (int iLoop=0; iLoop<iIndexPos; iLoop++)

{

cur=cur->next;

}

memcpy(dataStr,&cur->dataStr,DATASTR_SIZE);

}

else

{

iReturn=-1;

}

return(iReturn);

}

using namespace std;

#include <iostream>

#include <string.h>

#include <stdlib.h>

#ifndef _STACK

#include "stack.h"

#endif

#ifndef _QUEUE

#include "queue.h"

#endif

void Dump(Stack stack, Queue queue)

{

cout << "Stack Dump" << endl;

int N = stack.GetCount();

struct _TDataStr curDataStr;

for (int iLoop=0; iLoop<N; iLoop++)

{

stack.IndexerGetAtIndex(iLoop,&curDataStr);

switch (iLoop)

{

case 0 : { cout << curDataStr.data<<endl; break; }

case 1 : { cout << *((double*)curDataStr.data)<<endl; break; }

case 2 : { cout << *((long*)curDataStr.data)<<endl; break; }

}

}

cout << "------------------------------------------------------------" << endl;

cout << "Queue Dump" << endl;

N = queue.GetCount();

for (int iLoop=0; iLoop<N; iLoop++)

{

queue.IndexerGetAtIndex(iLoop,&curDataStr);

switch (iLoop)

{

case 2 : { cout << curDataStr.data<<endl; break; }

case 1 : { cout << *((double*)curDataStr.data)<<endl; break; }

case 0 : { cout << *((long*)curDataStr.data)<<endl; break; }

}

}

}

int main(int argc, char** argv)

{

cout << "Pushing ..." <<endl;

long longIntNum;

double flAmount;

struct _TDataStr dataStr;

Stack stack;

Queue queue;

longIntNum=52769;

dataStr.data = (char*)&longIntNum;

dataStr.size = sizeof(long);

stack.Push(&dataStr);

queue.Push(&dataStr);

flAmount=35.42;

dataStr.data = (char*)&flAmount;

dataStr.size = sizeof(double);

stack.Push(&dataStr);

queue.Push(&dataStr);

char str[] = "Hello";

dataStr.data = str;

dataStr.size = 6;

stack.Push(&dataStr);

queue.Push(&dataStr);

Dump(stack,queue);

cout << endl << "Popping..."<<endl;

int N = queue.GetCount();

struct _TDataStr popDataStr;

for (int iLoop=0; iLoop<N; iLoop++)

{

stack.Pop(&popDataStr);

switch (iLoop)

{

case 0 : { cout << popDataStr.data<<endl; break; }

case 1 : { cout << *((double*)popDataStr.data)<<endl; break; }

case 2 : { cout << *((long*)popDataStr.data)<<endl; break; }

}

}

if (stack.Pop(&popDataStr)!= 0)

{

cout << "Empty Stack " << endl;

}

for (int iLoop=0; iLoop<N; iLoop++)

{

queue.Pop(&popDataStr);

switch (iLoop)

{

case 0 : { cout << popDataStr.data<<endl; break; }

case 1 : { cout << *((double*)popDataStr.data)<<endl; break; }

case 2 : { cout << *((long*)popDataStr.data)<<endl; break; }

}

}

if (stack.Pop(&popDataStr)!= 0)

{

cout << "Empty Queue" << endl;

}

return 0;

}