No replies to this topic

[TkTech]

This is a simple implementation of a C++ stack template.

[highlight=cpp]
#pragma once

#include <cstdlib> //malloc()/realloc()/free()
#include <exception> //Exception baseclass

/* Public domain stack example by Tyler Kennedy */

class ExNotEnoughMemory : public std::exception
{
virtual const char* what() const throw(){
return "A memory operation(malloc()/realloc()/free() failed.";
}
} NotEnoughMemory;

class ExInvalidIndex : public std::exception
{
virtual const char* what() const throw(){
return "An element indexing error occured(underflow/overflow)";
}
} InvalidIndex;

template <typename DataType>
class stack {
private:
int m_ChunkSize;//The number of elements to allocate per stride
DataType *m_Storage; //The data pointer itself
int m_Size; //The number of _used_ elements
int m_Elements; //The number of _available_ elements
public:
stack();
void push(DataType Data); //Add an element to the stack
DataType pop(void); //Remove an element from the stack
int size(void); //Get the size of the stack
DataType top(void); //Get the last element from the stack, without removing it
int empty(void); //Check to see if the stack is empty
};

template <typename DataType>
stack<DataType>::stack() : m_ChunkSize(5), m_Storage(NULL)
{
m_Storage = (DataType*)realloc(NULL,sizeof(DataType) * m_ChunkSize);
if(m_Storage == NULL){
throw NotEnoughMemory;
}
m_Size = 0;
m_Elements = m_ChunkSize;
}

template <typename DataType>
void stack<DataType>::push(DataType Data){
if(m_Size >= m_Elements){
//We need to expand the array
DataType *temp;
temp = (DataType*)realloc(m_Storage,sizeof(DataType) * (m_Elements + m_ChunkSize));
if(temp == NULL){
throw NotEnoughMemory;
}
m_Elements += m_ChunkSize;
m_Storage = temp;
}

m_Storage[m_Size++] = Data;
}

template <typename DataType>
int stack<DataType>::size(void){
return m_Size;
}

template <typename DataType>
DataType stack<DataType>::pop(void){
DataType temp;
DataType *temp2;

if(size() <= 0){
throw InvalidIndex;
}

temp = m_Storage[--m_Size];
if(m_Size < m_Elements - m_ChunkSize){
/* Shrink the array if we don't need this much space */
temp2 = (DataType*)realloc(m_Storage,sizeof(DataType) * (m_Elements - m_ChunkSize));
if(temp2 == NULL){
throw NotEnoughMemory;
}
m_Elements -= m_ChunkSize;
m_Storage = temp2;
}
return temp;
}

template <typename DataType>
DataType stack<DataType>::top(void){
if(size() <= 0){
throw InvalidIndex;
}

return m_Storage[m_Size - 1];
}

template <typename DataType>
int stack<DataType>::empty(void){
if(size() == 0)
return true;
return false;
}
[/highlight]

...and a little tester...
[highlight=cpp]
#include "stack.h"
#include <exception>
#include <iostream>

int main(void){
stack<int> test;

for(int i = 0; i < 16; i++){
test.push(i);
}

for(int i = test.size(); i > 0 ; i--){
std::cout << test.pop() << std::endl;
}

try{
std::cout << test.top() << std::endl;
}catch(std::exception& e){
std::cout << e.what() << std::endl;
}

std::cin.get();
return 0;
}
[/highlight]