Implement Stack ADT by Linked List
/*
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"
#define DEFAULT_VALUE -1
struct stackNode {
int value;
struct stackNode *next;
struct stackNode *prev;
};
typedef struct stackNode *StackNode;
StackNode allocateEmptyStackNode(void) {
StackNode newNode = (StackNode)malloc(sizeof(struct stackNode));
newNode->value = DEFAULT_VALUE;
newNode->next = NULL;
newNode->prev = NULL;
return newNode;
}
void freeStackNode(StackNode node) { free(node); }
struct stack {
struct stackNode *tail;
struct stackNode *head;
};
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(StackADT));
// NULL <- head <-> tail -> NULL
stack->tail = allocateEmptyStackNode();
stack->head = allocateEmptyStackNode();
stack->tail->prev = stack->head;
stack->head->next = stack->tail;
return stack;
}
void deleteStack(StackADT stack) {
while (!isEmpty(stack)) {
pop(stack);
}
free(stack);
}
int isEmpty(StackADT stack) { return stack->tail->prev == stack->head; }
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));
}
}
}
deleteStack(stack);
return 0;
}
---------------------------------------End of Code---------------------------------------
## Implement Stack ADT by Linked List
In this problem, you need to implement the stack ADT by linked list. 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.
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 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**
```
10
pop
push 1
push 2
isEmpty
push 3
pop
push 4
isFull
pop
top
```
**Output**
```
empty
not empty
3
not full
4
2
```
**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`
- `push 4`: `[1] [2] [4] ...`
- `isFull`: `[1] [2] [4] ...`, print `not full`
- `pop`: `[1] [2] [] ...`, print `4`
- `top`: `[1] [2] [] ...`, print `2`
Submit