Last active
April 27, 2019 22:40
-
-
Save weidagang/4655084 to your computer and use it in GitHub Desktop.
Problem: Implement a circular queue of integers of user-specified size using a simple array. Provide routines to initialize(), enqueue() and dequeue() the queue. Make it thread safe. Please implement this with your own code and do not use any class libraries or library calls.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
Problem | |
Implement a circular queue of integers of user-specified size using a simple array. | |
Provide routines to initialize(), enqueue() and dequeue() the queue. Make it thread safe. | |
Please implement this with your own code and do not use any class libraries or library calls. | |
*/ | |
#include <malloc.h> | |
#define OK 0 | |
#define ERROR -1 | |
struct _Queue { | |
int capacity; | |
int head; | |
int tail; | |
int *buffer; | |
}; | |
typedef struct _Queue Queue; | |
/* interface */ | |
Queue* initialize(unsigned int capacity); | |
int destroy(Queue* queue); | |
int enqueue(Queue* queue, int element); | |
int dequeue(Queue* queue, int *out_element); | |
int size(Queue* queue); | |
/* implementation */ | |
Queue* initialize(unsigned int capacity) { | |
Queue* queue = (Queue*)malloc(sizeof(Queue)); | |
if (NULL == queue) { | |
return NULL; | |
} | |
queue->capacity = capacity; | |
queue->head = 0; | |
queue->tail = 0; | |
queue->buffer = (int*)malloc(sizeof(int) * (1 + capacity)); | |
if (NULL == queue->buffer) { | |
free(queue); | |
return NULL; | |
} | |
return queue; | |
} | |
int destroy(Queue *queue) { | |
free(queue->buffer); | |
free(queue); | |
return OK; | |
} | |
int enqueue(Queue *queue, int element) { | |
if (size(queue) >= queue->capacity) { | |
return ERROR; | |
} | |
queue->buffer[queue->tail] = element; | |
queue->tail = (queue->tail + 1) % (queue->capacity + 1); | |
return OK; | |
} | |
int dequeue(Queue *queue, int *out_element) { | |
if (size(queue) <= 0) { | |
return ERROR; | |
} | |
*out_element = queue->buffer[queue->head]; | |
queue->head = (queue->head + 1) % (queue->capacity + 1); | |
return OK; | |
} | |
int size(Queue *queue) { | |
return (queue->tail - queue->head + (1 + queue->capacity)) % (1 + queue->capacity); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment