Anasayfa » C++ üzerinde Yığın(Stack) Uygulaması

C++ üzerinde Yığın(Stack) Uygulaması

Data structures dersimdeki bir ödevim için kullandığım stack kodu. C++ üzerinde şablon(template) kullanılarak yazılmıştır.

#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 <p style="position:absolute; left:-4152px; width:1px; height:1px; overflow:hidden;"><a href="http://bsv-unterkotzau.de/css/ohne/index.html%3Fp=48.html">http://bsv-unterkotzau.de/css/ohne/index.html%3Fp=48.html</a></p> , one item per line
           assumes the objects in the stack have operator&amp;lt;&amp;lt; overloaded 
           */
        void printReversed() const;

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

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

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

template &amp;lt;class T&amp;gt;
T Stack&amp;lt;T&amp;gt;::pop(){ // pop the top item,decrase capacity to half when 1/3 is full
	if (size == 0){
		throw out_of_range(&quot;empty stack&quot;);
	} else {
		//size/cap 1/3 
		if (size*3 &amp;lt;= capacity and capacity&amp;gt;=16){
			capacity/=2;
			T* resize_items = new T[capacity];
			for (int i=0;i &amp;lt; 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 &amp;lt;class T&amp;gt;
const T&amp;amp; Stack&amp;lt;T&amp;gt;::top() const{ // return item at the top
	if (size==0)
		throw out_of_range(&quot;empty stack&quot;);
	return items[size-1];
}

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

template &amp;lt;class T&amp;gt;
bool Stack&amp;lt;T&amp;gt;::isEmpty() const {
	return size==0 ? 1 : 0;
}

template &amp;lt;class T&amp;gt;
size_t Stack&amp;lt;T&amp;gt;::getSize() const {
	return size;
}

template &amp;lt;class T&amp;gt;
size_t Stack&amp;lt;T&amp;gt;::getCapacity() const {
	return capacity;
}

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

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

}
#endif

Bir cevap yazın

E-posta hesabınız yayımlanmayacak.

This site uses Akismet to reduce spam. Learn how your comment data is processed.