There are essentially two steps to the problem, given
void foo ( int num );
1. do something with num % 2
2. call foo ( num / 2 );
Changing the order of those two steps changes what happens - feel free to experiment.
Oh, and you also need something to decide when to stop recursing otherwise you'll just go on until you run out of stack.
Salem
Posting Sage
11,531 posts since Dec 2005
Reputation Points: 5,862
Solved Threads: 953
There are essentially two steps to the problem, given
void foo ( int num );
1. do something with num % 2
2. call foo ( num / 2 );
Changing the order of those two steps changes what happens - feel free to experiment.
Oh, and you also need something to decide when to stop recursing otherwise you'll just go on until you run out of stack.
Yes essentially you are using the stack instead of recursion. So if you understand recursion than that shouldn't be a problem.
You would use while
((! Stack.empty())
to test if your stack is empty.
There is plenty of information on the web documenting the use of the stack from the STL.
iamthwee
Posting Expert
5,950 posts since Aug 2005
Reputation Points: 1,543
Solved Threads: 439
you mean my program is already using stack?actually i know nothing about stack and i just started c++ a week ago. i am still learning now.
huh?
You started programming a week ago and you're already learning data structures? Hmm, you must have an incompetent teacher like myself. LOL.
Anyhow, let's try and make sense of this.
>you mean my program is already using stack
By this are you asking, 'is there already a facility in c++ such that I don't have to write my own stack, templated procedure?' If that's the case then yes. Using 'stack' from the STL will provide you will all the rudimentary things you need to do. Like push and pop stuff from the stack.
>i am still learning now
me too welcome to the club.
iamthwee
Posting Expert
5,950 posts since Aug 2005
Reputation Points: 1,543
Solved Threads: 439
>>is there a specific function to push and pop
No. It depends on the implementation. If you are going to implement your own stack then you get to decide how do set things up. If you are using a third party implementation then you use the functions provided without worrying about the implementation as long as they meet your needs.
Lerner
Nearly a Posting Maven
2,382 posts since Jul 2005
Reputation Points: 739
Solved Threads: 396
The easiest answer is that you will probably find any number of stack implementations by searching the web. However, you will learn more by doing it yourself.
The two versions of implementing a stack that I'm most familiar with use either an array or a list as the underlying container, and build the stack as a wrapper around the underlying container. I am only familiar with implementing stacks using C++, so if you want to do it in C then I'll be of less help.
With an array based stack class you declare an array of a given size, you can use either static or dynamic memory, and then have a second member variable keep track of the last index actually used. Popping then amounts to decrementing the last index and pushing should be straightforward from what I've said already.
With a list, I find it easiest to always push/pop from the head of the list.
This information plus what Salem gave you should put you well on the way to at least roughing out your project. Post code and specific questions if necessary and someone will probably help from there.
Lerner
Nearly a Posting Maven
2,382 posts since Jul 2005
Reputation Points: 739
Solved Threads: 396
i am doing it in C++ and i dont have the faintest idea how to create a stack.i only know how to enter variables but not stacks :sad:
code such as
int x;
cin>> x;
cout<< x; :sad: :cry:
Ha ha, you need to go back to school and study sum more kiddo.
Does your stack need to be built using templates?
iamthwee
Posting Expert
5,950 posts since Aug 2005
Reputation Points: 1,543
Solved Threads: 439
>I believe its too hard to use templates
Maybe, although they afford a great deal of advantages, such as allowing one to create a stack of a generic type; char, int, string etc.
We'll wait until he gets back. I hope he knows what object-orientated design is at the very least. Most creations of stacks rely on this principle, or so I've read. Tee he he.
iamthwee
Posting Expert
5,950 posts since Aug 2005
Reputation Points: 1,543
Solved Threads: 439
As a start the code you posted looks okay. I might change a few things here and there to simplify it a bit so you don't have so much stuff in the way of understanding about the basic protocols, but it should work. Basically, it's creating a stack class using an array called items as the underlying container and using the variable Top to indicate the last index used (top could also be the first index available if you prefer, but I prefer the last index used).
Now it's time to start implementing each of the functions.
I'll start with the assumption you know that array indexes are zero based. Given that, you will need to use some integer value for top that could never be used as an index of items to indicate when there are no items in the array. Assign that value to top in the constructor and evaluate for that value when determining whether the stack is empty or not. Then when you push a add a new item to items increment top and when you remove an item from items decrease the value of top. You will probably want to do some bounds checking to be sure you don't try to pop from an empty stack or try push an item on a stack that's already full, but that is a level of sophistication above and beyond the actual mechanism to push and pop.
Write just one function at a time, not all at once.
Lerner
Nearly a Posting Maven
2,382 posts since Jul 2005
Reputation Points: 739
Solved Threads: 396
You might want to wack that in a header file or something.
Next step would be to test your stack implentation using a main().
Try simple stuff like pushing a bunch of numbers onto the stack then systematically popping them out, whilst at the same time displaying them on the screen.
iamthwee
Posting Expert
5,950 posts since Aug 2005
Reputation Points: 1,543
Solved Threads: 439
Well I can only assume your stack was built using notes you obtained from class.
With those notes you should also have a little snippnet detailing how you might actually use your stack inside int main().
You don't necessarily need to put your stack inside another header file but it's convenient to do so.
Look here's an example, using stack from the STL, it's content should be similar to your own.
#include <iostream>
#include <stack> //this is basically the utility you have been
//asked to design
using namespace std;
int main()
{
stack <char> thwees_stack;//initialise stack
thwees_stack.push('i'); //push chars onto the stack
thwees_stack.push('a'); //push chars onto the stack
thwees_stack.push('m'); //push chars onto the stack
thwees_stack.push('t'); //push chars onto the stack
thwees_stack.push('h'); //push chars onto the stack
thwees_stack.push('w'); //push chars onto the stack
thwees_stack.push('e'); //push chars onto the stack
thwees_stack.push('e'); //push chars onto the stack
while (! thwees_stack.empty()) //test if stack is empty
{
cout<<thwees_stack.top(); //print wat's at the top of da stack
thwees_stack.pop(); //delete from da stack
}
cin.get();
}
iamthwee
Posting Expert
5,950 posts since Aug 2005
Reputation Points: 1,543
Solved Threads: 439
