I'm implementing a stack by C++ and here I think it has memory leakage problem: in Stack::peek() and Stack::pop(), where I created heap space and returned pointer to function caller.
Users who call these two functions may perform deletion on returned pointer, which will recycle heap space once done. I am wondering what is a better approach to my current leakage prone approach.
Header file:
// this is the header file of stack data structure.
#ifndef MY_STACK_H
#define MY_STACK_H
class Node
{
private:
int number;
Node * next;
public:
Node(){number = 0; next = NULL;}
Node(int initialNumber, Node * initialNext = NULL)
{
number = initialNumber;
next = initialNext;
}
// copy constructor
Node(Node & copyFromNode)
{
this->number = copyFromNode.getNumber();
this->next = copyFromNode.getNext();
}
// setters & getters
int getNumber() {return number;}
Node * getNext() {return next;}
void setNumber(int newNumber) {number = newNumber;}
void setNext(Node * newNext) {next = newNext;}
};
class LinkedList
{
private:
Node * head;
public:
LinkedList(){head = NULL;}
// very similar to Stack::push()
void addFirst(Node *newNode)
{
newNode->setNext(head);
head = newNode;
}
// somehow similar to Stack::pop()
void deleteFirst()
{
if (head == NULL)
return;
else
{
Node * temp = head;
head = head->getNext();
delete temp;
}
}
bool isEmpty() {return (head == NULL);}
Node * getHead() {return head;}
// there is no setter to head
// since head should be maintained by addFirst() & deleteFirst() only.
};
class Stack
{
private:
Node * top;
LinkedList ll;
public:
Stack(){top = NULL; }
// push new node to the stack
// new node will become the new top of stack
void push(Node * newNode);
// it checks if the stack is empty or not.
bool isEmpty();
// it copies the top node on stack,
// without deleting it.
Node * peek();
// it copies the top node on stack,
// and deletes the node from stack.
Node * pop();
};
#endif
.cpp file:
// implementation for the stack
#include <iostream>
#include "stack.h"
using namespace std;
void Stack::push(Node * newNode)
{
ll.addFirst(newNode);
top = ll.getHead();
}
bool Stack::isEmpty()
{
if(top == NULL)
return true;
else
return false;
}
Node * Stack::peek()
{
// make a copy, erase next link and return
// copy is made by calling copy construtor
Node * copy = new Node(*top); // ?? asks for reference but pointer is given
return copy;
}
Node * Stack::pop()
{
if (isEmpty())
return NULL;
else
{
Node * copy = new Node(*top);
ll.deleteFirst();
top = ll.getHead();
return copy;
}
}
int main()
{
Stack stack;
Node * nd1 = new Node(100);
Node * nd2 = new Node(200);
// test push()
stack.push(nd1);
stack.push(nd2);
// test isEmpty()
cout<<"Test: isEmpty(): "<< stack.isEmpty()<<endl;
// test peek()
cout<<"Test: peek(): "<<stack.peek()->getNumber()<<endl;
// test pop()
cout<<"Test: pop()"<<stack.pop()->getNumber()<<endl;
cout<<"Test: pop()"<<stack.pop()->getNumber()<<endl;
cout<<"Test: isEmpty(): "<<stack.isEmpty()<<endl;
return 0;
}
