Klasa stosu C++

Question

W jaki sposób do takiej klasy stosu mogę dodać dynamiczną alokację pamięci? 

#define STACKSIZE 20

class stack
{
public:
void push(int a);
int pop();
void clear();
stack();
~stack();
private:
int top;
int dane[STACKSIZE];
};

#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include "stack.h"

stack::stack()
{
	this->top=0;
}

stack::~stack()
{
}

void stack::clear()
{
	this->top=0;
}

void stack::push(int a)
{
	assert(this->top<STACKSIZE);
	this->dane[this->top++]=a;
}

int stack::pop()
{
	assert(this->top>0);
	return this->dane[--this->top];
}

 

Comments

Ale w jakim sensie ? Takim, że np stos zaczyna się zapełniać i wtedy alokujesz większą liczbę pamięci ? Czy jak ?

---

Tak.

---

No to własnie tak jak powiedziałem xD a znasz operatory new i delete ?

---

No znam, tylko za bardzo w jakim miejscu użyć. Czy alokacja powinna być być w funkcji wrzucania elementów i zwolnienie pamieci w destruktorze czy osobne funkcje powinienem stworzyć?

---

Ja bym próbował w miejscu wrzucania elementów, popróbuj :) na własnych błędach nauczysz się najwięcej, ja tak robię :)

Answer 1

Po pierwsze nie pisz wszędzie this->. To niepotrzebne i strasznie sie czyta ten kod.

Czy alokacja powinna być być w funkcji wrzucania elementów i zwolnienie pamieci w destruktorze czy osobne funkcje powinienem stworzyć?

To w destruktorze na pewnie nie. Ofc też w destruktorze, ale nie o tym mówimy. Zwalniać będziesz więcej niż raz. Gdy będziesz chciał dodać element, a tablica będzię już wypełniona, to będziesz chciał:

1. Zaalokować nową, większą tablice.
2. Przekopiować do nowej tablicy dane ze starej i za przekopiowanymi danymi dokopiować dodawany element.
3.  Zwolnić starą, niepotrzebną już tablice.

 Więc powyższe kroki powinny być wykonywane w metodzie nazwanej u ciebie push. To czy napiszesz w celu zwalniania i alokacji tablicy osobną metode, to już tylko kwestia przejrzystości kodu czy twojego widzimisie.

Answer 2

Przede wszystkim wywal tą tablice. Stos to struktura dynamiczna.

Jakbyś chciał się bawić w robienie stosu w ten sposób, czyli na statycznych danych to równie dobrze mogłeś użyć vectora.

Stos, jako struktura dynamiczna powinien być tworzony jak sama nazwa wskazuje dynamicznie, czyli na wskaźnikach.

Stwórz sobie strukture w następujący sposob:

struct struktura{

struktura * nastepny;

// dane



}

I niech wszystko odbywa się dynamicznie.
Najpierw deklarujesz sobie wskaźnik wsk którym za pomocą operatora new zaalokujesz sobie dynamicznie zmienna typu struktura, oraz jeden wskaznik pomocniczy, nazwijmy go wskpom. Masz wiec wskaznik na pierwsza "cegielke z danymi" na twoim stosie. Kiedy chcesz dodać nowy element do stosu dajesz wskpomowi adres ktory trzyma wsk, zeby ci sie ten adres nie zgubil i za pomoca wsk znowu uzywasz new do zrobienia sobie kolejnej dynamicznej zmiennej typu struktura. Teraz wyjasnia sie po co wskaznik wewnatrz struktury. Wskaznikowi nastepny wewnatrz Twojej nowoutworzonej zmiennej ktorej adres trzyma wsk przypisujesz to co trzyma wskpom, czyli adres cegielki "pod nim" na stosie. I jak chcesz dodać kolejna "cegielke" to znowu, wskpom dostaje adres wsk zebys mial adres elementu na szczycie stosu, wsk alokuje nowa zmienna i tak dalej i tak dalej.

Tym sposobem każdy element stosu pamięta adres elementu pod nim, a calosc odbywa sie, jak przystalo na dynamiczna strukture, a jakze, dynamicznie.

Co do usuwania elementow ze stosu, mysle ze domyslasz sie ze trzeba poruszać się wskaźnikami odwrotnie.
Nie wrzuce ci tu gotowego kodu, bo to juz twoje zadanie go napisac ;)
Jesli sa jakies niejasnosci to pytaj.

Comments

To o czym piszesz to nie stos :)

---

A co? :) Jakaś argumentacja?

Ja w tym co przekazałem widzę dynamiczną kolejkę LIFO - stos.