Question

Please Write Pseudocode or Python code! Thanks!

W1. (6 marks) Write the pseudocode for removing and returning only the second element from the Stack. The top element of the Stack will remain the top element after this operation. You may assume that the Stack contains at least two items before this operation. (a) Write the algorithm as a provider implementing a Stack using a contiguous memory implementation. You can refer to the implementation given in stack.py. Your implementation should directly access the fields of the Stack, specifically a contiguous array called _data, and and integer first that contains the first empty slot in _data. (b) Write the algorithm as a provider implementing a Stack using a linked implementation, such as your implementation for P1. b). Your implementation should directly access the fields of the Stack, specifically head that stored the first node in a linked list. (c) Write the algorithm as a user with the provided interface for Stack. You can only use the provided operations for the Stack.
P1. b) is the following:

Answer 1

W1.

(a) Pseudocode to remove and return the second element of the stack as a provider implementing a Stack using a contiguous memory allocation

# since _first contains the first empty slot in _data i.e the next element inserted will be in _first
# hence the last element inserted i.e the top element of the stack must be in _first-1 and second element will be in _first-2 since contiguous array is used
# get the second top element of the stack
second_element = self._data[self._first-2]

# move the top element of stack to the left by one position in order to delete the second top element from the stack
self._data[self._first-2] = self._data[self._first-1]

# make the previous index of top element an empty slot, i.e the next element will be inserted in this index
self._first = self._first-1

# return the second element of the stack
return second_element

(b) Pseudocode to remove and return the second element of the stack as a provider implementing a Stack using a linked implemention

# _head store the first node of the linked list i.e the top element of the Stack
# get the second top element of the stack
# _head stores the top element of the stack
# second element will be stored in node _head.next where next is the field that contains the next node of the stack
# item contains the data stored in the node
second_element = self._head.next.item

# remove the second element from the stack by making the node next to head point to node next to node next to head
# i.e the earlier third element of the stack(if exist, else it will be None)
self._head.next = self._head.next.next

# return the second element of the stack
return second_element

(c) Pseudocode to remove and return the second element of the stack as a user with the provided interface for Stack

# let stack be the object of the provided Stack class
# remove and get the top element of the stack
top_element = stack.pop()

# remove and get the second top element of the stack
second_element = stack.pop()

# push the initial top element back into the stack
stack.push(top_element)

# return the second element of the stack
return second_element