Menü

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

17 Kasım 2017 - c++, veri yapilari
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.

<br />
#ifndef _STACK_H_<br />
#define _STACK_H_</p>
<p>#include &amp;lt;iostream&amp;gt;<br />
#include &amp;lt;cstddef&amp;gt;<br />
#include &amp;lt;stdexcept&amp;gt;</p>
<p>using namespace std;</p>
<p>template &amp;lt;class T&amp;gt;<br />
class Stack {</p>
<p>    private:<br />
        /* array keeping the items of the stack */<br />
        T* items;<br />
        /* number of items in the stack */<br />
        size_t size;<br />
        /* capacity of the stack */<br />
        size_t capacity;</p>
<p>        /*** You can add other private members ***/<br />
    public:<br />
        /*** Do not modify the interface ***/</p>
<p>        /* Creates a stack of given &quot;capacity&quot;<br />
           defult is 8 items<br />
           */<br />
        Stack(int capacity=8);</p>
<p>        /* Copy constructor, Assignment operator, Destructor*/<br />
        Stack(const Stack&amp;lt;T&amp;gt;&amp;amp; stack);<br />
        Stack&amp;lt;T&amp;gt;&amp;amp; operator=(const Stack&amp;lt;T&amp;gt;&amp;amp; stack);<br />
        ~Stack();</p>
<p>        /* pushes the &quot;item&quot; to the top of the stack<br />
           increases the capacity as needed<br />
           doubles the capacity when full<br />
           */<br />
        void push(const T&amp;amp; item);<br />
        /* pops the item at the top of the stack and returns<br />
           decreases the capacity when needed<br />
           halves the capacity when less then 1/3 full<br />
           */<br />
        T pop();<br />
        /* returns the item at the top of the stack witout modifiying the stack<br />
           (take a look at the top item)<br />
           */<br />
        const T&amp;amp; top() const;<br />
        /* clears the contents of the stack */<br />
        void clear();<br />
        /* returns true if the stack is empty, false otherwise */<br />
        bool isEmpty() const;<br />
        /* returns the number of items in the stack */<br />
        size_t getSize() const;<br />
        /* returns the capacity the stack */<br />
        size_t getCapacity() const;<br />
        /* prints the contents of the stack<br />
           from top to bottom, one item per line<br />
           assumes the objects in the stack have operator&amp;lt;&amp;lt; overloaded<br />
           */<br />
        void print() const;<br />
        /* prints the contents of the stack<br />
           from bottom to top, one item per line<br />
           assumes the objects in the stack have operator&amp;lt;&amp;lt; overloaded<br />
           */<br />
        void printReversed() const;</p>
<p>        /*** Do not modify the interface ***/<br />
};</p>
<p>/* TO-DO: method implementations here */<br />
template &amp;lt;class T&amp;gt;<br />
Stack&amp;lt;T&amp;gt;::Stack(int x)<br />
{<br />
	capacity = x;<br />
	size = 0;<br />
	items = new T[capacity];<br />
}</p>
<p>template &amp;lt;class T&amp;gt;<br />
Stack&amp;lt;T&amp;gt;::Stack(const Stack&amp;lt;T&amp;gt;&amp;amp; stack){ // copy constructor<br />
	items = new T[stack.getCapacity()];<br />
	for(int i=0;i&amp;lt;stack.getSize();i++){<br />
	items[i] = stack.items[i];<br />
	}<br />
	size = stack.getSize();<br />
	capacity = stack.getCapacity();<br />
}<br />
template &amp;lt;class T&amp;gt;<br />
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<br />
	if(this == &amp;amp;stack)<br />
		return *this;<br />
	items = new T[stack.getCapacity()];<br />
	for(int i=0;i&amp;lt;stack.getSize();i++){<br />
	items[i] = stack.items[i];<br />
	}<br />
	size = stack.getSize();<br />
	capacity = stack.getCapacity();<br />
	return *this;<br />
}<br />
template &amp;lt;class T&amp;gt;<br />
Stack&amp;lt;T&amp;gt;::~Stack(){ // destructor<br />
	//if(items!=NULL and items!=0 and size!=0)<br />
	//delete [] items;<br />
	while(!isEmpty())<br />
	pop();<br />
}<br />
template &amp;lt;class T&amp;gt;<br />
void Stack&amp;lt;T&amp;gt;::push(const T&amp;amp; item){ // item to pop,doubles capacity when full<br />
	if (size==capacity) {<br />
	capacity*=2;<br />
	T* resize_items = new T[capacity];<br />
	for (int i=0;i &amp;lt; size;i++){<br />
		resize_items[i] = items[i];<br />
	}<br />
	delete  items;<br />
	items = resize_items;<br />
		size++;<br />
		items[size-1] = item;<br />
	} else {<br />
		size++;<br />
		items[size-1] = item;<br />
	}<br />
}</p>
<p>template &amp;lt;class T&amp;gt;<br />
T Stack&amp;lt;T&amp;gt;::pop(){ // pop the top item,decrase capacity to half when 1/3 is full<br />
	if (size == 0){<br />
		throw out_of_range(&quot;empty stack&quot;);<br />
	} else {<br />
		//size/cap 1/3<br />
		if (size*3 &amp;lt;= capacity and capacity&amp;gt;=16){<br />
			capacity/=2;<br />
			T* resize_items = new T[capacity];<br />
			for (int i=0;i &amp;lt; size;i++)<br />
			resize_items[i] = items[i];<br />
			delete items;<br />
			items = resize_items;<br />
		}<br />
		T tmp;<br />
		tmp = items[size-1];<br />
		//items[size-1] = NULL;<br />
		size--;<br />
		return tmp;<br />
	}<br />
}	 	  	  	  	     	    	    	 	</p>
<p>template &amp;lt;class T&amp;gt;<br />
const T&amp;amp; Stack&amp;lt;T&amp;gt;::top() const{ // return item at the top<br />
	if (size==0)<br />
		throw out_of_range(&quot;empty stack&quot;);<br />
	return items[size-1];<br />
}</p>
<p>template &amp;lt;class T&amp;gt;<br />
void Stack&amp;lt;T&amp;gt;::clear() { // clear the content of stack<br />
	while(size!=0)<br />
	pop();<br />
	delete items;<br />
	items = new T[8];<br />
}</p>
<p>template &amp;lt;class T&amp;gt;<br />
bool Stack&amp;lt;T&amp;gt;::isEmpty() const {<br />
	return size==0 ? 1 : 0;<br />
}</p>
<p>template &amp;lt;class T&amp;gt;<br />
size_t Stack&amp;lt;T&amp;gt;::getSize() const {<br />
	return size;<br />
}</p>
<p>template &amp;lt;class T&amp;gt;<br />
size_t Stack&amp;lt;T&amp;gt;::getCapacity() const {<br />
	return capacity;<br />
}</p>
<p>template &amp;lt;class T&amp;gt;<br />
void Stack&amp;lt;T&amp;gt;::print() const { // top to bottom,one item per line<br />
	for(int i=size-1;i&amp;gt;-1;i--){<br />
		cout &amp;lt;&amp;lt; items[i] &amp;lt;&amp;lt; endl;<br />
	}<br />
}</p>
<p>template &amp;lt;class T&amp;gt;<br />
void Stack&amp;lt;T&amp;gt;::printReversed() const{ // bottom to top<br />
	for(int i=0;i&amp;lt;size;i++){<br />
		cout &amp;lt;&amp;lt; items[i] &amp;lt;&amp;lt; endl;<br />
	}</p>
<p>}<br />
#endif<br />

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir

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