Day-13.txt

                                  Day-13



1. Implement stack using Array

ANS.  

#include <stdio.h>
#include <stdlib.h>
struct Stack
{
    int size;
    int Top;
    int *s;
};
void push(struct Stack *st, int x)
{
    if (st->Top == st->size - 1)
        printf("stack overflow");
    else
    {
        st->Top++;
        st->s[st->Top] = x;
    }
}
int pop(struct Stack *st)
{
    int x = -1;
    if (st->Top == -1)
        printf("stack underflow");
    else
    {
        x = st->s[st->Top];
        st->Top--;
    }
    return x;
}
int peek(struct Stack st, int pos)
{
    int x = -1;
    if (st.Top - pos + 1 < 0 && st.Top - pos + 1 > st.size - 1)
        printf("invalid position");
    x = st.s[st.Top - pos + 1];
    return x;
}
int stacktop(struct Stack st)
{
    if (st.Top == -1)
        return -1;
    else
        return st.s[st.Top];
}
int isEmpty(struct Stack st)
{
    if (st.Top == -1)
        return 1;
    else
        return 0;
}
int isFull(struct Stack st)
{
    if (st.Top == st.size - 1)
        return 1;
    else
        return 0;
}
void display(struct Stack st)
{
    for (int i = st.Top; i >= 0; i--)
    {
        printf("%d ", st.s[i]);
        printf("\n");
    }
}
int main()
{
    struct Stack st;
    printf("enter the size of the stack");
    scanf("%d", &st.size);
    st.s = (int *)malloc(st.size * sizeof(int));
    st.Top = -1;

    push(&st, 10);
    push(&st, 20);
    push(&st, 30);

    printf("top=%d\n", peek(st, 2));
    display(st);
}



2.   Implement Queue using Array

ANS.  

     
     #include <stdio.h>
#include <stdlib.h>

struct Queue
{
    int size;
    int front;
    int rear;
    int *Q;
};

void enqueue(struct Queue *q, int x)
{
    if ((q->rear + 1) % q->size == q->front)
        printf("queue is full");
    else
    {
        q->rear = (q->rear + 1) % q->size;
        q->Q[q->rear] = x;
    }
}

int dequeue(struct Queue *q)
{
    int x = -1;
    if (q->front == q->rear)
        printf("queue is empty");
    else
    {
        q->front = (q->front + 1) % q->size;
        x = q->Q[q->front];
    }
    return x;
}

void Display(struct Queue q)
{
    int i = q.front + 1;
    do
    {
        printf("%d ", q.Q[i]);
        i = (i + 1) % q.size;
    } while (i != (q.rear + 1) % q.size);
}
void create(struct Queue *q, int size)
{
    q->size = size;
    q->front = q->rear = 0;
    q->Q = (int *)malloc(q->size * sizeof(int));
}

int main()
{
    struct Queue q;
    create(&q, 5);
    enqueue(&q, 12);
    enqueue(&q, 22);
    enqueue(&q, 32);
    enqueue(&q, 42);
    dequeue(&q);
    Display(q);
    return 0;
}



3.   Implement Stack using Queues

ANS.

queue<int> q1,q2;
    MyStack() {
        
    }
    
    void push(int x) {
        q2.push(x);
        if (q1.empty()==false)
        {
            while (!q1.empty())
            {
                q2.push(q1.front());
                q1.pop();
            }
        }
        swap(q1,q2);
    }
    
    int pop() {
        int x=-1;
        if (q1.empty()==false)
        {
           x=q1.front();
           q1.pop();   
        }
        return x;
    }
    
    int top() {
        return q1.front();
    }
    
    bool empty() {
      return q1.empty(); 
    }
};

     

4.   Implement Queues using Stack

ANS.   
 stack<int> s1;
    stack<int> s2;
    
    MyQueue() {
        
    }
    
    void push(int x) {
        s1.push(x);
    }
    
    int pop() {
        int res=-1;
        if (s2.empty()==true)
        {  
           if (s1.empty())
               return res;
           else
           {
               while (!s1.empty())
                {
                    int x=s1.top();
                    s1.pop();
                    s2.push(x);
                }  
           } 
        }
        res=s2.top();
        s2.pop();
        return res;
    }
    
    int peek() {
        if (s2.empty()==false)
            return s2.top();
        else
        {
            while (!s1.empty())
                {
                    int x=s1.top();
                    s1.pop();
                    s2.push(x);
                }
                return s2.top();
        }
        
    }
    
    bool empty() {
        if (s1.empty() && s2.empty())
            return true;
        else
            return false;
     }
    
   

5. Valid Parentheses

ANS.  1st approach (using stack):

      bool isValid(string s) {
       stack<char> st;
        for (int i=0;i<s.size();i++)
        {
            if (s[i]=='(' ||s[i]=='[' || s[i]=='{')
                st.push(s[i]);
            else 
            {
                if (st.empty())
                    return false;
                char y=st.top();
                st.pop();
                
                if (s[i]-y==1)
                    continue;
                else if (s[i]-y==2)
                    continue;
                else
                    return false;
            }
        }
         return st.empty();
    }


6.  Next Greater Element I

ANS.  

vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        vector<int> v;
        stack<int> s;
        map<int,int> m;
        m[nums2[nums2.size()-1]]=-1;
        s.push(nums2[nums2.size()-1]);
        for (int i=nums2.size()-2;i>=0;i--)
        {
            while (s.size()>0 && s.top()<=nums2[i])
                s.pop();
            if (s.empty())
                m[nums2[i]]=-1;
            else
                m[nums2[i]]=s.top();
            
            s.push(nums2[i]);
                
        }
        for (int i=0;i<nums1.size();i++)
        {
            v.push_back(m[nums1[i]]);
        }
        
        return v;
        
    }
 


7.  Sort an Array Using Recursion

ANS.  1st approach (makes the input smaller in each step):

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

void inserts(vector<int>& nums,int temp)
    {
        if (nums.size()==0 || nums[nums.size()-1]<=temp)
        {
            nums.push_back(temp);
            return;
        }
        int val=nums[nums.size()-1];
        nums.pop_back();
        inserts(nums,temp);
        nums.push_back(val);
    }
    void sorting(vector<int>& nums)
    {
        if (nums.size()==1)
            return;
        int temp=nums[nums.size()-1];
        nums.pop_back();
        sorting(nums);
        inserts(nums,temp);
    }
    
    int main()
    {
        vector<int> v={1,5,2,24};
        sorting(v);
        for (int i:v)
        cout<<i<<" ";

    }

8.   Sort the Stack

ANS.  1st approach ():

void insert(stack<int> &s,int temp)
{
    if (s.size()==0 || s.top()<=temp)
    {
        s.push(temp);
        return;
    }
    int val=s.top();
    s.pop();
    insert(s,temp);
    s.push(val);
}
void SortedStack :: sort()
{
   if (s.size()==0)
      return;
   
   int temp=s.top();
   s.pop();
   sort();
   insert(s,temp);
   
}
      

9.  Reverse a Stack

ANS.   1st approach ():

    
void insert_at_bottom(stack<int> &s,int temp)
{
    if (s.size()==0)
    {
        s.push(temp);
        return;
    }
    int val=s.top();
    s.pop();
    insert_at_bottom(s,temp);
    s.push(val);
}

void reverseStack(stack<int> &st) {
    if (st.size()==0)
        return;
    int temp=st.top();
    st.pop();
    reverseStack(st);
    insert_at_bottom(st,temp);
}
    

10.  Delete middle element of a stack 

ANS.   1st approach ():

        void remove(stack<int>&s, int n,int i)
    {
        if (i==n)
        {
          s.pop();
          return;
        }
          
        int x=s.top();
        s.pop();
        remove(s,n,i+1);
        s.push(x);
    }
    
    //Function to delete middle element of a stack.
    void deleteMid(stack<int>&s, int sizeOfStack)
    {
        sizeOfStack=(sizeOfStack/2.0)+1;        remove(s,sizeOfStack,1);
    }