Is it possible to make a 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?
Is it possible to make a 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?
They would have to be small numbers, and the maximum size of the stack would be pretty small, but yes, you could.
Let’s say I wanted to push 5, 9, and 3 on to the stack. How would I store this on a single “int”?
I would use bit manipulation. It takes 4 bits to represent the numbers 1-9, and your implementation probably uses a 32-bit integer, so you could probably hold up to 8 values on your stack. The implementation would be pretty detailed, so I'll leave that for you to do. Just think of the int as a series of bits, and you can separate the bits into logical pieces, and use each piece separately.
as daved said, they have to be small numbers and even then it'd be a small stack.Originally Posted by chad101
one way to do it would be to specify that all numbers are 4 bits. Assuming a 32 bit int you can then store 8 4bit numbers in the stack using bit-shifting.
or you could say that each number is a single decimal digit and just divide by 10^stack position
either way it's not gonna be much use.
Last edited by ChaosEngine; 11-07-2005 at 07:21 PM. Reason: damnit he just beat me to it!!
"I saw a sign that said 'Drink Canada Dry', so I started"
-- Brendan Behan
Free Compiler: Visual C++ 2005 Express
If you program in C++, you need Boost. You should also know how to use the Standard Library (STL). Want to make games? After reading this, I don't like WxWidgets anymore. Want to add some scripting to your App?
Code:#include <iostream.h> #include <stdlib.h> int main() { unsigned int x; unsigned int nibble; int size = sizeof(unsigned int); int count = 0; x = 0; cout << "count groups of 4 bits (nibbles) from right to left ...\n\n"; x = 1 << (count++ * size); x += 2 << (count++ * size); x += 3 << (count++ * size); x += 4 << (count++ * size); x += 5 << (count++ * size); x += 6 << (count++ * size); x += 7 << (count++ * size); x += 8 << (count * size); //-------------------------------- //nibble = ( x >> (2 * 4) ) & 0x0F; //x += -nibble << (2 * 4); //x += 4 << (2 * 4) & 0x0F; cout << "\n... retrieve values ...\n\n"; for (count=0; count<8; count++) { nibble = ( x >> (count * size) ) & 0x0F; cout << nibble <<endl; } system("PAUSE"); return 0; }
Well done.
Two things I would mention. A stack is generally first in last out, so you should probably try to retrieve the values in the opposite order. Also, <iostream.h> is out-dated and non-standard (your code doesn't compile on my compiler). You should use <iostream>, which requires you to specify the std namespace (simply done by adding using namespace std; to your code).
Hello, chad101. May I copy your code down for reference so I can write something like that after?
I will include your board name and the forum address as the code source in the file.
Last edited by Frost Drake; 11-12-2005 at 01:54 AM.
sure Here is the finished version.
Code://---------------------------------------------------------- // Written By: Chad Wood // Date: 11-13-05 // Description: one int stack //---------------------------------------------------------- #include <iostream> #include <stdlib.h> using namespace std; const int MAX_ITEMS = 8; template <class ItemType> class Stack { private: ItemType stk; ItemType top; public: Stack() : stk(0), top(-1) {} void MakeEmpty() { stk = 0; top = -1; } bool IsEmpty() const { return (top == -1); } bool IsFull() const { return (top == MAX_ITEMS - 1); } void Push(ItemType temp) { if (IsFull()) { cout << "\n Error! Stack is full "; return; } if (temp >15 || temp < 0) { cout << "\nError! Range is not 0-15 \n"; return; } stk += temp << (++top * 4); } void Pop() { if (IsEmpty()) { cout << "\n Error! Stack is empty"; return; } top--; } ItemType Top() { ItemType temp = ( stk >> (top * 4) ) & 0x0F; return temp; } void PrintStack() const { ItemType print; for (ItemType i = top; i > -1; i--) { print = ( stk >> (i * 4) ) & 0x0F; cout << print << endl; } } }; //end class int main() { Stack<int> st; char i; while(i != '5') { cout << "\n****Press 5 to quit****"; cout << "\n 1 push | 2 pop | 3 Top of stack | 4 MakeEmpty "; cin >> i; switch(i) { case '1': { //ItemType num int num; cout << "Enter number to push "; cin >>num; cin.ignore(); st.Push(num); st.PrintStack(); break; } case '2': { st.Pop(); st.PrintStack(); break; } case '3': { cout << "\nTop is: " << st.Top() <<endl; break; } case '4': { st.MakeEmpty(); cout << "\nStack is empty "; break; } } // end switch } // end while loop system("PAUSE"); return 0; }
#include <stdlib.h> --> <cstdlib>