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.

Quote:

---

Originally Posted by chad101

Let’s say I wanted to push 5, 9, and 3 on to the stack. How would I store this on a single “int”?

---

as daved said, they have to be small numbers and even then it'd be a small stack.

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.

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;
}

---

:D

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.

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>