7. (3 points) We can use a linked list to implement a stack. We assume that we use structure Node with
two rembers to represent a node of the linked list. The member data stores the data, and the rnernber
next points to the next node in the linked list. Also we use a variable bead to point to the first node of
the linked list. head is initialized to NULL.
1. Pushing the value of a variable i into the stack can be implemented as follows.
newHead = malloc(sizeof (Node));
newHead-＞data - i;
newHead-＞next = = head;
head = newHead;
2. Popping the top of the stack into a variable i can be implemented as follows.
free(head) ;
head-＞data ;
head = = head-＞next ;
3.To test if the stack is empty we can check if the head is a NULL pointer.
4. We can improve the push/pop effciency of this stack by adding another pointer tail that points
to the end of the linked list, so we can access the Last node in the list in O(1) time.
5. We can improve the push/pop eficiency of this stack by adding another pointer member into every
node, so it becomes a double linked list. That is, we can traverse in both directions in this linked
阿摩線上測驗
登入