Simple Queue (Non-circular) implementation using stack through arrays in c

-

Queue can be implemented by using two stacks, either making (enqueue operation expensive O(n) and dequeue  operation simple O(1)) or (enqueue operation simple O(1) and dequeue operation expensive O(n)).

I've done it by Enqueue operation simple O(1) 
and Dequeue operation expensive O(n).

Note: A stack can also be implemented using Queue by??

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

void enqueue(int stack[], int *top, int size, int data)
{

    *top=*top+1;
    stack[*top]=data;
}
void dequeue(int s1[], int *t1, int size)
{
    int i,top;
    int stack2[size], top2=-1;
if(*t1==-1)
    printf("Queue is already empty!");
else
    {
       for(i=*t1;i>=0;i--)
        enqueue(stack2, &top2, size, s1[i]);
        //I've pasted the elements of first(actual Queue) stack into second stack, but did not deleted any value from it. But what i'll do is that, after pasting the
        //elements into second stack, considering that stack1 is becomeing empty, but actuall not.
        //I'll set stack pointer of first stack to -1 to make it empty and overwrite it with new values from second stack.
        printf("Dequeued element is: %d", stack2[top2]);// Dequeued element is same as s1[0];
        //now, for pop operation i've shifted top2 pointer of second stack down by one value.
        top2=top2-1;
        //Now, make stack pointer of first stack -1, to consider it empty;
        *t1=-1;top=-1;
        // *t1 and top here are having same value. And are the stack pointers of same s1 or stack1 stack.
        //But, You cannot pass here t1 as parameter, bcz it t1 is a pointer, but according to definition it should be variable whose address should be passed.
        // So, I declared top variable to pass as parameter. And wrote *t1=top, so that the actual top1 of stack1 from main function can get there value updated.
        for(i=top2;i>=0;i--){
        enqueue(s1, &top, size, stack2[i]);*t1=top;}
    }
}
void display(int stack[], int top)
{
    int i;
    if(top==-1)
        printf("Queue is empty.");
    else{
        printf("Queue is\nFront\n");
        for(i=0;i<=top;i++)
            printf("%d\n",stack[i]);
            printf("End");
    }
}
void peek(int stack[], int top)
{
    int i;
    if(top==-1)
        printf("Queue is empty.");
    else
        printf("Element at Front is: %d",stack[0]);
}
int main()
{
    int n,ch,choice=1,data;
    printf("Enter the size of Queue: ");
    scanf("%d",&n);
    int stack1[n];
    int top1=-1;
    while(choice==1){
    printf("\nEnter 1. to enqueue(insert in queue) \n");
    printf("Enter 2. to dequeue (to delete from queue)\n");
    printf("Enter 3. to display \n");
    printf("Enter 4. to peek (to show the element at front) \n choice: ");
    scanf("%d",&ch);
    if(ch==1)
    {
        if(top1!=n-1){
        printf("enter the data to be entered: ");
        scanf("%d",&data);
        enqueue(stack1,&top1,n,data);}
        else printf("Queue is full");
    }
    else if(ch==2)
        dequeue(stack1, &top1, n);
    else if(ch==3)
        display(stack1, top1);
    else if(ch==4)
        peek(stack1,top1);
    else
        printf("invalid choice:");
    printf("\nDo you want to continue(0,1): ");
    scanf("%d",&choice);
    }
}

Comments

Post a Comment

Popular posts from this blog

First_Come_First_Serve CPU Scheduling

-
#include<stdio.h> #include<conio.h> struct proc {     int id;     int burst;     int at; }; int main() {     int n,i,j,total_waiting_time,waiting_time;     printf("Enter the number of processess: ");     scanf("%d",&n);     struct proc p[n],temp;     f or(i=0;i<n;i++)     {         p[i].id=i;         printf("Enter the arrival time of the process: ");         scanf("%d",&p[i].at);         printf("Enter the burst time of the process: ");         scanf("%d",&p[i].burst);     }     for(i=0;i<n;i++)     {         for(j=i+1;j<n;j++)         {             if(p[j].at<p[i].at)             {                 ...
Read more

Reversing stack Method 2 !! (One Helper Stack only)

-
#include   <bits/stdc++.h> using   namespace   std ; stack < int >  rev ( stack < int >  s ) {      int   size  =  s . size (),  x ,  y ,  t ;      stack < int >  s2 ;      size  -=  1 ;      while  ( size --)     {          t  =  size  +  1 ;          x  =  s . top ();          s . pop ();          while  ( t --)         {              s2 . push ( s . top ());              s . pop ();         }  ...
Read more

Populating Next Right Pointers in Each Node in O(1) space (without queue and level order)

-
Image
Example 1: Input: root = [1,2,3,4,5,6,7] Output: [1,#,2,3,#,4,5,6,7,#] Explanation: Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level. Example 2: Input: root = [] Output: [] class Solution { public:     Node * connect ( Node * root )     {         Node * p1 = root , * p2 ;         while ( p1 != NULL )         {             p2 = p1 ;             while ( p2 != NULL )             {                 if ( p2 -> left )                     p2 -> left -> next = p2 -> right ;       ...
Read more

Calculate factorial of large numbers !! (Using Arrays)

-
#include   <bits/stdc++.h> using   namespace   std ; #define   max   10000 int   main () {      int   n ,  c ,  j ,  k ,  x ,  i ;      int   a [ max ];      cout   <<   "Enter the number: " ;      cin   >>   n ;      j  =  0 ;  // j will be pointing to new index created to stored carry      a [ 0 ] =  1 ;      for  ( i  =  2 ;  i  <=  n ;  i ++)     {          c  =  0 ;  //carry when each number of array is multiplied by i          //(i is a...
Read more

Multiplication of large numbers (Given in string format)

-
  class   Solution { public:      string   multiply ( string   num1 ,  string   num2 )     {          if  ( num1  ==  "0"  ||  num2  ==  "0" )              return   "0" ;          if  ( num1  ==  "1" )              return   num2 ;          if  ( num2  ==  "1" )              return   num1 ;          if  ( num1 . size () ==  1  &&  num2 . size () ==  1 )         {           ...
Read more

Left View of Binary Tree (Method 1 using recursion)

-
#include   <iostream> #include   <vector> using   namespace   std ; struct   TreeNode {      int   val ;      TreeNode  * left ;      TreeNode  * right ;      TreeNode () :  val ( 0 ),  left ( nullptr ),  right ( nullptr ) {}      TreeNode ( int   x ) :  val ( x ),  left ( nullptr ),  right ( nullptr ) {}      TreeNode ( int   x ,  TreeNode   * left ,  TreeNode   * right ) :                              val ( x ),  left ( left ),  right ( right ) {} }; TreeNode   * BuildTree () {      int   d ;      cin   >>   d ;      if  ( d  == -...
Read more

Check Bracket Sequence

-
#include<bits/stdc++.h> using namespace std; int main() {     int i,f,top=-1,size;     string s;     cin>>s;     size=s.size();     char a[size];     f=1;     for(i=0;i<s.size() && f==1;i++)     {         if(s[i]=='(')         a[++top]='(';         else if(s[i]==')')         {             if(top==-1)             f=0;             else             top-=1;         }     }     if(top!=-1 || f==0)     cout<<"invalid\n";     else     cout<<"Valid"; }
Read more

Image Multiplication

-
https://practice.geeksforgeeks.org/problems/image-multiplication0627/1 Input: 1 / \ 3 2 / \ / \ 7 6 5 4 / \ \ / \ \ 11 10 15 9 8 12 Output: 332 Explanation: Sum = (1*1) + (3*2) + (7*4) + (6*5) + (11*12) + (15*9) = 332 class Solution {     public:     void treeHelper ( Node * a , Node * b , long long int & ans )     {         if (a== NULL ||b== NULL )         return ;         long long int temp=( a -> data * b -> data )%( 1000000007 );         ans=(ans+temp)%( 1000000007 );         treeHelper ( a -> left , b -> right , ans);         treeHelper ( a -> right , b -> left , ans);     }   ...
Read more

Boundary Traversal of binary tree

-
struct Node {     int data;     Node * left, * right; }; class Solution { public:     void call_left ( vector < int > & v , Node * root )     {         if ( root == NULL )             return ;         if ( root ->left == NULL && root ->right == NULL )             return ; // don't push the leaf nodes.         v . push_back ( root ->data);         if ( root ->left)             call_left ( v , root ->left);         else             call_left ( v , root ->right);     }     void call_leaves ( vector < int > & v , Node * root )     {         if ( root == NULL )             return ;   ...
Read more

BST to greater sum tree

-
  // Input: //            2 //          /    \ //         1      6 //               /  \ //              3    7 // Output: 18 16 13 7 0 (InOrder) // Explanation: // Every node is replaced with the sum of nodes greater than itself. // The resultant tree is: //                16 //              /    \ //            18       7 //                   /   \ //                  13    0 //Bhaskar Varshney #include <iostream> #include <queue> using namespace std; struct TreeNode {     int val;     TreeNode *left;     TreeNode *rig...
Read more