/*
Time limit: 1000ms
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
*/
#define DEFAULT_VALUE -1
struct listNode {
int value;
struct listNode *next;
struct listNode *prev;
};
typedef struct listNode *ListNode;
ListNode allocateEmptyListNode(void) {
ListNode newNode = (ListNode)malloc(sizeof(struct listNode));
newNode->value = DEFAULT_VALUE;
newNode->next = NULL;
newNode->prev = NULL;
return newNode;
}
void freeListNode(ListNode node) { free(node); }
struct list {
struct listNode *head;
struct listNode *tail;
};
typedef struct list *ListADT;
ListADT createList(void);
void deleteList(ListADT list);
int isEmptyList(ListADT list);
void insertInPlace(ListADT list, ListNode p, int value);
void insert(ListADT list, int value);
void delete(ListADT list, ListNode p);
ListADT createList(void) {
ListADT list = (ListADT)malloc(sizeof(struct list));
list->head = allocateEmptyListNode();
list->tail = allocateEmptyListNode();
list->head->next = list->tail;
list->tail->prev = list->head;
return list;
}
int isEmptyList(ListADT list)
{
return list->head->next == list->tail;
}
void deleteList(ListADT list) {
while (isEmptyList(list) == 0) {
ListNode current = list->head->next;
list->head->next = current->next;
current->next->prev = list->head;
freeListNode(current);
}
freeListNode(list->head);
freeListNode(list->tail);
free(list);
}
void insertInPlace(ListADT list, ListNode p, int value)
{
// WRITE YOUR CODE HERE
}
void insert(ListADT list, int value)
{
// WRITE YOUR CODE HERE
}
void delete(ListADT list, ListNode p)
{
// WRITE YOUR CODE HERE
}
struct queue {
int size;
int AlternatingSum;
ListADT List;
};
typedef struct queue* QueueADT;
// Functions prototypes for the queue
QueueADT createQueue();
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);
int SizeofQueue(QueueADT q);
int AlternatingSumofQueue(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() {
QueueADT q = (QueueADT)malloc(sizeof(struct queue));
q->List = createList();
q->size = 0;
q->AlternatingSum = 0;
return q;
}
/**
* @brief Delete the queue
* @param q the queue
*/
void deleteQueue(QueueADT q) {
deleteList(q->List);
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 isEmptyList(q->List); }
/**
* @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->size < 0); }
/**
* @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
}
int SizeofQueue(QueueADT q) {
// WRITE YOUR CODE HERE
}
int AlternatingSumofQueue(QueueADT q) {
// WRITE YOUR CODE HERE
}
// DO NOT MODIFY THE CODE BELOW
int main(void) {
QueueADT q = createQueue();
int n;
scanf("%d", &n);
char str[30];
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");
}
} else if (strcmp(str, "size") == 0) {
printf("%d\n", SizeofQueue(q));
} else if (strcmp(str, "alternatingsum") == 0) {
printf("%d\n", AlternatingSumofQueue(q));
}
}
deleteQueue(q);
return 0;
}
---------------------------------------End of Code---------------------------------------
## Implement a Queue ADT by Linked List
In this problem, you are required to first implement the list ADT, which is the same as problem 1. The list should support the following operations:
- `createList()`: Create an empty list.
- `deleteList(ListADT)`: Delete the list and free all the memory used by it.
- `isEmptyList(ListADT)`: Return `true` if the list is empty, `false` otherwise.
- `insert(ListADT, int value)`: add element `value` to the end of the list.
- `insertInPlace(ListADT, node p, int value)`: add element `value` after node `p` stored in the list.
- `delete(ListADT, node p)`: delete node `p` from the list.
Next, you need to implement the queue ADT by applying the List ADT you have implemented. The queue should support the following operations:
- `createQueue()`: Create a new queue.
- `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.
- `SizeofQueue(QueueADT)`: Output the number of elements in the queue.
- `AlternatingSum(QueueADT)`: Compute the alternating sum of elements in the queue: $q_1 - q_2 + q_3 - q_4 + \dots$, where $q_1$ is the front element, $q_2$ is the next element, and so on until the rear of the queue.
Note that some of the operations have been implemented in the given code template. You need to implement the rest of the operations.
Note that the queue is implemented by a linked list. So the capacity of a queue is unlimited and thus there is no parameter for the capacity to create a queue, and `isFull` will always return `false`.
### Input
The first line contains an integer $n\,(1 \leq n \leq 300000)$, 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**
```
13
isEmpty
enqueue 1
enqueue 2
enqueue 3
enqueue 4
alternatingsum
dequeue
isFull
front
enqueue 5
size
dequeue
alternatingsum
```
**Output**
```
empty
-2
1
not full
2
4
2
4
```
**Explanation**
initial queue: `[] [] [] ...`, which has unlimited capacity.
- `isEmpty`: print `empty`
- `enqueue 1`: `[1] [] [] ...`
- `enqueue 2`: `[1] [2] [] ...`
- `enqueue 3`: `[1] [2] [3] ...`
- `enqueue 4`: `[1] [2] [3] [4] ...`
- `alternatingsum`: `[1] [2] [3] [4] ...`, print `-2`
- `dequeue`: `[2] [3] [4] ...`, print `1`
- `isFull`: `[2] [3] [4] ...`, print `not full`
- `front`: `[2] [3] [4] ...`, print `2`
- `enqueue 5`: `[2] [3] [4] [5] ...`
- `size`: `[2] [3] [4] [5] ...`， print `4`
- `dequeue`: `[3] [4] [5] ...`, print `2`
- `alternatingsum`: `[3] [4] [5] ...`, print `4`