1 int stack ADT

This is a discussion on 1 int stack ADT within the C++ Programming forums, part of the General Programming Boards category; Is it possible to make a Stack ADT, using a single C++ int data type to contain ALL of the ...

  1. #1
    Pupil
    Join Date
    Oct 2005
    Location
    Toledo
    Posts
    27

    Question 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?

  2. #2
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    They would have to be small numbers, and the maximum size of the stack would be pretty small, but yes, you could.

  3. #3
    Pupil
    Join Date
    Oct 2005
    Location
    Toledo
    Posts
    27

    Question thank you

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

  4. #4
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    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.

  5. #5
    semi-colon generator ChaosEngine's Avatar
    Join Date
    Sep 2005
    Location
    Chch, NZ
    Posts
    597
    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.
    Last edited by ChaosEngine; 11-07-2005 at 06: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?

  6. #6
    Pupil
    Join Date
    Oct 2005
    Location
    Toledo
    Posts
    27

    got it

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

  7. #7
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    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).

  8. #8
    C++ Newbie
    Join Date
    Nov 2005
    Posts
    49

    Talking

    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 12:54 AM.

  9. #9
    Pupil
    Join Date
    Oct 2005
    Location
    Toledo
    Posts
    27

    sure

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

  10. #10
    Registered User
    Join Date
    Apr 2003
    Posts
    2,662
    #include <stdlib.h> --> <cstdlib>

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Debug Error Really Quick Question
    By GCNDoug in forum C Programming
    Replies: 1
    Last Post: 04-23-2007, 12:05 PM
  2. Replies: 1
    Last Post: 10-27-2006, 01:21 PM
  3. Replies: 2
    Last Post: 03-24-2006, 07:36 PM
  4. easy if you know how to use functions...
    By Unregistered in forum C Programming
    Replies: 7
    Last Post: 01-31-2002, 06:34 AM
  5. My graphics library
    By stupid_mutt in forum C Programming
    Replies: 3
    Last Post: 11-26-2001, 05:05 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21