Why stack in convex hull

Question

I was reserarching about Convex hull and Graham Scan to implement it and It drew my attention that everyone has used stacks. So I wanted to ask why are the stacks used in the algoithm precisely, what's the benefit of using stacks?

Answer 1

In graham scan while constructing the hull there is a need of backtracking if the points do not form a left turn with the next considered points so previous points need to be reconsidered as valid points of hull hence we use stack to get them in order of last visited first for re-validation. Though is its not mandatory to use stack you can use a simple array as well to do the same.

Answer 2

The stack here can be considered as an abstract data structure that supports push, pop and empty operations. If you read the description of the Graham Scan algorithm you'll see that these are exactly the operations which the algorithm uses, so I really can't see what could be an alternative to a stack - it would probably be a different algorithm then.

What data structure is used to back/implement these operations in the stack (i. e. the class that implements stack interface in OO terms) can be decided rather freely. Often an array is used, but for some applications also linked lists might make sense.