Implement Stack using Queue

Problem Statement:

Implement a Stack using Queue.

Solution:

Utilize two Queues.
Use Q1 to push the elements.
Use Q2 as temporary, to store the  other elements while popping.

Code:

<ankzcode>

#include <stdio.h>
#include <malloc.h>

typedef struct __node {
    int data;
    struct __node *next;
    struct __node *prev;
}Node, *PNode;

typedef struct __q {
    PNode head;
    PNode tail;
    int   elemCount;
}Q, *PQ;

void enqueue(PQ q, int val)
{
    PNode node=NULL;
  
    if(q == NULL) { printf("Error: Q empty\n"); return;}

    node = (PNode) malloc (sizeof(Node));

    if(node==NULL) return;
  
    node->data =  val;
    node->next = NULL;
    node->prev = NULL;

    if(q->tail == NULL) {
        q->tail    = node;
        q->head    = node;
    } else {
        node->next = q->tail;
        q->tail->prev = node;
        q->tail = node;
    }
    q->elemCount++;
}

int dequeue(PQ q)
{
    int res = -1;
    PNode tmp;

    if((q == NULL) || (q->head == NULL)) return -1;
    res = q->head->data;
    tmp = q->head;
    q->head = tmp->prev;
    if(q->head != NULL) q->head->next = NULL;
    else q->tail = q->head;
    free(tmp);

    q->elemCount--;

    return res;
}

void initQ(PQ q)
{
    if(q == NULL) return;

    q->head = NULL;
    q->tail = NULL;
    q->elemCount=-1;
    return;
}

void displayQ(PQ q)
{
    PNode tmp = NULL;
    if(q == NULL) return;

    tmp = q->head;
    printf("Queue status: ");
    while( tmp ) {
          printf("%d ", tmp->data);
          tmp = tmp->prev;
    }
    printf("\n");
}

int testQ()
{
    Q q;

    initQ(&q);

    enqueue(&q,3);
    enqueue(&q,2);
    enqueue(&q,6);
    enqueue(&q,1);
    printf("%d\n", dequeue(&q));
    printf("%d\n", dequeue(&q));
    printf("%d\n", dequeue(&q));
    printf("%d\n", dequeue(&q));
  
    return 0;
}

typedef struct __s {
    PQ q1;
    PQ q2;
}S, *PS;

void initS(PS s)
{
    if(s == NULL) return;

    s->q1 = (PQ)malloc(sizeof(Q));
    s->q2 = (PQ)malloc(sizeof(Q));

    initQ(s->q1);
    initQ(s->q2);

    return;
}

void push(PS s, int val)
{
    if(s == NULL) return;
  
    enqueue(s->q1, val);  
}

int pop(PS s)
{
    PQ tmp = NULL;
    int res = -1;

    if((s == NULL) || (s->q1 == NULL)) return res;
    while(s->q1->elemCount > 0) {
        enqueue(s->q2, dequeue(s->q1));
    }

    res = dequeue(s->q1);

    tmp = s->q1;
    s->q1 = s->q2;
    s->q2 = tmp;
    return res;
}

int main()
{
    S s;

    initS(&s);

    printf("Pushing\n");
    push(&s, 3);
    push(&s, 2);
    push(&s, 6);
    push(&s, 1);
    displayQ(s.q1);

    printf("Poping\n");
    printf("%d\n", pop(&s));
    printf("%d\n", pop(&s));
    printf("%d\n", pop(&s));
    printf("%d\n", pop(&s));
    return 0;
}

</ankzcode>

Find the string in sequence/set 1 for corresponding index in set 2

Problem Statement:

Two sets S1 and S2 exists .
S1 represent a set of string such that
S1 = { a,b,c, ..., z, aa,ab,ac,..,az,ba,bb,bc,..,bz,...,yz,aaa,aab,... }

Now S2 represents an array of index, such that:
S2 = { 0,1,2,3,... }

Find the corresponding entry in S1 for corresponding index in S2.

Ex:

S2       S1
0   ---> a
1   ---> b
:
:
:
25 ---> z
26 ---> aa

Solution in C :

<ankzcode> 

#include <stdio.h>

#define SIZE 1000

int main()
{
    int N=26,n=1255;
    char stack[SIZE];
    int top=-1;

    scanf("%d", &n);

    short flag=0;

    // As the characters are received in reverse orde
    // Store the values in Stack (LIFO)
    do{
        // Need to subtract -1 from only the last
        stack[++top] = 'a' + ((n%N)+(flag?-1:0));
        n /= N;
        if(n<N)flag = 1;
    }while(n);

    while(top>=0) {
        printf("%c",stack[top--]);
    }
    printf("\n");
    return 0;
}

</ankzcode> 

Find the minimum without linear search / WAP to find the minimum value in an array using divide and conquer approach

Problem Statement

Find the minimum value in an array without linear search/
WAP to find the minimum value in an array using divide and conquer approach

Solution:

Approach is using divide and conquer.

Divide the array in smaller sub-sets of two.
Find the minimum of each sub-sets.

Finally compare and return the smallest/minimum value of the two largest sub-sets.

Code:

<ankzcode>

 #include <stdio.h>

int findMin(int a[], int l,int h)
{
    int pivot = (l + h) / 2;
    int minl=-1, minh = -1;

    if ( (pivot - l ) > 1) {
        minl = findMin(a, l, pivot);
    }
    else {
        minl = (a[l] > a[pivot])?a[pivot]:a[l];
    }
    if ( (h - pivot ) > 1) {
        minh = findMin(a, pivot, h);
    }
    else {
        minh = (a[l] > a[pivot])?a[pivot]:a[l];
    }

    return (minl>minh)?minh:minl;
}

int main()
{
    int a[]={5,2,9,10,3};
    printf("%d\n",findMin(a, 0, 5));
    return 0;
}

</ankzcode>