We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Here is a pure C solution. The standard C library doesn't include any pre-canned data structure implementations, so this solution includes a home-grown stack and queue implementation.
Approach
The main idea is to implement a queue (FIFO) using two stacks (LIFO) where each stack manages one end of the queue. The nifty part is that both stacks manage the same memory buffer. The 'rear' stack grows upward and is initially empty, whereas the 'front' stack grows downward and is initially full. Enqueue operations are only done on the 'rear' stack (i.e. push operations to an initially empty stack), and dequeue operations are only done to the 'front' stack (i.e. pop operations on a stack that is 'upside down' in memory and initially full).
Code
#include<stdio.h>#include<string.h>#include<math.h>#include<stdlib.h>#include<stdint.h>#include<errno.h>#include<stdbool.h>//#define DEBUG#ifdef DEBUG#define dbg_print(fmt, ...) fprintf(stderr, (fmt), __VA_ARGS__)#else#define dbg_print(fmt, ...)#endif/* * LIFO Stack Implementation. */typedefintstack_data_t;structstack{stack_data_t*elements;size_tsize;size_ttop;boolis_initialized;boolis_growing_up;};staticintstack_clear(structstack*stack){intstatus=EXIT_FAILURE;if(!stack||stack->size==0){status=-EINVAL;gotoout;}stack->top=0;dbg_print("stack %p: top is %lu.\n",stack,stack->top);status=EXIT_SUCCESS;out:returnstatus;}staticintstack_fill(structstack*stack){intstatus=EXIT_FAILURE;if(!stack||stack->size==0){status=-EINVAL;gotoout;}stack->top=stack->size;dbg_print("stack %p: top is %lu.\n",stack,stack->top);status=EXIT_SUCCESS;out:returnstatus;}voidstack_free(structstack*stack){if(!stack){return;}dbg_print("freeing stack %p.\n",stack);if(stack->is_initialized&&stack->elements){dbg_print("stack %p: freeing %p.\n",stack,stack->elements);free(stack->elements);}memset(stack,0,sizeof(*stack));}intstack_init(structstack*stack,size_tsize,boolis_growing_up){intstatus=EXIT_FAILURE;if(!stack||size==0){status=-EINVAL;gotoout;}stack->elements=calloc(size,sizeof(stack_data_t));if(!stack->elements){status=-ENOMEM;gotoout;}stack->size=size;stack->is_growing_up=is_growing_up;status=stack_clear(stack);if(status!=EXIT_SUCCESS){gotoout_free;}stack->is_initialized=true;status=EXIT_SUCCESS;out_free:if(status!=EXIT_SUCCESS){stack_free(stack);}out:returnstatus;}/* * NOTE: For safety purposes, an uninitialized stack * is treated as both full and empty. This maximizes * the likelihood that execution is directed to an * error path if stack_is_empty/full() is called * without first checking if the stack is initialized. */boolstack_is_full(conststructstack*stack){returnstack&&stack->is_initialized?stack->top==stack->size:true;}boolstack_is_empty(conststructstack*stack){returnstack&&stack->is_initialized?stack->top==0:true;}intstack_push(structstack*stack,intvalue){intstatus=EXIT_FAILURE;if(!stack){status=-EINVAL;gotoout;}if(!stack->is_initialized){status=-ENODATA;gotoout;}if(stack_is_full(stack)){status=-ENOBUFS;gotoout;}size_tindex=stack->is_growing_up?stack->top:stack->size-1-stack->top;stack->elements[index]=value;stack->top++;dbg_print("stack %p: top is %lu (%d).\n",stack,stack->top,stack->elements[index]);status=EXIT_SUCCESS;out:returnstatus;}intstack_pop(structstack*stack,int*value){intstatus=EXIT_FAILURE;if(!stack||!value){status=-EINVAL;gotoout;}if(!stack->is_initialized){status=-ENODATA;gotoout;}if(stack_is_empty(stack)){status=-ENOBUFS;gotoout;}stack->top--;size_tindex=stack->is_growing_up?stack->top:stack->size-1-stack->top;*value=stack->elements[index];dbg_print("stack %p: top is %lu (%d).\n",stack,stack->top,stack->elements[index]);status=EXIT_SUCCESS;out:returnstatus;}intstack_peek(conststructstack*stack,stack_data_t*value,size_tindex){intstatus=EXIT_FAILURE;if(!stack||!value){status=-EINVAL;gotoout;}if(!stack->is_initialized){status=-ENODATA;gotoout;}if(index>=stack->top){status=-ERANGE;gotoout;}*value=stack->is_growing_up?stack->elements[index]:stack->elements[stack->size-1-index];dbg_print("peek @ index %lu: %d\n",index,*value);status=EXIT_SUCCESS;out:returnstatus;}/* * FIFO Queue Implementation. */typedefstack_data_tqueue_data_t;structqueue{structstackfront;structstackrear;boolis_initialized;size_tcount;};intqueue_init(structqueue*q,size_tsize){intstatus=EXIT_FAILURE;if(!q||size==0){status=-EINVAL;gotoout;}/* The 'rear' stack is initially empty. */status=stack_init(&q->rear,size,true);if(status!=EXIT_SUCCESS){gotoout;}/* * The 'front' stack manages the same memory buffer * as the 'rear', but it grows in the opposite direction * and is treated as being initially full. */q->front.elements=q->rear.elements;q->front.size=q->rear.size;q->front.is_growing_up=!q->rear.is_growing_up;stack_fill(&q->front);q->front.is_initialized=true;q->count=0;q->is_initialized=true;status=EXIT_SUCCESS;out:returnstatus;}voidqueue_free(structqueue*q){if(!q){return;}if(q->is_initialized){/* * The front and rear stacks both manage the same * memory buffer, so we only need to free one of * them. */stack_free(&q->rear);}memset(q,0,sizeof(*q));}size_tqueue_count(conststructqueue*q){returnq&&q->is_initialized?q->count:0;}/* * NOTE: For safety purposes, an uninitialized queue * is treated as both full and empty. This maximizes * the likelihood that execution is directed to an * error path if queue_is_empty/full() is called * without first checking if the queue is initialized. */boolqueue_is_empty(conststructqueue*q){returnqueue_count(q)==0;}boolqueue_is_full(conststructqueue*q){returnqueue_count(q)==q->rear.size;}intqueue_enqueue(structqueue*q,queue_data_tvalue){intstatus=EXIT_FAILURE;if(!q){status=-EINVAL;gotoout;}if(!q->is_initialized){status=-ENODATA;gotoout;}if(queue_is_full(q)){status=-ENOBUFS;gotoout;}/* * As elements are enqueued and dequeued, the top of the * front and rear stacks will drift upward. To ensure * continuous operation, have the rear stack wrap * circularly when the end of the buffer is reached. * Note that this is done only after checking that there * is still empty space in the queue! */if(stack_is_full(&q->rear)){status=stack_clear(&q->rear);if(status!=EXIT_SUCCESS){gotoout;}}status=stack_push(&q->rear,value);if(status!=EXIT_SUCCESS){gotoout;}/* Check for counter overflow */if(q->count+1<q->count){status=-E2BIG;gotoout;}q->count++;out:returnstatus;}intqueue_dequeue(structqueue*q,queue_data_t*value){intstatus=EXIT_FAILURE;if(!q||!value){status=-EINVAL;gotoout;}if(!q->is_initialized){status=-ENODATA;gotoout;}if(queue_is_empty(q)){status=-ENOBUFS;gotoout;}/* * As elements are enqueued and dequeued, the top of the * front and rear stacks will drift upward. To ensure * continuous operation, have the front stack wrap * circularly when the end of the buffer is reached. * Note that this is done only after checking that there * are occupied spaces in the queue! */if(stack_is_empty(&q->front)){status=stack_fill(&q->front);if(status!=EXIT_SUCCESS){gotoout;}}status=stack_pop(&q->front,value);if(status!=EXIT_SUCCESS){gotoout;}/* Check for counter underflow */if(q->count-1>q->count){status=-E2BIG;gotoout;}q->count--;out:returnstatus;}intqueue_print_front(conststructqueue*q){intstatus=EXIT_FAILURE;stack_data_tfront=0;if(!q){status=-EINVAL;gotoout;}if(!q->is_initialized){status=-ENODATA;gotoout;}status=stack_peek(&q->front,&front,q->front.top-1);if(status!=EXIT_SUCCESS){gotoout;}dbg_print("front element is %d\n",front);printf("%d\n",front);status=EXIT_SUCCESS;out:returnstatus;}intread_int(int*value){intstatus=EXIT_FAILURE;if(!value){status=EINVAL;gotoout;}errno=0;intrc=scanf("%d",value);if(rc!=1){if(rc!=EOF){errno=rc;}perror("scanf");status=-errno;gotoout;}dbg_print("scanf read: %d\n",*value);status=EXIT_SUCCESS;out:returnstatus;}enumquery_type{QUERY_TYPE_INVALID=0,QUERY_TYPE_ENQUEUE=1,QUERY_TYPE_DEQUEUE=2,QUERY_TYPE_PRINT=3,QUERY_TYPE_LIMIT};intmain(){/* Enter your code here. Read input from STDIN. Print output to STDOUT */#define MIN_QUERIES 1#define MAX_QUERIES 100000#define MIN_Q_VALUE 1#define MAX_Q_VALUE 1000000000intstatus=EXIT_FAILURE;intqueries=0;structqueueq;/* Read the number of queries */status=read_int(&queries);if(status!=EXIT_SUCCESS){errno=-status;perror("read_int");gotoout;}if(queries<MIN_QUERIES||queries>MAX_QUERIES){fprintf(stderr,"Number of queries must be between %u and %u.\n",MIN_QUERIES,MAX_QUERIES);status=-ERANGE;gotoout;}/* Initialize the queue */status=queue_init(&q,queries);if(status!=EXIT_SUCCESS){errno=-status;perror("queue_init");gotoout;}/* Process each query */for(size_ti=0;i<queries;i++){enumquery_typequery=QUERY_TYPE_INVALID;intvalue=0;size_tcount=queue_count(&q);dbg_print("queue count is %lu.\n",count);/* Read the query type */status=read_int(&value);if(status!=EXIT_SUCCESS){errno=-status;perror("read_int");gotoout_free;}query=(enumquery_type)value;switch(query){caseQUERY_TYPE_ENQUEUE:/* Read the value to enqueue */status=read_int(&value);if(status!=EXIT_SUCCESS){errno=-status;perror("read_int");gotoout_free;}status=queue_enqueue(&q,value);if(status!=EXIT_SUCCESS){errno=-status;perror("queue_enqueue");gotoout_free;}break;caseQUERY_TYPE_DEQUEUE:status=queue_dequeue(&q,&value);if(status!=EXIT_SUCCESS){errno=-status;perror("queue_dequeue");gotoout_free;}break;caseQUERY_TYPE_PRINT:status=queue_print_front(&q);if(status!=EXIT_SUCCESS){errno=-status;perror("queue_print_front");gotoout_free;}break;default:fprintf(stderr,"Invalid query '%d'.\n",query);status=-EINVAL;gotoout_free;}}out_free:queue_free(&q);out:exit(status);}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Queue using Two Stacks
You are viewing a single comment's thread. Return to all comments →
Summary
Here is a pure C solution. The standard C library doesn't include any pre-canned data structure implementations, so this solution includes a home-grown stack and queue implementation.
Approach
The main idea is to implement a queue (FIFO) using two stacks (LIFO) where each stack manages one end of the queue. The nifty part is that both stacks manage the same memory buffer. The 'rear' stack grows upward and is initially empty, whereas the 'front' stack grows downward and is initially full. Enqueue operations are only done on the 'rear' stack (i.e. push operations to an initially empty stack), and dequeue operations are only done to the 'front' stack (i.e. pop operations on a stack that is 'upside down' in memory and initially full).
Code