Get Maximum element of stack at any instance in O(1)

// Print the maximum value in the stack in O(1)

#include<stdio.h>
#include<stack>
#include <iostream>
#include<algorithm>
using namespace std;
#define ll long long int

int main() {

stack<ll> s;
ll n,t,q;
scanf("%lld", &n);
for (int i = 0; i < n; i++) {

 scanf("%lld", &q);
 //q=1 when push element in stack
 //q=2 when pop element from stack
 //q=3 when we have to print maximum element of current stack
if(q==1) // push element to stack (always push maximum element at top)

{
scanf("%lld", &t);
      if (s.empty()) {
           s.push(t);
      }
      else {
          s.push(max(t, s.top()));
      }
}

if(q==2) // pop element from stack
{
      if (!s.empty()) {
s.pop();
      }
}
if(q==3) //Prints maximum element of stack
{
printf("%lld\n", s.top());
}
}
return 0;
}

Basically here we always push the maximum element at top of stack as while pushing element in stack we check if the element to be pushed is greater than top element of stack we push that new element otherwise we push top of stack again thus always maintaining maximum element at the top.

Check Balanced Brackets in a string !!

#include <iostream>

using namespace std;

int s1[10000],top=-1;

void push(int t)

    {

    s1[++top]=t;

}

char pop()

    {

    char x=s1[top--];

    return x;

}

int main(){

    int i,t,f=0;

    cin >> t;

    char x;

       string s;

    for(int a0 = 0; a0 < t; a0++){

         f=0;

        cin >> s;

        top=-1;

    for( i=0;i<s.length();i++)

        {

        if(s[i]=='{'||s[i]=='['||s[i]=='(')

            push(s[i]);

        else{

            

            if(s[i]=='}')

                {

                 x=pop();

                if(x!='{')

                    {

                    f=1;

                    break;

                }

                

            }

            else if(s[i]==']')

                {

                 x=pop();

                if(x!='[')

                    {

                    f=1;

                    break;

                }

            }

            else {

                 x=pop();

         

                if(x!='(')

                    {

                    f=1;

                    break;

                

            }

        }

    }

    }

    if(f==1||(top!=-1))

        cout<<"NO\n";

    else

        cout<<"YES\n";

    }

    

    return 0;

}

Program to find word whose occurrence is maximum times in a sentence using Map STL

#include <string>
#include <iostream>
#include <map>
#include <utility>
using namespace std;

int main()
{
  map<string,int> ana;
string d,s[100],s1[100];
int i=0,j=0;
while(cin>>s[i])
{
s1[j++]=s[i++];
}

for( i=0;i<j;i++)
{
ana[s1[i]]++ ;
}

map<string,int>::iterator ii;
int max=ana.begin()->second;
d=ana.begin()->first;
for(ii =ana.begin(); ii!=ana.end(); ++ii)
{
  if(ii->second >max)
  {
  max=ii->second;
  d=ii->first;
  }
}

cout<<"\n Word '"<<d<<"' Occurs max times("<<max <<")";
    return 0;
}

Anagram using Map STL in C++

#include <string>
#include <iostream>
#include <map>
using namespace std;
int main()
{
  map<char,int> ana;
    map<char,int> ana1;
string s,s1;
int i,f=0;
cin>>s>>s1;

  for(i=0;i<s.length();i++)
  {
  ana[s[i]]++; //indexing each character of input string using map1
  }
 
  for(i=0;i<s1.length();i++)
  {
  ana1[s1[i]]++;   //indexing each character of input string using map2
  }
 
map<char,int>::iterator ii;  //iterator to access each element of map
map<char,int>::iterator jj;
if(ana.size()==ana1.size())
{
    for(ii =ana.begin(),jj=ana1.begin(); ii!=ana.end(); ++ii,++jj)
    {
      if(ii->first==jj->first&&ii->second==jj->second)
      {
      f=1;
      }
      else
      {
      f=0;
      break;
    }
    }

    if(f==0)
    cout<<"NOT";
    else
    cout<<"YEs";
}
else
cout<<"NOT";
return 0;
}

Program to Reverse a Sentence.

#include<iostream>
using namespace std;
string rev;
void reverse(string ch[],int n)
{
int i,j;
for(i=0,j=n-1;i<n/2;i++,j--)
{
string t=ch[i];
ch[i]=ch[j];
ch[j]=t;
}
for(i=0;i<n;i++)
{
cout<<ch[i]<<"  ";
}
}

int main()
{
string str[100],s[100];
int i=0,j=0;
while(cin>>str[i])
  {
  s[j]+=str[i++];
  j++;
  }
  reverse(s,j);
}

Efficient Program for Factorial using Memoization

#include <iostream>

using namespace std;

long long int cache[100000]={0};

long long int fact(long long int n)

{

if(n<=1)

return 1;

else 
    if(cache[n]>0)

return cache[n];

else

{

        long long int v=n*fact(n-1);

cache[n]=v;

return v;

}

}

int main()

 {

    long long int n;

   cin>>n;

   cout<<"Factorial of  "<<n <<"is = "<<fact(n);

   return 0;

}

Check string ,if palindrome using Queue

#include<iostream.h>

#include<conio.h>

#include<stdio.h>

#include<string.h>

#define que_size 10

int front=-1;

int rear=-1;

char q[que_size];

void insert(char c)

{

         if(rear==que_size-1)

    {

         printf("\n\nOverflow Occurs!!");

         getch();

         return;

     }

          if(front==-1)

          front=front+1;

          rear =rear+1;

          q[rear]=c;

}

void display()

{

          int i;

          if(front==-1)

     {

          printf("\n\nQueue is empty !!");

     }

         else

     {

         printf("\n\nString is : ");

         for(i=front;i<=rear;i++)

      {

         printf("%c",q[i]);

      }

    }

}

void check()

{

         int f;

         while(front!=rear)

    {

         if(q[front]==q[rear])

      {

         f=1;

         front++;

         rear--;

      }

        else

     {

        f=0;

        break;

     }

  }

        if(f==1)

        printf("\nString is a palindrome !!");

        else

        printf("\nString is not a palindrome!!");

}

void main()

{

       int i;

       char s[10];

        clrscr();

        printf("\nEnter string : ");

        gets(s);

        for(i=0;i<=strlen(s)-1;i++)

    {

        insert(s[i]);

    }

        if(rear!=que_size-1)

   {

       display();

       check();

   }

      getch();

}

Output: