program must be in c part ii a automatic resizing of a stack plus a clone function y 5153520
PROGRAM MUST BE IN C!!
Part II-A – automatic resizing of a Stack plus a clone function.
You have already seen an implementation of a stack module in C. This module follows the principles of an Abstract Data Type by separating its interface — the operations that a client of the stack is able to perform on it — from the implementation of those operations.
The interface was specified in a .h file and a particular implementation was written in a .c file.
There is a weakness in the implementation you studied: the maximum number of entries a stack can hold must be a constant that is known at compile time. However, it is not uncommon for application programs to only know the size of stack (or other “container”) it will need until runtime; even worse, the needed size might not even be known when a stack is created (dynamically) within a program!
Your assignment:
(1) Modify the stack.c implementation file to make it fully dynamic. The underlying implementation will still be (effectively) an array (really a pointer), but if a push operation would exceed the size of this array, you dynamically create a new array of twice the size! You continue with this new array representing the stack contents.
Details here are up to you. But one thing to remember is to deallocate (using free) any previously allocated memory that will no longer be used.
Some things to consider:
In your new implementation, what should stk_is_full return?
Remember, you can change contents of stack_struct to fit the new implementation.
You cannot change the function declarations as specified in stack.h
(2) You may notice that stack.h has a function prototype: stk_clone. Your second task is to implement this function (in stack.c). It takes an existing stack as a parameter and returns a new stack with exactly the same contents.
CHECKLIST:
|
Code you will need to Modify |
|
|
the specification of stack_struct |
|
|
stk_create |
|
|
stk_push |
|
|
stk_clone (write from scratch) |
|
|
stk_free |
|
|
stk_is_full |
|
Comments: remember that dynamic memory allocation is done through the library function malloc which takes as a parameter the number of bytes the caller is requesting and returns a pointer to the base address of a contiguous block of memory of that size. A simple example to allocate a block of memory to be used as an array of n integers:
|
int main(int argc, char *argv[]) { int n, i; int *a; n = atoi(argv[1]); // no error checking… // the point here is that we do not know // the value of n at compile time. a = malloc(n*sizeof(int)); for(i=0; i a[i] = 0; // note we can use array indexing operator! // do some other stuff with a[] // now I’m done with a[] free(a); // do whatever else the program is supposed to do. } |