Question

Write a program to implement the following algorithm:
 Start with two indexes one at the left and other at the right end of the array.
 Left index simulate the first stack and second index simulate the right stack.
 If we want to put the element in the first stack then put the element at the left index.
Similarly, if we want to put the element in the second stack then put the element at the
right index.
 First stack grow towards left and second stack grow towards left.

Answer 1

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

struct stacks {
    int* data;
    int size;
    int i1, i2;
};
typedef struct stacks TwoStacks;
void InitStacks(TwoStacks* st, int size) {
    st->data = (int *) malloc(size * sizeof(int));
    st->size = size;
    st->i1 = 0;
    st->i2 = size-1;
}

void FreeStacks(TwoStacks* st) {
    free(st->data);
    st->data = NULL;
}

void Push1(TwoStacks* st, int x) {
    if ( st->i1 > st->i2 ) {
        fprintf(stderr, "Error: stacks are full\n");
        return;
    }
    st->data[st->i1++] = x;
}

void Push2(TwoStacks* st, int x) {
    if ( st->i1 > st->i2 ) {
        fprintf(stderr, "Error: stacks are full\n");
        return;
    }
    st->data[st->i2--] = x;
}


int Pop1(TwoStacks* st)
{
    if (st->i1 == 0) {
        fprintf(stderr, "Error: stack1 is empty\n");
        return 0;
    }
    return st->data[--st->i1];
}

int Pop2(TwoStacks* st)
{
    if (st->i2 == st->size-1) {
        fprintf(stderr, "Error: stack2 is empty\n");
        return 0;
    }
    return st->data[++st->i2];
}

int IsFull(TwoStacks* st)
{
    return st->i1 > st->i2;
}
int IsEmpty1(TwoStacks* st)
{
    return st->i1 == 0;
}
int IsEmpty2(TwoStacks* st)
{
    return st->i2 == st->size-1;
}

int main() {
    TwoStacks st;
    int data[] = { 1, 2, 3, 4, 5};
    int n = sizeof(data)/sizeof(data[0]);
    int x, i;

    InitStacks(&st, 10);
    for (i=0; i<n; i++) {
        printf("Pushing %d\n", data[i]);
        Push1(&st, data[i]);
    }

    while (!IsEmpty1(&st)) {
        x = Pop1(&st);
        Push2(&st, x);
        printf("%d was poped from first stack and pushed into second one\n", x);
    }

    printf("\nNow poping stack 2:\n");
    while (!IsEmpty2(&st) ) {
        x = Pop2(&st);
        printf("%d ", x);
    }

    printf("Have a nice day!\n");
    return 0;
}