Problem (10 points).
In this problem you need to implement a Stack of Strings.
You must use a
ay implementation of the Stack and resize (double the capacity) the Stack when it’s full. Please check Demo version: https:
youtu.be/sc8p3rBY5pA
Requirements:
1. Please download and use main_template.txt template file from Assignment Dropbox. You must use the template file or you’ll receive zero grade.
2. You must only use stack_t data structure to implement the Stack of strings. You’ll get a zero grade if you use anything else.
3. Do NOT use scanf() , sscanf(), functions anywhere. You'll get -3 points if this requirement not met.
4. You must use fgets() function to get each string from the console. New line must be removed. Assume input won't exceed MAX_LEN – see MAX_LEN macros.
5. You must co
ectly allocate memory for each string on the HEAP based on the length of the string and push the string to the Stack.
6. You must co
ectly implement main Stack functions (lines XXXXXXXXXXin the template). If needed, you can add your own supplementary functions (See Hint N3).
7. You must implement resizeStack(..) that will double the capacity of the Stack when it’s full.
8. Your program must work similarly to the demo. Namely, the program should have the same input and output, ignore inco
ect input, etc.
9. Your solution should have optimal time and space complexity, check for possible e
or and free allocated memory that no longer needed (there should be no memory leak!)
Hints:
1. Check the Stack of integers implementation in Exercise 11.1 !
2. Stack of strings is essentially a Stack of pointers.
3. You might want to use extra function getStr() to get a string from console, allocate memory for it on the HEAP and return a pointer to memory block that you can then push to the Stack.
4. For resizeStack(..) function you’d need to use realloc() function.
5. Don’t forget to check if any memory allocation was successful.
6. Don’t forget to deallocate memory for each string after pop() function or you’ll have a memory leak.
7. Compilation warnings are considered to be major mistakes.
Final Exam, Winter2020 Template
You can add other li
aries if needed
#include
#include A structure to represent a stack
YOU MUST USE THIS STRUCTURE for Stack!
typedef struct {
int top;
size_t capacity;
char** a
ay;
} stack_t;
#define FLUSH stdin=freopen(NULL,"r",stdin)
The maximum length of the string in the input
#define MAX_LEN 20
Initial maximum size of the stack.
#define STACK_SIZE 2
function to create a stack of a given capacity.
stack_t* createStack(size_t);
* You need to implement the following functions:
Check if Stack is full
... isFull( .... );
Check if Stack is empty
... isEmpty( .... );
Function to add an item to stack.
... push( .... );
Function to remove an item from stack. It decreases top by 1
... pop( .... );
Function to return the top from stack without removing it
... peek( .... );
Function to resize the capacity of the Stack
... resizeStack( .... );
*
You might also declare and implement other functions here!
*
int main() {
stack_t* stack = createStack(STACK_SIZE);
printf("Created a Stack of size %zu.\n", stack->capacity);
/* Your code goes below:
*
printf("Cu
ently Stack has size %zu.\n", stack->capacity);
printf("Popping elements from stack:\n");
/* Your code goes below:
*
return 0;
}
Exercise 11.1
C program for a
ay implementation of stack
#include
#include A structure to represent a stack
typedef struct {
int top;
size_t capacity;
int* a
ay;
} stack_t;
#define MAX_SIZE 12
function to create a stack of given capacity.
It initializes size of stack as 0
stack_t* createStack(size_t);
Stack is full when top is equal to the last index
int isFull(stack_t*);
Stack is empty when top is equal to -1
int isEmpty(stack_t*);
Function to add an item to stack. It increases top by 1
void push(stack_t*, int);
Function to remove an item from stack. It decreases top by 1
int* pop(stack_t*);
Function to return the top from stack without removing it
int* peek(stack_t*);
int main() {
int i=0;
int a
ay[MAX_SIZE] = { 27, 14, 35, 10, 19, 31, 42, 55, 99 , 39, 36, 40 };
stack_t* stack = createStack(MAX_SIZE);
int* item;
item = peek(stack);
if (item) {
XXXXXXXXXXprintf("Top element of Stack: %d\n", *item);
}
else {
XXXXXXXXXXprintf("Top element of Stack: empty\n");
}
printf("Pushing elements to stack: ");
for (i=0; i XXXXXXXXXXpush(stack, a
ay[i]);
XXXXXXXXXXprintf("%d ", a
ay[i]);
}
putchar('\n');
item = peek(stack);
if (item) {
XXXXXXXXXXprintf("Top element of Stack: %d\n", *item);
}
else {
XXXXXXXXXXprintf("Top element of Stack: empty\n");
}
printf("Popping elements from stack: ");
while ( (item = pop(stack))!=NULL) {
XXXXXXXXXXprintf("%d ", *item);
}
putchar('\n');
return 0;
}
function to create a stack of given capacity.
It initializes size of stack as 0
stack_t* createStack(size_t capacity) {
stack_t* stack = (stack_t*)malloc(sizeof(stack_t));
if (stack == NULL) {
printf("Cannot allocate memory for stack!\n");
XXXXXXXXXXexit(-1);
}
stack->a
ay = (int*)malloc(capacity * sizeof(int));
if (stack->a
ay ==NULL) {
printf("Cannot allocate memory for %zu elements of the fixed stack!\n", stack->capacity);
XXXXXXXXXXexit(-1);
}
stack->capacity = capacity;
stack->top = -1;
return stack;
}
Stack is full when top is equal to the last index
int isFull(stack_t* stack) {
return stack->top == stack->capacity - 1;
}
Stack is empty when top is equal to -1
int isEmpty(stack_t* stack) {
return stack->top == -1;
}
Function to add an item to stack. It increases top by 1
void push(stack_t* stack, int item) {
if (!isFull(stack)) {
XXXXXXXXXXstack->a
ay[++stack->top] = item;
printf("%d pushed to stack\n", item);
}
}
Function to remove an item from stack. It decreases top by 1
We return NULL (stack is empty) or memory address of a
ay element
int* pop(stack_t* stack) {
return isEmpty(stack) ? NULL: &stack->a
ay[stack->top--];
}
Function to return the top from stack without removing it
int* peek(stack_t* stack) {
return isEmpty(stack)? NULL : &stack->a
ay[stack->top];
}