nodes [while headnodes append (head datahead head next while nodes printnodes pop ()the time and space complexity are ( )where is the number of nodes in the list learn to recognize when the stack lifo property is applicable for exampleparsing typically benefits from stack consider augmenting the basic stack or queue data structure to support additional operationssuch as finding the maximum element table top tips for stacks know your stack libraries some of the problems require you to implement your own stack classfor othersuse the built-in list-type append(epushes an element onto the stack not much can go wrong with call to push [- will retrievebut does not removethe element at the top of the stack pop(will remove and return the element at the top of the stack len( = tests if the stack is empty when called on an empty list sboth [- and pop(raise an indexerror exception implement stack with max api design stack that includes max operationin addition to push and pop the max method should return the maximum value stored in the stack hintuse additional storage to track the maximum value solutionthe simplest way to implement max operation is to consider each element in the stacke by iterating through the underlying array for an array-based stack the time complexity is (nand the space complexity is ( )where is the number of elements currently in the stack the time complexity can be reduced to (log nusing auxiliary data structuresspecificallya heap or bstand hash table the space complexity increases to (nand the code is quite complex suppose we use single auxiliary variablemto record the element that is maximum in the stack updating on pushes is easym max(me)where is the element being pushed howeverupdating on pop is very time consuming if is the element being poppedwe have no way of knowing what the maximum remaining element isand are forced to consider all the remaining elements we can dramatically improve on the time complexity of popping by cachingin essencetrading time for space specificallyfor each entry in the stackwe cache the maximum stored at or below that entry now when we popwe evict the corresponding cached value