Need a lot of help with stack program

[Gintaras]

Hello guys, first of all, I'm sorry if my English is bad.. :D
So, I'm going straight to the topic. I need some help with my programming homework.

"Write a program to create a stack from a given set of numbers. Provide two program variations that have different ways of implementing the stack. In one case, the stack is realized by static data structure, otherwise it is a dynamic data structure. In both cases, the values of a given numbers are scanned from the original data file. Write individual functions that check whether the stack is empty, add new elements to the stack, remove elements from the stack. The program implements a dialogue with the user to help manage the program. After every change show stack content on the screen, post the final content to the results file after the program is executed. Compare the speed of execution of both versions of the program and provide conclusions."


Maybe for you, guys it will look simple, but I don't really know where I should even start.. I'm so desperate for help, I could even repay you with some steam games I have... :D It's due on tuesday :/

[jonnin]

like all programs, you start by breaking it down.
are you past objects/classes yet, or is this without?

a static stack without classes is just an array.

int stack[some_max_size];
unsigned int position = 0;

void push(int* s, unsigned int &pos, int value)
{
if(pos >= some_max_size)
//some error message, return statement
else //not needed due to return statement, but the IMPLIED else:
s[pos++] = value;
}

int pop(int* s, unsigned int &pos, int value)
{
if(pos)
return s[pos--];
else
//error message and stuff
}

something like that? Do you need more than push and pop? Because you have to manually track and handle position, you don't need all the 'is empty' function stuff, because you KNOW that all the time.

What you do when you overflow the max size matters.
the dynamic one, if you reallocate memory or not will matter too. Its unclear what is wanted for the edge cases, or if you are just supposed to handle it quietly and correctly however you want.

see if you can use something like that as a starting point. If its in a class, wrap it in a class ... array and position are members, the functions become member functions, right?

[Gintaras]

But as I know, in stack, when you add new element, it should appear in the beggining.
For example, if my stack looks like this: "1 2 3 4 5" and I add "10", it should look like this "10 1 2 3 4 5". But in my program, I can only do it like this "10 1 2 3 4". I know that my mistake is in this part:

cout << "Enter your numer: ";
cin >> nb;
for (int i = size; i > 0; i--)
{
Stack[i] = Stack[i - 1];
}
Stack[0] = nb;

[Repeater]

From that example, looks like you're not increasing the value of size, so that when you print out the stack, you're still only printing out the first 5 items on the stack instead of all six.

[Gintaras]

But I defined size as 100 at the beggining and in my example stack only has 5 elements in it and I put in the sixth one, so shouldn't that be enough? I know, I'm pretty bad at it, still learning.. :D

[Gintaras]

Okay, so I completed my static stack and everything looks fine. How could I turn it to dynamic?

[jonnin]

the easy way out is to use this opportunity to learn about <vector> which is one of the most used things in c++ and can do a lot of the work for you. If that is not viable, or you want to do it yourself, you need to learn about pointers and allocating your own memory. When the user fills up the memory, you have to get a bigger piece of memory, copy all the items over, and delete the old memory.

my approach to this is to allocate a lot more than what I need, let the user fill that up, and if the size of the stack ever exceeds what I gave them, double it. If it happens again, double it again.

so it looks exactly the same except when the stack becomes full, you run through an additional routine that fixes the problem by allocating a bigger slot, updating max possible size, copy over, deallocate old one, and return to your normal push routine. looks roughly like

void push(something * stack, unsigned int &size, unsigned int &next, something newitem)
{
..blah
if(adding 1 more exceeds max size)
reallocatestack(... ); //does the memory management stuff
stack[next++] = newitem; //push continues as before.
}

if you want to get really, really fancy you can un-grow the stack if it becomes very empty, like less than 50% full you can remove some of the excess. This is usually not worth the trouble and more often than not a performance hit to recover memory (and we typically have a lot more memory than we need available these days).