Wednesday, September 8, 2010

Stack Implementation in C++ through an array

Stack is one of the important data structures that every computer programmer should be aware of. It follows the simple LIFO (Last In First Out) principle. Implementation of stack can be done in many ways. One of the simplest way is using Arrays. Here an array is initialized to a maximum value first, lets call it capacity. As and when we push elements onto the array, its size will get increased. When the size reaches the capacity, we should ideally double the array size. But in the code given below I am not doing that.



#include <iostream>
        using namespace std;
        #define STACKSIZE 10
        class stack
        {
                private:
                        int arr[STACKSIZE+1];
                        int tos;
                public:
                        stack();
                        void push(int x);
                        int  pop();
                        bool is_empty();
                        bool is_full();
                        int  size();
                        void display();
        };

        stack::stack()
        {
                tos = 0;
        }

        void stack::push(int x)
        {
                if(!is_full())
                        arr[tos++] = x;
                else
                        cout << "Stack is full, Can not push " << x << endl;
        }

        int stack::pop()
        {
                if(!is_empty())
                        return arr[--tos];
                else
                        cout << "Stack is empty, cannot pop" << endl;
                return -1;
        }

        bool stack::is_empty()
        {
                if(tos == 0)
                        return true;
                else
                        return false;
        }

        bool stack::is_full()
        {
                if(tos == STACKSIZE)
                        return true;
                else
                        return false;
        }

        int stack::size()
        {
                return tos;
        }

        void stack::display()
        {
                if(tos == 0)
                {
                        cout << "No elements to display" << endl;
                        return;
                }
                for(int i=0;i
                        cout << arr[i] << " ";
                cout << endl;
        }

        int main()
        {
                stack mystack;
                cout << mystack.size() << endl;
                mystack.push(1);
                if(mystack.is_full())
                        cout << "stack is full" << endl;
                mystack.pop();
                if(mystack.is_empty())
                        cout << "stack is empty" << endl;
        }


Cheers!!
Bragaadeesh.

5 comments:

Cpt. Jack Sparrow said...

Hi!
first of all...this helped me a lot in grasping the concept...
however i am having problem doing this same code for char input in Visual C++ 2010...
can you help?
thanx.

bragadeesh said...

hi jack,

sure i can help.. can you paste some code and probably what error you are facing>

Cpt. Jack Sparrow said...

Here is the code(same as yours but char input instead of int)
***********************************
#include
#include
#include
using namespace std;
#define STACKSIZE 30
class stack
{
char *stack_arr[STACKSIZE+1];
char *ch;
int top;
public:
stack();
void push(char &c);
char* pop(void);
bool is_empty(void);
bool is_full(void);
void display(void);
};
stack::stack()
{
top=0;
}
void stack::push(char &c)
{
char c, *pc;
pc=&c;
*ch=*pc;
if(!is_full())
{
strcpy(stack_arr[top++], ch);
cout<<"Stack top:"<<top<<"\n";
}

else
cout<<"Stack is full!\n";
}
char* stack::pop(void)
{
if( !is_empty())
{
stack_arr[--top];
cout<<"Stack top:"<<top<<"\n";
return(stack_arr[--top]);
}
else
cout<<"The stack is empty!\n";

}
bool stack::is_empty(void)
{
if(top==0)
return true;
else
return false;
}
bool stack::is_full(void)
{
if(top==STACKSIZE)
return true;
else
return false;
}
void stack::display(void)
{
if(!is_empty())
{
for(char i=0;i<=top-1;i++)
cout<<stack_arr[i]<<" ";
cout<<"\n";
}

else
cout<<"Stack is empty, nothing to display!";
}
void main()
{

stack postfix;
postfix.push("1");
postfix.push("/");
postfix.push("2");
postfix.push("*");
postfix.display();
postfix.pop();
postfix.pop();
postfix.display();
_getch();
}
*******************************
and here's the error...
error C2082: redefinition of formal parameter 'c'
'stack::push' : cannot convert parameter 1 from 'const char [2]' to 'char &'(this one 4 times, for each input)

btyrrew said...

Hi can u give a program for implementing push pop peep

BragBoy said...

@btyrrew : Its not peep, its usually called peek(). The idea of peek() is to just return the top value from the stack and not remove it. Should be pretty simple.