Thread: 1 int stack ADT

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.

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).

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>