Sunday, November 20, 2011

Data Structure: Stack implementation in C++

(A) Top of stack varying method

Algorithm for top of stack varying method

1. Declare and initialize necessary variables, eg top = -1, MAXSIZE etc.
2. For push operation,
If top = MAXSIZE - 1
print " stack overflow"
else
top = top + 1;
Read item from user
stack[top] = item
3. For next push operation, goto step 2.
4. For pop operation,
If top = -1
print "Stack underflow"
Else
item = stack[top]
top = top - 1
Display item
5. For next pop operation, goto step 4.
6. stop

Source code for top of stack varying method

#include<iostream>
#include<cstdlib>
#define MAX_SIZE 10
using namespace std;
class Stack{
    private:
        int item[MAX_SIZE];
        int top;
    public:
        Stack(){
            top = -1;
        }
        void push(int data){
            item[++top] = data;
        }
        int pop(){
            return item[top--];
        }
        int size(){
            return top+1;
        }
        bool is_empty(){
            if(top==-1)
                return true;
            else
                return false;
        }
        bool is_full(){
            if(top==MAX_SIZE-1)
                return true;
            else
                return false;
        }
        void display(){
            for(int i=0; i<this->size(); i++){
                cout<<item[i]<<" ";
            }
            cout<<endl;
        }
};
int main(){
    int choice;
    int temp;
    Stack stack;
    while(true){
        cout<<"Choose any one of the following"<<endl;
        cout<<"1. Push Item. "<<endl;
        cout<<"2. Pop Item."<<endl;
        cout<<"3. Size of Stack."<<endl;
        cout<<"4. Display all elements of stack."<<endl;
        cout<<"5. Exit."<<endl;
        cout<<"Your Choice: ";
        cin>>choice;
        switch(choice){
            case 1:
                if(!stack.is_full()){
                    cout<<"Enter number to push: ";
                    cin>>temp;
                    stack.push(temp);
                }else{
                    cout<<"Can't push. Stack is Full!!"<<endl;
                }
                break;
            case 2:
                if(!stack.is_empty()){
                    cout<<"The number popped is: "<<stack.pop()<<endl;
                }else{
                    cout<<"Cant't pop. Stack is Empty!!"<<endl;
                }
                break;
            case 3:
                cout<<"The size of the stack is: "<<stack.size()<<endl;
                break;
            case 4:
                if(!stack.is_empty()){
                    cout<<"The elements in stack are: ";
                    stack.display();
                    cout<<endl;
                }else{
                    cout<<"Stack is Empty"<<endl;
                }
                break;
            case 5:
                exit(0);
                break;
        }
    }
    return 0;
}

(B) Top Fixed method ( Base varying method)


Algorithm for top fixed method

1. Declare and initialize necessary variables e.g. BOS = 0, MAXSIZE etc.
2. For push operation,
If BOS = MAXSIZE
print "stack overflow"
Else
Insert new element by making vacant space at stack[0] location
/* for(i = BOS; i > 0; i--){
stack[i] = stack[i-1];
}
stack[0] = BOS
++BOS
*/
3. For next push operation goto step 2.
4. For pop operation
If BOS = 0
print"stack underflow"
else
extract item from stack[0]. Decrement BOS and refil empty space by lowering each step by 1.
5. For next pop operation, goto step 4.
6. Stop




Source code for top fixed method

#include<iostream>
#include<cstdlib>
#define MAX_SIZE 10
using namespace std;
class Stack{
    private:
        int item[MAX_SIZE];
        int BOS;
    public:
        Stack(){
            BOS = 0;
        }
        void push(int data){
            for(int i=BOS; i>0; i--){
                item[i] = item[i-1];
            }
            item[0] = data;
            ++BOS;
        }
        int pop(){
            int temp = item[0];
            for(int i = 0; i<BOS; i++){
            item[i] = item[i+1];
            }
            BOS--;
            return temp;
        }
        void display(){
            for(int i = 0; i<BOS; i++){
                cout<<item[i]<<" ";
            }
            cout<<endl;
        }
        bool isEmpty(){
            if(BOS == 0){
                return true;
            }else{
                return false;
            }
        }
        bool isFull(){
            if(BOS == MAX_SIZE){
                return true;
            }else{
                return false;
            }
        }
};
int main(){
    int choice, data;
    Stack stack;
    while(true){
        cout<<"1. Push a Data"<<endl;
        cout<<"2. Pop a Data"<<endl;
        cout<<"3. Display All Element of Stack"<<endl;
        cout<<"4. Quit"<<endl;
        cout<<"Enter your choice: ";
        cin>>choice;
        switch(choice){
            case 1:
                if(!stack.isFull()){
                    cout<<"Enter the data to push: ";
                    cin>>data;
                    stack.push(data);
                    cout<<endl;
                }else{
                    cout<<"STACK IS FULL!!"<<endl;
                }
                break;
            case 2:
                if(!stack.isEmpty()){
                    cout<<"The data popped is "<<stack.pop()<<endl;
                }else{
                    cout<<"THE STACK IS EMPTY"<<endl;
                }
                break;
            case 3:
                if(!stack.isEmpty()){
                    stack.display();
                }else{
                    cout<<"STACK IS EMPTY"<<endl;
                }
                break;
            case 4:
                exit(0);
                break;
        }
    }
    return 0;
}

1 comment: