Data Structure - Stack

We have been looking into data structures in this series. First we looked at linked list, and then a specialization of it - the queue. The linked list can also be specialized to form a structure, that is called Stack.

The stack behaves - well, just like a stack of boxes. If queue were a first-in-first-out setup, then stacks have a 'first in, last out' or the FILO configuration. Nodes that are added in the beginning would be removed at the end after all other nodes that were added after it are removed.

As with the queue, these two operations are made to operate on the list in a certain way for it to be a stack.

• Push - or add node
• Pop - or retrieve node

When a node is added, it is added at the 'top' of the list. Also, when a node is poped, it is done so from the top. (In the context of stack, 'top' and 'bottom' are used instead of start and end of a list).

We can state the operations performed for pushing and popping a node in pseudo code.

Push

1. Create a new node
2. Set the data element to whatever is required
3. Set its reference node to the start of the list

Pop

1. Get the data from the starting node of the list
2. Set the start of the list as the second node
3. Destroy the first node from memory

The Stack Data Structure is used in a number of design patterns like parsing regular expressions, memory management, and problem solving.