/*
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"
#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 stack {
int sum;
ListADT List;
};
typedef struct stack *StackADT;
StackADT createStack(void);
void deleteStack(StackADT stack);
int isEmpty(StackADT stack);
int isFull(StackADT stack);
void push(StackADT stack, int value);
int pop(StackADT stack);
int top(StackADT stack);
StackADT createStack(void) {
StackADT stack = (StackADT)malloc(sizeof(struct stack));
stack->sum = 0;
stack->List = createList();
return stack;
}
void deleteStack(StackADT stack) {
while (!isEmpty(stack)) {
pop(stack);
}
free(stack);
}
int isEmpty(StackADT stack) { return isEmptyList(stack->List); }
int isFull(StackADT stack) {
(void)stack;
return 0;
}
void push(StackADT stack, int value) {
// WRITE YOUR CODE HERE
}
int pop(StackADT stack) {
// WRITE YOUR CODE HERE
}
int top(StackADT stack) {
// WRITE YOUR CODE HERE
}
// DO NOT MODIFY THE CODE BELOW
int main(void) {
StackADT stack = createStack();
int n;
scanf("%d", &n);
char op[20];
for (int i = 0; i < n; ++i) {
scanf("%s", op);
if (strcmp(op, "push") == 0) {
int value;
scanf("%d", &value);
if (isFull(stack)) {
printf("full\n");
} else {
push(stack, value);
}
} else if (strcmp(op, "pop") == 0) {
if (isEmpty(stack)) {
printf("empty\n");
} else {
printf("%d\n", pop(stack));
}
} else if (strcmp(op, "isFull") == 0) {
if (isFull(stack)) {
printf("full\n");
} else {
printf("not full\n");
}
} else if (strcmp(op, "isEmpty") == 0) {
if (isEmpty(stack)) {
printf("empty\n");
} else {
printf("not empty\n");
}
} else if (strcmp(op, "top") == 0) {
if (isEmpty(stack)) {
printf("empty\n");
} else {
printf("%d\n", top(stack));
}
} else if (strcmp(op, "sum") == 0) {
printf("%d\n", stack->sum);
}
}
deleteStack(stack);
return 0;
}
---------------------------------------End of Code---------------------------------------
## Implement Stack ADT by Linked List
In this problem, you are required to first implement the list ADT. 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 are required to implement the stack ADT by leveraging the List ADT you have implemented. The stack should support the following operations:
- `createStack()`: Create a new stack.
- `deleteStack(StackADT)`: Delete the stack and free all the memory used by it.
- `isEmpty(StackADT)`: Return `true` if the stack is empty, `false` otherwise.
- `isFull(StackADT)`: Return `false` always.
- `push(StackADT, int value)`: Add an element `value` to the top of the stack.
- `pop(StackADT)`: Remove and return the element at the top of the stack.
- `top(StackADT)`: Return the element at the top of the stack without removing it.
- `sum(StackADT)`: Return the summation of all values in the stack.
Note that the stack is implemented by a linked list. So the capacity of a stack is unlimited and thus there is no parameter for the capacity to create a stack, and `isFull` will always return `false`.
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 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**
```
12
pop
push 1
push 2
isEmpty
push 3
pop
sum
push 4
isFull
pop
top
sum
```
**Output**
```
empty
not empty
3
3
not full
4
2
3
```
**Explanation**
initial stack: `[] [] [] ...`, which has unlimited capacity.
- `pop`: `[] [] [] ...`, print `empty`
- `push 1`: `[1] [] [] ...`
- `push 2`: `[1] [2] [] ...`
- `isEmpty`: `[1] [2] [] ...`, print `not empty`
- `push 3`: `[1] [2] [3] ...`
- `pop`: `[1] [2] [] ...`, print `3`
- `sum`: `[1] [2] [] ...`, print `3`
- `push 4`: `[1] [2] [4] ...`
- `isFull`: `[1] [2] [4] ...`, print `not full`
- `pop`: `[1] [2] [] ...`, print `4`
- `top`: `[1] [2] [] ...`, print `2`
- `sum`: `[1] [2] [] ...`, print `3`