/*
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"
struct deque {
// WRITE YOUR CODE HERE
};
typedef struct deque *DequeADT;
DequeADT createDequeue(int capacity);
void deleteDequeue(DequeADT deque);
int size(DequeADT deque);
int isEmpty(DequeADT deque);
int isFull(DequeADT deque);
int front(DequeADT deque);
int back(DequeADT deque);
void pushFront(DequeADT deque, int value);
void pushBack(DequeADT deque, int value);
int popFront(DequeADT deque);
int popBack(DequeADT deque);
/**
* @brief Create a deque, which can store at most `capacity` elements
* @param capacity the capacity of the deque
* @return the deque
*/
DequeADT createDequeue(int capacity) {
// WRITE YOUR CODE HERE
}
/**
* @brief Delete the deque
* @param deque the deque
*/
void deleteDequeue(DequeADT deque) {
// WRITE YOUR CODE HERE
}
/**
* @brief Get the number of elements in the deque
* @param deque the deque
* @return the number of elements in the deque
*/
int size(DequeADT deque) {
// WRITE YOUR CODE HERE
}
/**
* @brief Check if the deque is empty
* @param deque the deque
* @return 1 if the deque is empty, 0 otherwise
*/
int isEmpty(DequeADT deque) {
// WRITE YOUR CODE HERE
}
/**
* @brief Check if the deque is full
* @param deque the deque
* @return 1 if the deque is full, 0 otherwise
*/
int isFull(DequeADT deque) {
// WRITE YOUR CODE HERE
}
/**
* @brief Get the front value of the deque
* @param deque the deque
* @return the front value of the deque
* @note Make sure the deque is not empty before calling this function
*/
int front(DequeADT deque) {
// WRITE YOUR CODE HERE
}
/**
* @brief Get the back value of the deque
* @param deque the deque
* @return the back value of the deque
* @note Make sure the deque is not empty before calling this function
*/
int back(DequeADT deque) {
// WRITE YOUR CODE HERE
}
/**
* @brief Add a value to the front of the deque
* @param deque the deque
* @param value the value to be added
* @note Make sure the deque is not full before calling this function
*/
void pushFront(DequeADT deque, int value) {
// WRITE YOUR CODE HERE
}
/**
* @brief Add a value to the back of the deque
* @param deque the deque
* @param value the value to be added
* @note Make sure the deque is not full before calling this function
*/
void pushBack(DequeADT deque, int value) {
// WRITE YOUR CODE HERE
}
/**
* @brief Remove a value from the front of the deque, and return it
* @param deque the deque
* @return the value removed from the front of the deque
* @note Make sure the deque is not empty before calling this function
*/
int popFront(DequeADT deque) {
// WRITE YOUR CODE HERE
}
/**
* @brief Remove a value from the back of the deque, and return it
* @param deque the deque
* @return the value removed from the back of the deque
* @note Make sure the deque is not empty before calling this function
*/
int popBack(DequeADT deque) {
// WRITE YOUR CODE HERE
}
// DO NOT MODIFY THE CODE BELOW
int main(void) {
int capacity;
scanf("%d", &capacity);
DequeADT deque = createDequeue(capacity);
int n;
scanf("%d", &n);
char str[20];
for (int i = 0; i < n; ++i) {
scanf("%s", str);
if (strcmp(str, "push_front") == 0) {
int value;
scanf("%d", &value);
if (isFull(deque)) {
printf("full\n");
} else {
pushFront(deque, value);
}
} else if (strcmp(str, "push_back") == 0) {
int value;
scanf("%d", &value);
if (isFull(deque)) {
printf("full\n");
} else {
pushBack(deque, value);
}
} else if (strcmp(str, "pop_front") == 0) {
if (isEmpty(deque)) {
printf("empty\n");
} else {
printf("%d\n", popFront(deque));
}
} else if (strcmp(str, "pop_back") == 0) {
if (isEmpty(deque)) {
printf("empty\n");
} else {
printf("%d\n", popBack(deque));
}
} else if (strcmp(str, "front") == 0) {
if (isEmpty(deque)) {
printf("empty\n");
} else {
printf("%d\n", front(deque));
}
} else if (strcmp(str, "back") == 0) {
if (isEmpty(deque)) {
printf("empty\n");
} else {
printf("%d\n", back(deque));
}
} else if (strcmp(str, "size") == 0) {
printf("%d\n", size(deque));
} else if (strcmp(str, "isEmpty") == 0) {
if (isEmpty(deque)) {
printf("empty\n");
} else {
printf("not empty\n");
}
} else if (strcmp(str, "isFull") == 0) {
if (isFull(deque)) {
printf("full\n");
} else {
printf("not full\n");
}
}
}
deleteDequeue(deque);
return 0;
}
---------------------------------------End of Code---------------------------------------
## Implement Deque ADT
Deque (double-ended queue) is a data structure that supports insertion and deletion at both the front and the back of the queue, which is a generalization of the stack and the queue.
In this problem, you need to implement the deque ADT by any method you want. The deque should support the following operations:
- `createDeque(int n)`: create a new deque that can store at most `n` elements.
- `deleteDeque(DequeADT)`: delete the deque and free the memory.
- `isEmpty(DequeADT)`: check if the deque is empty.
- `isFull(DequeADT)`: check if the deque is full.
- `front(DequeADT)`: get the front element of the deque.
- `back(DequeADT)`: get the back element of the deque.
- `pushFront(DequeADT, int value)`: add `value` to the front of the deque.
- `pushBack(DequeADT, int value)`: add `value` to the back of the deque.
- `popFront(DequeADT)`: remove and return the front element of the deque.
- `popBack(DequeADT)`: remove and return the back element of the deque.
Note that whichever method you choose to implement the deque, you need to ensure that the time complexity of each operation is $O(1)$, and `isFull` returns `true` if and only if the deque has `n` elements. That means:
- if the deque is implemented by an array, the ring buffer may has a size of `n+1` to distinguish between `isEmpty` and `isFull`;
- if the deque is implemented by a linked list, you may need to maintain an extra value to store the size of the deque.
The code template that contains the function signatures and the main function is provided. You need to fill up the empty functions. You may refer the code template for the first two problems to implement the `createDeque` and `deleteDeque` functions. For `deleteDeque`, you can leave it empty if you don't need to free memory.
### 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
push_front 1
push_back 2
push_front 3
pop_front
front
back
push_back 4
size
push_back 5
pop_back
```
**Output**
```
3
1
2
3
full
4
```
**Explanation**
initial deque: `[] [] []`
- `push_front 1`: `[1] [] []`
- `push_back 2`: `[1] [2] []`
- `push_front 3`: `[3] [1] [2]`
- `pop_front`: `[1] [2] []`, print `3`
- `front`: `[1] [2] []`, print `1`
- `back`: `[1] [2] []`, print `2`
- `push_back 4`: `[1] [2] [4]`
- `size`: `[1] [2] [4]`, print `3`
- `push_back 5`: `[1] [2] [4]`, print `full`
- `pop_back`: `[1] [2] []`, print `4`