Notes to Accompany Array Stack ImplementationThe handout you have includes three files:1) stack.h2) stack.c3) revword.cAs you might imagine, stack.h and stack.c go together. The firstprovides a list of the functions that pertain to using a stack. Note that I call my struct stackDT instead of stackADT as thetext has done. The reason for this is that in my implementationof a stack, the storage of the data is NOT hidden. Ideally, onecould look at the .h listing of the functions, not KNOW how thedata was stored, and still use all these functions. However, thisinformation can be ascertained by looking at stack.hNotice however, that all of these functions can be used withoutthe user directly manipulating the data. All manipulationsoccur through the functions outlined in stack.h. This is theessence of an abstract data type. It is one that the user doesNOT need to know the specific manner in which data is storedin order to use it effectively. Knowing how to use the structurecomes from understanding the functions that are provided tomanipulate it. All one has to understand is WHAT thefunctions do, not HOW they accomplish the feat.stack.hThis file contains the struct used to store a stack, a constantdefinition, and the function headers of all the functions thatwill operate on a stack. Each of these very closely mirrors thefunctions discussed in the text. My implementation storescharacters as can be seen by the Push function.Each function always takes in a stack by reference so thatchanges made to the stack in the function are reflected in thecalling function.Just using the information in stack.h, it is possible to write anew program that USES a stack without knowing exactly howthe functions pertaining to the stack were written.revword.cThis simple application reads in a word from the user, and thenuses a stack to aid it print out the word read in, in reverseorder. The characters of the input string are pushed onto astack created in the main function, one-by-one starting fromthe beginning of the string. Then, after these are all pushed onthe stack, each item gets popped off the stack, one-by-one andprinted out as they are popped. In order to do these tasks, thefollowing functions were necessary:NewStack, Push, Pop, StackIsEmptystack.cThe actual implementation of a stack using an array isn't toodifficult. Here are the components we need to store:1) The array storing the elements.2) An index to the top of the stack (actually the elementAFTER the top of the stack.) We'll assume the bottom of thestack is index 0, and go from there.When we create a new stack, we simply need to get space forthe object and then set top to 0, to indicate that the stack isempty.Quick Question: Why didn't we do this?struct stackDT s;s.top = 0;return &s;To push an element, we must simply copy it into the nextlocation for the top of the stack and then adjust top.To pop, we must save the value at the top of the stack,decrement top, and then return the saved element.The way I have implemented this stack, top is already thedepth of the stack.Checking to see whether the stack is full or empty is reasonablyeasy since top keeps track of the number of elements currentlyin a stack.How to Use Dynamically Allocated Arrays for StacksIn the implementation of a stack we discussed in class last time,we were forced to not allow more than 20 elements onto thestack. However, it's mostly likely that there would have beenmore memory available in the computer on which the programwas running. Furthermore, we already KNOW how todynamically allocate memory for an array.Thus, rather that saying that our stack is full when our arrayis, we can simply dynamically "grow" our array!Let's consider how we can do this:Given an array values that is already full and stores lengthnumber of elements, when we want to add newval to the end ofthe array, we can do the following:1) Dynamically create a new array temp, that has more spacethat values.2) Copy each element in values into temp, one by one.3) Add the new element that didn't fit in values into aremaining open slot in temp.4) Deallocate the memory for values.5) Assign the pointer values to temp.Here is a code segment that takes care of this task:int *temp = (int *)malloc((length+1)*sizeof(int));for (i=0; i<length; i++) temp[i] = values[i];temp[i] = newval;delete [] values;values = temp;This will work, but do you notice any potential weaknesseshere?What would happen if we had to add one more element intothis array?How much time would it take for each addition in terms of thetotal number of elements currently in the array?Clearly, if we just extend or "grow" the array by one elementeach time, we have LOTS of work in front of us for eachaddition into the array. Instead, here's a better strategy:Whenever you expand the array, double its size.It turns out that this rule leads to great performance in thelong run. Instead of adding an element taking O(n) time wheren is the total number of elements, adding an element takes O(1)on average.In order not to waste huge amounts of memory, it is alsoadvisable to "shrink" this type of array by half when the arrayis less than one quarter full. Once again, it can be shown thatthis procedure leads to efficient average case running times.These ideas can easily be incorporated into a stack class so thatthe size of the stack is not so limiting. Even so, a StackIsFullfunction is advisable since sometimes a malloc call may returnNULL.Linked List Implementation of a StackWe can essentially use a standard linked list to simulate astack, where a push is simply designated as inserting into thefront of the linked list, and a pop would be deleting the frontnode in a linked list.There are multiple ways to achieve this:1) Create just one struct for the stack which essentially actssimilar to the struct defined for use with linked lists.2) Use an existing linked list data structure, and simply borrowan instance of that, creating a new struct that has a pointer to alinked list as a component.In my example, I chose the former method. A good exercise foryou would be to see if you can adapt my code to work the otherway, using the linked list code we have already gone over.Some issues to think about when writing this