Stack: is a restricted version of linear/Linked lists. When the insertions and deletions on a linked list are restricted to be on the same end the resulting data structure is a Stack.
Definition:Stack is List in which the insertions(Push) and deletions (Pop) are performed at the same end which is called a TOP.
Stack is a LIFO structure.
Stack is a very popular Data structure, it place an important role in solving problems which are recursive in nature. In C++ we have the STL implementation of Stack data structure called "stack"
The below implementation of a stack is a custom implementation of stack. I am using this to write non-recursive solutions for Binary Tree based problems.Hopefully i will be adding a template based general implementation of stack very soon.
####################################################################################
File: stackint.h
Author:Thejas
####################################################################################
#ifndef STACKINT_H
#define STACKINT_H
#include <assert.h>
#include "include/BinaryTreeIntNode.h"
#include <iostream>
using namespace std;
class StacktNode{
public:
StacktNode* next;
BinaryTreeIntNode* node;
int colour;//Used for using Coloring ALGORITHMS for NON Recursive implementations
StacktNode(){next = NULL; node= NULL;}
StacktNode(BinaryTreeIntNode* n,StacktNode* nextNode);
~StacktNode(){}
};
class StackInt
{
public:
StackInt();
~StackInt();
StackInt(StacktNode* topStack, int stackSize);
void push(StacktNode* newNode);
StacktNode* pop();
bool isEmpty(){return (size == 0 || size < 0);}
void setSize(int stackSize)
{
assert(stackSize > 0);
size = stackSize;
return;
}
int getSize(){return size;}
void incrmentSize(){size++; return;}
protected:
private:
StacktNode* top;
int size;
};
#endif // STACKINT_H
###################################################################################
###################################################################################
File: stackint.h
Author:Thejas
###################################################################################
#include "stackint.h"
#include <iostream>
StacktNode::StacktNode(BinaryTreeIntNode* n,StacktNode* nextNode)
{
node= n;
next=nextNode;
colour=0;
return;
}
StackInt::StackInt()
{
size = 0;
top = NULL;
return;
}
StackInt::~StackInt()
{
StacktNode* temp = NULL;
while(top!=NULL)
{
temp=top->next;
delete top;
top = temp;
}
return;
}
StackInt::StackInt(StacktNode* topStack, int stackSize)
{
top = topStack;
size=stackSize;
return;
}
void StackInt::push(StacktNode* newNode)
{
newNode->next=top;
top = newNode;
size++;
return;
}
StacktNode* StackInt::pop()
{
StacktNode* retVal = NULL;
if(size !=0)
{
retVal = top;
top= top->next;
size--;
return retVal;
}
cout<<"Trying to POP an empty STACK"<<endl;
return retVal;
}
No comments:
Post a Comment