Zásobník a pole – C / C++ – Fórum – Programujte.com

Pekný deň mohol by sem hodiť niekto kód pre úplne jednoduchý zásobnik do ktorého by sa plnil a pod.pomocou klasických funkcií pop() push(), pretože mám jeden veľký problém neviem si zásobník predstaviť neviem či je to pole alebo čo to vlastne je....   

template <typename type, int n>
class Stack  //sablona tridy Stack, n urcuje pocet prvku
{
  private:
    type stackArray[n];  //pole stacku
    type* stackPointer;  //ukazatel na vrchol stacku, resp. na prvek do ktereho bude ulozena dalsi hodnota
  
  public:
    Stack(){stackPointer = stackArray;}  //konstruktor nastavujici stackPointer na zacatek stacku
    bool IsEmpty(){return stackPointer == stackArray;}  //vraci true pokud je stack prazdny
    bool IsFull(){return stackPointer == stackArray + n;}  //vraci true pokud je stack plny
    void Push(type) throw(const char*);  //prida prvek na vrchol stacku
    type Pop() throw(const char*);  //odebere prvek z vrcholu stacku a vrati jeho hodnotu
};

template <typename type, int n>
void Stack<type,n>::Push(type val) throw(const char*)  //prida prvek na vrchol stacku
{
  if(IsFull())
    throw "The stack is full.";  //pokud je stack plny vyhodi vyjimku typu const char*
  *stackPointer = val;  //zkopíruje val na místo kam ukazuje stackPointer
  stackPointer++;  //posune stackPointer o jeden prvek smerem k vrcholu
}

template <typename type, int n>
type Stack<type,n>::Pop() throw(const char*)  //odebere prvek z vrcholu stacku a vrati jeho hodnotu
{
  if(IsEmpty())
    throw "The stack is empty.";  //pokud je stack prazdny vyhodi vyjimku typu const char*
  stackPointer--;  //posune stackPointer o jeden prvek smerem k zacatku
  return *stackPointer;  //vrati vrati prvek ktery byl odebran
}

Stačí nějak takhle?

Zasobnik(stack) moze byt implementovany roznymi sposobmi. Stack nie je ani tak datova struktura ako skor sposob ako sa do takej struktury ukladaju data. Implementovany moze byt pomocou ronych linearnych datovych struktur ako pole, dynamicke pole(vector), rada, zretazeny zoznam(list)...

Viac mas toho tu: http://cs.wikipedia.org/wiki/Z%C3%A1sobn%C3%ADk_(datov%C3%A1_struktura)

Riesenie od Luckin-a je viac menej funkcne ale je nevhodne na ukladanie zlozitejsich typov .

#3 vitamin
Jistě, napsal jsem to tak nějak jednoduše, chtěl to tak, aby si to mohl představit. Hlavní nevýhoda tohoto stacku je t vom, že má omezenou a neměnnou velikost. Osobně nejčastěji používám linked list.

#4 Luckin
Hlavna nevyhoda tvojho stacku je to, ze aj ked v nom nic nie je tak sa vola 'n' krat konstruktor/destructor. Dalsia nevyhoda je ze ak chces do toho stacku vlozit objkt tak musi mat pretazeny operator=. Dalsia nevyhoda je ze v Pop a Push sa vytvaraju zbitocne kopie objektov...

#5 vitamin
To, že se n-krát volá konstruktor, souvisí s tou neměnnou velikostí. Operátor = má každá třída přetížená defaultně a to tak že provádí mělkou kopii, pokud toto nevyhovuje a nechceš či nemůžeš operátor přetížit, pak bys musel do stacku ukládat pouze adresy objektů nebo reference na ně. Co se týče zbytečných kopií v Push a Pop, tak to máš pravdu, mélo by tam být:

void Push(const type &) throw(const char*);
const type & Pop() throw(const char*);

#6 Luckin
Da sa to riesit aj ovla efektivnejsie:

#include <iostream>
#include <type_traits>
#include <stdexcept>


template <class T, size_t N>
class stack{
	private:
		char data[sizeof(T)*N];
		size_t pos;
		
		inline T* t_data(size_t i){return reinterpret_cast<T*>(data) + i;}
		inline const T* t_data(size_t i)const{return reinterpret_cast<const T*>(data) + i;}
		
	public:
		inline size_t size()const{return pos;}
		inline constexpr size_t max_size()const{return N;}
		inline bool empty()const{return (pos == 0);}
		inline bool full()const{return (pos == N);}
		
		stack():pos(0){}
		
		~stack(){
			if(!std::is_trivial<T>::value)	//ak nemas c++11 tak tuto podmienku odstran
				for(size_t i = pos; i > 0; --i)
					t_data(i-1)->~T();
		}
		
		void clear(){
			this->~stack();
			pos = 0;
		}
			
		template <class U>
		void push(const U& u){
			if(full())throw std::out_of_range("stack is full");
			new(t_data(pos)) T(u);
			++pos;
		}
		
		void push(T&& t){	//ak nmas c++11 tak tuto metodu odstran
			if(full())throw std::out_of_range("stack is full");
			new(t_data(pos)) T(std::move(t));
			++pos;
		}
		
		template <class... Args>
		void emplace(Args... args){	//ak nmas c++11 tak tuto metodu odstran
			if(full())throw std::out_of_range("stack is full");
			new(t_data(pos)) T(args...);
			++pos;
		}
		
		void pop(){
			if(empty())throw std::out_of_range("stack is empty");
			--pos;
			t_data(pos)->~T();
		}
		
		const T& top()const{
                       if(empty())throw std::out_of_range("stack is empty");			
                       return *t_data(pos-1);
		}

                T& top(){
                        if(empty())throw std::out_of_range("stack is empty");
                        return *t_data(pos-1);                }	
};

#7 vitamin
Použít operátor new s umístěním pro přidání prvku mě nenapadlo :) Ale myslím že pouze pro pochopení a představení stacku je moje řešení dostačující.

ďakujem za odpovede ale chcel som čo najjednoduchšiu implementáciu na pole ale aj tak díki 

nemáte predstavu čo môže človek učiaci sa programovanie robiť keď už o ccecku co  vie chcel som začať s týmito dátovými štruktúrami ale nwm či je to správna cesta :P

#9 Koler

Ucis sa c alebo c++ ?

#10 vitamin
Mimochodem můžu se zeptat co je to T&& t. S C++11 jsem zatím nedělal.

#11 Luckin
rvalue referencia. Pouziva sa na presuvanie objektov:

#include <iostream>

class C{
	double* data;

	public:
		C(){
			std::cout << "C()\n";
			data = new double[10000];
		}

		~C(){
			std::cout << "!C()\n";
			delete[] data;
		}

		C(const C& c){	//copy constructor (musi prekopyrovat vsetkych 10k prvkov)
		
			std::cout << "C(const C&)\n";
			data = new double[10000];
			for(size_t i = 0; i < 10000; ++i)
				data[i] = c.data[i];
		}
		C(C&& c){	//move constructor (iba presunie prvky, konstruktor vie ze objekt c sa uz nebude pouzivat)
			std::cout << "C(C&&)\n";
			data = c.data;	
			c.data = nullptr;
		}
};

C create_C(){
	C c;
	return c;	//vola sa move constructor
	return C();	//toto zabrani optimalizaciam...
}

int main(){
	C c1;

	C c2(c1);		//vola sa copy constructor

	C c3 = create_C();	
}

http://en.wikipedia.org/wiki/C%2B%2B11#Rvalue_references_and_move_constructors

#12 vitamin
Chápu správně, že to slouží k přesouvání deklarovaných objektů, tedy objektů vytvořených na stacku, ven z funkcí nebo bloků?

#13 Luckin
http://www.youtube.com/watch?v=OB-bdWKwXsU  37:10

#14 vitamin
Pochopil jsem, že jsem to v podstatě pochopil.

#10 vitamin
c++ :D