Implement Queue ADT by Array
/*
Time limit: 5000ms
Memory limit: 256mb
---------------------Copy the following code, complete it and submit---------------------
I, <Your Full Name>, am submitting the assignment for
an individual project.
I declare that the assignment here submitted is original except for
source material explicitly acknowledged, the piece of work, or a part
of the piece of work has not been submitted for more than one purpose
(i.e. to satisfy the requirements in two different courses) without
declaration. I also acknowledge that I am aware of University policy
and regulations on honesty in academic work, and of the disciplinary
guidelines and procedures applicable to breaches of such policy and
regulations, as contained in the University website
http://www.cuhk.edu.hk/policy/academichonesty/.
It is also understood that assignments without a properly signed
declaration by the student concerned will not be graded by the
teacher(s).
*/
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
/**
* @brief The queue data structure, which is implemented by an array
* @note The queue can store at most `capacity - 1` elements
*/
struct queue {
int capacity;
int* arr;
int front;
int rear;
};
typedef struct queue* QueueADT;
// Functions prototypes for the queue
QueueADT createQueue(int capacity);
void deleteQueue(QueueADT q);
int isEmpty(QueueADT q);
int isFull(QueueADT q);
void enqueue(QueueADT q, int value);
int dequeue(QueueADT q);
int front(QueueADT q);
/**
* @brief Create a queue that can store at most `capacity` elements
* @param capacity the capacity of the queue
* @return the queue
* @note We set the capacity of the queue to be `capacity + 1` to store `capacity` elements
*/
QueueADT createQueue(int capacity) {
QueueADT q = (QueueADT)malloc(sizeof(struct queue));
q->arr = (int*)malloc((capacity + 1) * sizeof(int));
q->front = 0;
q->rear = 0;
q->capacity = capacity + 1;
return q;
}
/**
* @brief Delete the queue
* @param q the queue
*/
void deleteQueue(QueueADT q) {
free(q->arr);
free(q);
}
/**
* @brief Check if the queue is empty
* @param q the queue
* @return 1 if the queue is empty, 0 otherwise
*/
int isEmpty(QueueADT q) { return q->front == q->rear; }
/**
* @brief Check if the queue is full
* @param q the queue
* @return 1 if the queue is full, 0 otherwise
*/
int isFull(QueueADT q) { return (q->rear + 1) % q->capacity == q->front; }
/**
* @brief Add a value to the queue
* @param q the queue
* @note Make sure the queue is not full before calling this function
*/
void enqueue(QueueADT q, int value) {
// WRITE YOUR CODE HERE
}
/**
* @brief Remove a value from the queue
* @param q the queue
* @return the value removed from the queue
* @note Make sure the queue is not empty before calling this function
*/
int dequeue(QueueADT q) {
// WRITE YOUR CODE HERE
}
/**
* @brief Get the front value of the queue
* @param q the queue
* @return the front value of the queue
* @note Make sure the queue is not empty before calling this function
*/
int front(QueueADT q) {
// WRITE YOUR CODE HERE
}
// DO NOT MODIFY THE CODE BELOW
int main(void) {
int capacity;
scanf("%d", &capacity);
QueueADT q = createQueue(capacity);
int n;
scanf("%d", &n);
char str[20];
for (int i = 0; i < n; ++i) {
scanf("%s", str);
if (strcmp(str, "enqueue") == 0) {
int value;
scanf("%d", &value);
if (!isFull(q)) {
enqueue(q, value);
} else {
printf("full\n");
}
} else if (strcmp(str, "dequeue") == 0) {
if (!isEmpty(q)) {
printf("%d\n", dequeue(q));
} else {
printf("empty\n");
}
} else if (strcmp(str, "front") == 0) {
if (!isEmpty(q)) {
printf("%d\n", front(q));
} else {
printf("empty\n");
}
} else if (strcmp(str, "isEmpty") == 0) {
if (isEmpty(q)) {
printf("empty\n");
} else {
printf("not empty\n");
}
} else if (strcmp(str, "isFull") == 0) {
if (isFull(q)) {
printf("full\n");
} else {
printf("not full\n");
}
}
}
deleteQueue(q);
return 0;
}
---------------------------------------End of Code---------------------------------------
## Implement Queue ADT by Array
In this problem, you need to implement the queue ADT by array. The queue should support the following operations:
- `createQueue(int n)`: Create a new queue that can store at most `n` elements.
- `deleteQueue(QueueADT)`: Delete the queue and free all the memory used by it.
- `isEmpty(QueueADT)`: Return `true` if the queue is empty, `false` otherwise.
- `isFull(QueueADT)`: Return `true` if the queue is full, `false` otherwise.
- `enqueue(QueueADT, int value)`: Add an element `value` to the end of the queue.
- `dequeue(QueueADT)`: Remove and return the element at the front of the queue.
- `front(QueueADT)`: Return the element at the front of the queue without removing it.
Note that some of the operations have been implemented in the given code template. You need to implement the rest of the operations.
### Input
The first line of the input contains an integer $m\,(1 \leq m \leq 10000)$, the maximum number of elements that the queue can store.
The second line contains an integer $n\,(1 \leq n \leq 10000)$, the number of operations to perform.
The next $n$ lines, each of which contains an operation to perform.
### Output
Each line is the response to the operation.
### Example
**Input**
```
3
10
isEmpty
enqueue 1
enqueue 2
enqueue 3
enqueue 4
dequeue
isFull
front
enqueue 5
dequeue
```
**Output**
```
empty
full
1
not full
2
2
```
**Explanation**
initial queue: `[] [] []`
- `isEmpty`: print `empty`
- `enqueue 1`: `[1] [] []`
- `enqueue 2`: `[1] [2] []`
- `enqueue 3`: `[1] [2] [3]`
- `enqueue 4`: `[1] [2] [3]`, print `full` since the queue is full
- `dequeue`: `[2] [3] []`, print `1`
- `isFull`: `[2] [3] []`, print `not full`
- `front`: `[2] [3] []`, print `2`
- `enqueue 5`: `[2] [3] [5]`
- `dequeue`: `[3] [5] []`, print `2`
Submit