Question

In the linked-list version of the Stack class, which operations require linear time for their worst-case behavior?

		is_empty()
		push()
		pop()
		None of these operations require linear time.

Answer 1

The answer is "None of these operations require linear time".

is_empty():

This method checks if the stack has any elements in it.

It can be directly found using the top pointer.

If it is NULL, then stack is empty.

This does not require linear time. It takes constant time.

push():

This method pushes the element to stack.

Here, it adds the node to the linked list.

This does not need linear time because a new node can be created and using the top node, the newly created node can be added to the top node.

This makes the top point point to the currently pushed node.

pop():

This operation removes the top node.

This takes constant time.

The top can be set to the previous node and the links can be modified.

The memory can be released using free().

So, these three operations does not require linear time in any case.