Fork me on GitHub
Menu

Stack Implementation in C++

21 January 2017 - c++, code snippets, data structures
Stack Implementation in C++

Here’s a stack implementation, written in C++ with templates. I used this code in my homework for c++ class. (ceng213 – data structures)

#ifndef _STACK_H_
#define _STACK_H_

#include <iostream>
#include <cstddef>
#include <stdexcept>

using namespace std;

template <class T> 
class Stack {

    private:
        /* array keeping the items of the stack */
        T* items;
        /* number of items in the stack */
        size_t size;
        /* capacity of the stack */
        size_t capacity;

        /*** You can add other private members ***/
    public:
        /*** Do not modify the interface ***/

        /* Creates a stack of given "capacity" 
           defult is 8 items
           */
        Stack(int capacity=8);

        /* Copy constructor, Assignment operator, Destructor*/
        Stack(const Stack<T>& stack);
        Stack<T>& operator=(const Stack<T>& stack);
        ~Stack();

        /* pushes the "item" to the top of the stack 
           increases the capacity as needed
           doubles the capacity when full
           */
        void push(const T& item);
        /* pops the item at the top of the stack and returns 
           decreases the capacity when needed
           halves the capacity when less then 1/3 full
           */
        T pop();
        /* returns the item at the top of the stack witout modifiying the stack 
           (take a look at the top item) 
           */
        const T& top() const;
        /* clears the contents of the stack */
        void clear();
        /* returns true if the stack is empty, false otherwise */
        bool isEmpty() const;
        /* returns the number of items in the stack */
        size_t getSize() const;
        /* returns the capacity the stack */
        size_t getCapacity() const;
        /* prints the contents of the stack 
           from top to bottom, one item per line
           assumes the objects in the stack have operator<< overloaded 
           */
        void print() const;	
        /* prints the contents of the stack 
           from bottom to top, one item per line
           assumes the objects in the stack have operator<< overloaded 
           */
        void printReversed() const;

        /*** Do not modify the interface ***/
};

/* TO-DO: method implementations here */
template <class T>
Stack<T>::Stack(int x)
{	 	  	  	  	     	    	    	 	
	capacity = x;
	size = 0;
	items = new T[capacity];
}

template <class T>
Stack<T>::Stack(const Stack<T>& stack){ // copy constructor
	items = new T[stack.getCapacity()];
	for(int i=0;i<stack.getSize();i++){
	items[i] = stack.items[i];
	}
	size = stack.getSize();
	capacity = stack.getCapacity();
}
template <class T>
Stack<T>& Stack<T>::operator=(const Stack<T>& stack){ // assignment operator
	if(this == &stack)
		return *this;
	items = new T[stack.getCapacity()];
	for(int i=0;i<stack.getSize();i++){
	items[i] = stack.items[i];
	}
	size = stack.getSize();
	capacity = stack.getCapacity();
	return *this;
}
template <class T>
Stack<T>::~Stack(){ // destructor
	//if(items!=NULL and items!=0 and size!=0)
	//delete [] items;
	while(!isEmpty())
	pop();
}
template <class T>
void Stack<T>::push(const T& item){ // item to pop,doubles capacity when full
	if (size==capacity) {	 	  	  	  	     	    	    	 	
	capacity*=2;
	T* resize_items = new T[capacity];
	for (int i=0;i < size;i++){
		resize_items[i] = items[i];
	}
	delete  items;
	items = resize_items;
		size++;
		items[size-1] = item;
	} else {
		size++;
		items[size-1] = item;
	}
}

template <class T>
T Stack<T>::pop(){ // pop the top item,decrase capacity to half when 1/3 is full
	if (size == 0){
		throw out_of_range("empty stack");
	} else {
		//size/cap 1/3 
		if (size*3 <= capacity and capacity>=16){
			capacity/=2;
			T* resize_items = new T[capacity];
			for (int i=0;i < size;i++)
			resize_items[i] = items[i];
			delete items;
			items = resize_items;
		}
		T tmp;
		tmp = items[size-1];
		//items[size-1] = NULL;
		size--;
		return tmp;
	}	
}	 	  	  	  	     	    	    	 	

template <class T>
const T& Stack<T>::top() const{ // return item at the top
	if (size==0)
		throw out_of_range("empty stack");
	return items[size-1];
}

template <class T>
void Stack<T>::clear() { // clear the content of stack
	while(size!=0)
	pop();
	delete items;
	items = new T[8];
}

template <class T>
bool Stack<T>::isEmpty() const {
	return size==0 ? 1 : 0;
}

template <class T>
size_t Stack<T>::getSize() const {
	return size;
}

template <class T>
size_t Stack<T>::getCapacity() const {
	return capacity;
}

template <class T>
void Stack<T>::print() const { // top to bottom,one item per line
	for(int i=size-1;i>-1;i--){
		cout << items[i] << endl;
	}	 	  	  	  	     	    	    	 	
}

template <class T>
void Stack<T>::printReversed() const{ // bottom to top
	for(int i=0;i<size;i++){
		cout << items[i] << endl;
	}

}
#endif

Leave a Reply

Your email address will not be published. Required fields are marked *