Zásobník a pole – C / C++ – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu

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

 

Koler0
Duch
7. 4. 2013   #1
-
0
-

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....   

Nahlásit jako SPAM
IP: 95.102.187.–
Luckin
~ Anonymní uživatel
57 příspěvků
7. 4. 2013   #2
-
0
-

   

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?

Nahlásit jako SPAM
IP: 89.103.156.–
vitamin+8
Grafoman
7. 4. 2013   #3
-
0
-

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 .

Nahlásit jako SPAM
IP: 95.105.157.–
obfuscate: "The cruel god Malloc will strike you down. "
ZMeson: "That's the C god. C++ has a new god. "
Luckin
~ Anonymní uživatel
57 příspěvků
7. 4. 2013   #4
-
0
-

#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.

Nahlásit jako SPAM
IP: 89.103.156.–
vitamin+8
Grafoman
7. 4. 2013   #5
-
0
-

#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...

Nahlásit jako SPAM
IP: 95.105.157.–
obfuscate: "The cruel god Malloc will strike you down. "
ZMeson: "That's the C god. C++ has a new god. "
Luckin
~ Anonymní uživatel
57 příspěvků
7. 4. 2013   #6
-
0
-

#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*);
Nahlásit jako SPAM
IP: 89.103.156.–
vitamin+8
Grafoman
7. 4. 2013   #7
-
0
-

#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);                }	
};
Nahlásit jako SPAM
IP: 95.105.157.–
obfuscate: "The cruel god Malloc will strike you down. "
ZMeson: "That's the C god. C++ has a new god. "
Luckin
~ Anonymní uživatel
57 příspěvků
7. 4. 2013   #8
-
0
-

#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í.

Nahlásit jako SPAM
IP: 89.103.156.–
Koler0
Duch
7. 4. 2013   #9
-
0
-

ď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

Nahlásit jako SPAM
IP: 95.102.187.–
vitamin+8
Grafoman
7. 4. 2013   #10
-
0
-

#9 Koler

Ucis sa c alebo c++ ?

Nahlásit jako SPAM
IP: 95.105.157.–
obfuscate: "The cruel god Malloc will strike you down. "
ZMeson: "That's the C god. C++ has a new god. "
Luckin
~ Anonymní uživatel
57 příspěvků
7. 4. 2013   #11
-
0
-

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

Nahlásit jako SPAM
IP: 89.103.156.–
vitamin+8
Grafoman
7. 4. 2013   #12
-
0
-

#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

Nahlásit jako SPAM
IP: 95.105.157.–
obfuscate: "The cruel god Malloc will strike you down. "
ZMeson: "That's the C god. C++ has a new god. "
Luckin
~ Anonymní uživatel
57 příspěvků
7. 4. 2013   #13
-
0
-

#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ů?

Nahlásit jako SPAM
IP: 89.103.156.–
vitamin+8
Grafoman
7. 4. 2013   #14
-
0
-
Nahlásit jako SPAM
IP: 95.105.157.–
obfuscate: "The cruel god Malloc will strike you down. "
ZMeson: "That's the C god. C++ has a new god. "
Luckin
~ Anonymní uživatel
57 příspěvků
7. 4. 2013   #15
-
0
-

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

Nahlásit jako SPAM
IP: 89.103.156.–
Koler0
Duch
8. 4. 2013   #16
-
0
-

#10 vitamin
c++ :D

Nahlásit jako SPAM
IP: 95.102.187.–
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 4 hosté

Podobná vlákna

Pole : zasobnik — založil Atheo

Zásobník — založil Seann_K

Zasobnik — založil bbeni

Zásobník — založil Siggi

Moderátoři diskuze

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032024 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý