Stack ADT Implementation: Static vs Dynamic Representations

Static Representation of a Stack ADT

In which case will we use a static representation of a Stack ADT?

We use this when the size of all the stacks we need in our application is the same. The static representation requires knowing the maximum size at compile time; that is, knowing in advance the number of items that the stacks used in this application will contain.

Pseudostatic Representation of a Stack ADT

When should we use a pseudostatic representation of a Stack ADT?

This is used when it is convenient to utilize stacks of different sizes within a program. In this representation, the maximum size of a stack is not the same for all stacks and is set at runtime when it is created. The user will be asked for the size of the stack at the time of creation, but this size remains fixed throughout the lifetime of the stack.

Dynamic Representation of a Stack ADT

When do you use a dynamic representation of a Stack ADT?

We use it when we do not know in advance the number of items a stack could have. In this case, the size of the stacks created in our application is variable, allowing them to increase or decrease in size as needed at runtime.

Pointers in Dynamic Stack Representations

Why is a stack represented as a pointer to the designed data structures in a dynamic representation?

The reason for introducing a pointer is to ensure that passing parameters to the operations of the TAD (Abstract Data Type) is done by reference. This ensures that changes made to the formal parameters are reflected in the actual parameters.

Passing Stack Registers by Reference

Why is the register representing the stack passed by reference in static or pseudostatic representations, even when not strictly required?

This is done because of the principle of independence of representation. One way to achieve this is to define a pointer to the designed data structures. This results in two distinct advantages:

• Transparency: Passing by reference is hidden from the implementation of the TAD and is transparent to the user.
• Memory Efficiency: You save memory by avoiding duplicate data while running a function. When you run a function call, parameter passing by value is always performed, which causes the actual parameters to be copied to the formal ones. By defining the stack type as a pointer to the record that represents the stack, the system only makes a copy of this pointer and not the full record.