Data Structures & Algorithms – Stack

/* array implementation of stack*/
// Stack - Object oriented implementation using arrays

#include<iostream>
using namespace std;

#define MAX_SIZE 101

class Stack{
private:
    int A[MAX_SIZE];  //array to store the stack
    int top;  //variale to mark the top index of stack
public:
    Stack(){  //constructor
        top=-1;  //for empty stack,set top=-1
    }

    //Push operation to insert an element on top of stack
    void Push(int x){
        if(top==MAX_SIZE-1){  //overflow case
            cout<<"Error: stack overflow"<<endl;
            return;
        }
        A[++top]=x; //pre-increment top
    }

    //Pop operation to remove an element from top of stack
    void Pop(){
        if(top==-1){  //throw error, if stack empty
            cout<<"Error: Stack is empty"<<endl;
            return;
        }
        top--;
    }

    //Top operation to return element at top of stack
    int Top(){
        return A[top];
    }


    //this ftn returns 1(true),if stack is empty,0(false) otherwise
    bool IsEmpty(){
        if(top==-1)return 1;
        return 0;
    }

    //only for testing-not a valid operation of stack
    void Print(){
        cout<<"Stack: ";
        for(int i=0;i<=top;i++)
            cout<<A[i]<<" ";
            cout<<endl;
    }
};

int main()
{ /*Driver code to test the implementation*/
    Stack S;
    S.Push(2);
    S.Push(4);
    S.Push(6);
    S.Print();//2 4 6
    S.Pop();
    S.Print();  //2 4
    S.Push(8);
    S.Print();  //2 4 8
    return 0;
}

/* 2.2 Linked List implementation of stack */


#include<iostream>
using namespace std;

class Stack{
private:
    int data;
    Stack *link,*top;
public:
    Stack(){
        top=NULL;
    }

    void Push(int x){
        Stack* temp=new Stack;
        temp->data=x;
        temp->link=NULL;
        if(top==NULL){
            top=temp;
            return;
        }
        Stack* temp1=top;
        temp->link=temp1;
        top=temp;
    }

    void Pop(){
        Stack* temp=top;
        if(temp==NULL) {
            cout<<"Error: Stack Empty"<<endl;
            return;
        }
        top=temp->link;
        delete temp; //dealloc memory from heap
    }

    int Top(){
        Stack* temp=top;
        cout<<temp->data<<endl;
        return top->data; //return temp
    }

    int IsEmpty(){
        if(top==NULL) return 1;
        else return 0;
    }

    //only for test purpose- NOT A VALID OPERATION OF STACK
    void Print(){
        Stack* temp=top;
        while(temp!=NULL){
            cout<<temp->data<<" ";
            temp=temp->link;
        }
        cout<<endl;
    }

};

int main()
{
    Stack S;
    S.Push(3);
    S.Push(2);
    S.Push(1);
    S.Print(); //1 2 3
    S.Pop();
    S.Print(); //2 3
    S.Push(4);
    S.Print(); //4 2 3
    return 0;
}

/*  2.3-a Reversing a String using stack STL  */

#include<iostream>
#include<string.h>
#include<stack>   //stack from STL
using namespace std;

void Reverse(char *C,int n)     /*   char*C same as char C[],since arrays are passed by ref thru pointer*/
{
    stack<char> S; /*syntax:   stack<datatype> name or identifier*/

    //loop for push
    for(int i=0;i<n;i++){
        S.push(C[i]);
    }

    //loop for pop
    for(int i=0;i<n;i++){
        C[i]=S.top(); //overwrite the char at index i
        S.pop(); //perform pop
    }
}

int main()
{
    char C[50];
    cout<<"Enter a string: ";
    cin.getline(C,50);
    Reverse(C,strlen(C));
    cout<<"Output: "<<C;
    return 0;
}

/*  2.3-b Reversing a Linked List using stack STL  */


#include<iostream>
#include<stack>
using namespace std;

struct Node{
    int data;
    Node* next;
};
Node* head;

void Insert(int x){
    Node* temp=new Node;
    temp->data=x;
    temp->next=NULL;
    if(head==NULL){
        head=temp;
        return;
    }
    Node* temp1=head;
    temp->next=temp1;
    head=temp;
}

void Reverse(){
    if(head==NULL) return;
    stack< Node*>S;
    Node* temp=head;
    while(temp!=NULL){
        S.push(temp);
        temp=temp->next;
    }
    temp=S.top();head=temp;
    S.pop();
    while(!S.empty()){
        temp->next=S.top();
        S.pop();
        temp=temp->next;
    }
    temp->next=NULL;
}


void Print(){
    Node* temp=head;
    while(temp!=NULL){
        cout<<temp->data<<" ";
        temp=temp->next;
    }
    cout<<endl;
}


int main(){
    Insert(3);
    Insert(8);
    Insert(87);
    Insert(45);
    Print(); //45 87 8 3

    Reverse();
    Print();  //3 8 87 45
    return 0;
}

/*pseudocode to evaluate Postfix expression:*/

EvaluatePostfix(exp){
	create a stack S
	for i<-0 to length(exp)-1
		{
			if(exp[i] is operand)
                                         push(exp[i])
			else if(exp[i] is operator)
			{
				op2<-pop()
				op1<-pop()
				res<-perform(exp[i],op1,op2)
				push(res)
			} //end of else if
		} //end of for loop
return top of stack
}

/* Pseudocode for Infix to Postfix */

InfixToPostfix(exp){
   create a stack S
   res<- empty string
   for(i<- 0 to length(exp)-1){
	if(exp[i] is operand){
		res<- res + exp[i]
	}
	else if(exp[i] is operator ){
		while(!s.empty() && HasHigherPreced(S.top(),exp[i]) ){
			res<- res + S.top()
			S.pop()
		}	// end of while
	S.push(exp[i])	
	}//end of else if
}//end of for loop

while(!S.empty()){
	res<-res+S.top()
	S.pop()
} //end of while
return res
}//EOF

/* Infix to Postfix with Paranthesis */

InfixToPostfix(exp){
   create a stack S
   res<- empty string
   for(i<- 0 to length(exp)-1){
	if(exp[i] is operand){
		res<- res + exp[i]
	}
	else if(exp[i] is operator ){
		while(!S.empty() && HasHigherPreced(S.top(),exp[i]) && !IsOpenParanth(S.top()) ){
			res<- res + S.top()
			S.pop()
		}	// end of while
	S.push(exp[i])	
	}//end of else if
else if(IsOpenParanth(exp[i])){    /* elseif(exp[i]==’(’)    */
	S.push(exp[i])
}//end of elseif
elseif(IsClosingParanth(exp[i])){   /*elseif(exp[i]==’)’)   */
	while(!S.empty() && IsOpen)
}//end of elseif
}//end of for loop

while(!S.empty()   &&  !IsOpenParanth(S.top())){
	res<-res+S.top()
	S.pop()
} //end of while
S.pop()
}//end of elseif

while(! S.empty()){
	res<-res+ S.top()
	S.pop()
} //end of while
return res
}//EOF