Stack Help
Hi. This is a homework direction. I am not understanding this part...
"In designing the data structure, you may assume that the stack elements are integers in the range 0 to 15. Given the size of the elements and the size of a variable of type int, you must determine the value of MAX_STACK. Remember, the whole stack must fit inside a single integer.
You may assume that integers are always 32 bits. (Note! This is not always true in C++. To truly find the size of int you should use the function sizeof(int).)"
Really confused about this part because it says that you may assume that the integers are always 32 bits and yet you assume the elements are integers in range 0 to 15. Shouldn't I only be concerned about the integers from 0-15?
I am also extremely confused about the "Remember, the whole stack must fit inside a single integer". What does this mean? Also, when it says "In designing the data structure" part, does that mean I have to create a structure inside of the class that is used for the stack?
I am just not sure how to initialize the stack size and what the size should be. Any hints/answers?
"In designing the data structure, you may assume that the stack elements are integers in the range 0 to 15. Given the size of the elements and the size of a variable of type int, you must determine the value of MAX_STACK. Remember, the whole stack must fit inside a single integer.
You may assume that integers are always 32 bits. (Note! This is not always true in C++. To truly find the size of int you should use the function sizeof(int).)"
Really confused about this part because it says that you may assume that the integers are always 32 bits and yet you assume the elements are integers in range 0 to 15. Shouldn't I only be concerned about the integers from 0-15?
I am also extremely confused about the "Remember, the whole stack must fit inside a single integer". What does this mean? Also, when it says "In designing the data structure" part, does that mean I have to create a structure inside of the class that is used for the stack?
I am just not sure how to initialize the stack size and what the size should be. Any hints/answers?
You need a maximum of 4 bits to store any integer between 0 and 15 (15 is 1111 in binary).
Sounds like your professor is asking you to "cram" several of these into the space of one 32-bit
Sounds like your professor is asking you to "cram" several of these into the space of one 32-bit
int....
I've used sizeof function and found out that "int" is 4 bits. So that means the value of MAX_STACK must be at least 60? (15 X 4 = 60)
Actually did you mean bytes? Because in my book it says an int is the size of 4 bytes...
I don't understand though. Why be concerned about the size and all when you could just simply initialize an integer stack size to 15 and just enter the numbers...
Actually did you mean bytes? Because in my book it says an int is the size of 4 bytes...
I don't understand though. Why be concerned about the size and all when you could just simply initialize an integer stack size to 15 and just enter the numbers...
Last edited on
No, I meant bits.
Apparently, you're supposed to assume that
So something like
(this is all in binary)
would all fit in a 32-bit
(I hope I did the conversion correctly) since 0001 is 1 in binary, 0101 is 5 in binary, and so on.
Does that make sense?
Apparently, you're supposed to assume that
int is 32 bits (which is 4 bytes), so what I think you're supposed to do is stuff a bunch of 4-bit integers (which is just enough to store the numbers 0 through 15) into a 32-bit int.So something like
0001 0101 0010 0110 1110 0101 1010 1111 |
(this is all in binary)
would all fit in a 32-bit
int (it would be 354,870,703 in decimal), but if you treat it as 8 chunks of 4 bits instead of one 32-bit number, this can also represent the numbers1 5 2 6 14 5 10 15 |
(I hope I did the conversion correctly) since 0001 is 1 in binary, 0101 is 5 in binary, and so on.
Does that make sense?
Ah I see. It makes much more sense. Now I can see why he wrote this in the other part of the directions.
"It will be necessary to manipulate individual bits in an integer variable in order to add and remove items from the stack. There are several methods you may use to accomplish this. One method is to use the bit level manipulators built into C++.
You can use the bit-wise AND operator ( & ) to clear bits:
newItem = newItem & 0x0F; // clear upper bits of newItem
You can use the bit-wise SHIFT operator to move bits:
items = items << 4; // make room for newItem
You can use the bit-wise OR operator ( | ) to set bits:
items = items | newItem; // merge newItem into items"
So, I am assuming that I will use those functions in the pop and push operations. Correct?
I understand what you're saying. But very mind boggled at the overall picture. Like why is it necessary to use the operations listed above? Or why be concerned about the sizes of each element and the variable integer.
I have made stacks without using the operations listed above and not worrying about the sizes of each element or the variable integer without problems.
15X4 is 60 bits. So, how are 15 elements going to fit in?
Lol this is the most complicated homework assignment I've ever had to be honest. I really have a lot of questions regarding to this assignment. I don't want to make a wall of text...
"It will be necessary to manipulate individual bits in an integer variable in order to add and remove items from the stack. There are several methods you may use to accomplish this. One method is to use the bit level manipulators built into C++.
You can use the bit-wise AND operator ( & ) to clear bits:
newItem = newItem & 0x0F; // clear upper bits of newItem
You can use the bit-wise SHIFT operator to move bits:
items = items << 4; // make room for newItem
You can use the bit-wise OR operator ( | ) to set bits:
items = items | newItem; // merge newItem into items"
So, I am assuming that I will use those functions in the pop and push operations. Correct?
I understand what you're saying. But very mind boggled at the overall picture. Like why is it necessary to use the operations listed above? Or why be concerned about the sizes of each element and the variable integer.
I have made stacks without using the operations listed above and not worrying about the sizes of each element or the variable integer without problems.
15X4 is 60 bits. So, how are 15 elements going to fit in?
Lol this is the most complicated homework assignment I've ever had to be honest. I really have a lot of questions regarding to this assignment. I don't want to make a wall of text...
Last edited on
Here is the entire directions.
Your assignment is to re-implement the Stack ADT, using a single C++ int data type to contain ALL of the stack elements. In other words, one integer variable is used as a stack that can store several smaller integers. One of the main points of this exercise is to impress upon you that abstract data structures need not be implemented in a way that conforms at all to our preconceived notions. Often programmers need to find new and creative (sometimes even bizarre!) ways to implement the data structures they want to use.
You must implement all the stack operations for the Stack ADT as specified.
bool isEmpty(); // returns true if stack is empty
bool isFull(); // return true if stack is full
void push(int n); // item n is pushed onto stack, throw exception on full stack.
void pop(); // removes top item from stack, throw exception on empty stack.
int top(); // returns top of stack, throw exception on empty stack.
void printStack(); // prints stack, stack is unchanged
The printStack function must neatly print the contents of a stack on the screen, in a column, one stack element per line, in the same order that the elements would come off the stack if they were to be taken off using the Pop operation. If the stack is empty, printStack has no output at all. The stack itself must be in the same state after the printStack operation is executed as it was before. The same elements are in the stack, in the same order.
In designing the data structure, you may assume that the stack elements are integers in the range 0 to 15. Given the size of the elements and the size of a variable of type int, you must determine the value of MAX_STACK. Remember, the whole stack must fit inside a single integer.
You may assume that integers are always 32 bits. (Note! This is not always true in C++. To truly find the size of int you should use the function sizeof(int).)
It will be necessary to manipulate individual bits in an integer variable in order to add and remove items from the stack. There are several methods you may use to accomplish this. One method is to use the bit level manipulators built into C++.
You can use the bit-wise AND operator ( & ) to clear bits:
newItem = newItem & 0x0F; // clear upper bits of newItem
You can use the bit-wise SHIFT operator to move bits:
items = items << 4; // make room for newItem
You can use the bit-wise OR operator ( | ) to set bits:
items = items | newItem; // merge newItem into items
Your assignment is to re-implement the Stack ADT, using a single C++ int data type to contain ALL of the stack elements. In other words, one integer variable is used as a stack that can store several smaller integers. One of the main points of this exercise is to impress upon you that abstract data structures need not be implemented in a way that conforms at all to our preconceived notions. Often programmers need to find new and creative (sometimes even bizarre!) ways to implement the data structures they want to use.
You must implement all the stack operations for the Stack ADT as specified.
bool isEmpty(); // returns true if stack is empty
bool isFull(); // return true if stack is full
void push(int n); // item n is pushed onto stack, throw exception on full stack.
void pop(); // removes top item from stack, throw exception on empty stack.
int top(); // returns top of stack, throw exception on empty stack.
void printStack(); // prints stack, stack is unchanged
The printStack function must neatly print the contents of a stack on the screen, in a column, one stack element per line, in the same order that the elements would come off the stack if they were to be taken off using the Pop operation. If the stack is empty, printStack has no output at all. The stack itself must be in the same state after the printStack operation is executed as it was before. The same elements are in the stack, in the same order.
In designing the data structure, you may assume that the stack elements are integers in the range 0 to 15. Given the size of the elements and the size of a variable of type int, you must determine the value of MAX_STACK. Remember, the whole stack must fit inside a single integer.
You may assume that integers are always 32 bits. (Note! This is not always true in C++. To truly find the size of int you should use the function sizeof(int).)
It will be necessary to manipulate individual bits in an integer variable in order to add and remove items from the stack. There are several methods you may use to accomplish this. One method is to use the bit level manipulators built into C++.
You can use the bit-wise AND operator ( & ) to clear bits:
newItem = newItem & 0x0F; // clear upper bits of newItem
You can use the bit-wise SHIFT operator to move bits:
items = items << 4; // make room for newItem
You can use the bit-wise OR operator ( | ) to set bits:
items = items | newItem; // merge newItem into items
Topic archived. No new replies allowed.