stack queue perm

perm.c

#include<stdio.h>
#define MAXSIZE 100
typedef struct {
	int arr[MAXSIZE];
	int top;
} stack;

typedef struct {
	 int front;
	 int rear;
	 int arr[MAXSIZE];
} queue;

//stack operations
void init_stack(stack* st) {
	st->top = -1;
}
int pop(stack* st) {
	if(st->top == -1) return -1;
	return st->arr[st->top--];
}
int peek(stack* st) {
	if(st->top == -1) return -1;
	return st->arr[st->top];
}
void push(stack* st, int element) {
	if(st->top == MAXSIZE - 1) return;
	st->arr[++st->top] = element;
}

//queue operations
void init_queue(queue* q) {
	q->front = -1;
	q->rear = -1;
}
int qempty(queue* q) {
	return q->front == q->rear && q->front == -1;
}
void add(queue* q, int element) {
	if(q->rear == MAXSIZE - 1) return;
	if(q->front == -1 && q->rear == -1) q->front = 0;
	q->arr[++q->rear] = element;
}
int qremove(queue* q) {
	if(q->front == -1) return -1; 
	int element = q->arr[q->front];
	q->front++;
	if(q->front > q->rear) { 
		q->front = -1;
		q->rear = -1;
	}
	return element;
}
int qpeek(queue* q) {
	if(q->front == -1) return -1; 
	return q->arr[q->front];
}
int main() {
	printf("Enter the value of n:\n");
	queue p, q, out;
	stack s;
	init_stack(&s);
	init_queue(&p);
	init_queue(&q);
	init_queue(&out);
	int n;
	scanf("%d", &n);
	printf("Enter the input permutation:\n");
	for(int i = 0; i < n; i++) {
		int k;
		scanf("%d", &k);
		add(&p, k);
	}
	printf("Enter the output permutation:\n");
	for(int i = 0; i < n; i++) {
			int k;
			scanf("%d", &k);
			add(&out, k);
	}
	
	//from this point we cannot call add to queue p anymore only we can call delete operations 
	while (!qempty(&out)) {
	    // Case 1: front of P matches front of Out
	    if (!qempty(&p) && qpeek(&p) == qpeek(&out)) {
	        add(&q, qremove(&p));
	        qremove(&out);
	    }
	    // Case 2: top of stack matches front of Out
	    else if (s.top != -1 && peek(&s) == qpeek(&out)) {
	        add(&q, pop(&s));
	        qremove(&out);
	    }
	    // Case 3: need to push from P into stack
	    else if (!qempty(&p)) {
	        push(&s, qremove(&p));
	    }
	    // Case 4: no move possible → not a valid permutation
	    else {
	        printf("Not possible. Exiting program.\n");
	        return -1;
	    }
	}
	printf("Final output:\n");
	while(!qempty(&q)) printf("%d ", qremove(&q));
	printf("\n");
	return 0;
}