How to Implement a Stack using Arrays and Linked Lists

A Stack follows the Last In First Out principle, meaning the last element pushed onto the stack is the first one to be removed. Think of a stack of plates. You always add to the top and remove from the top.

In the array approach, maintain a variable called TOP that tracks the index of the topmost element. To push, first check if the stack is full by comparing TOP to the maximum capacity. If not full, increment TOP by one and place the new element at that index.

To pop, first check if TOP is at negative one, which means the stack is empty. If empty, report an underflow error. If not empty, retrieve the element at index TOP, then decrement TOP by one. The element is now logically removed.

In the linked list approach, the HEAD of the list represents the top of the stack. To push, create a new node with the given value. Set the new node's next pointer to the current HEAD. Then update HEAD to point to the new node. The new element is now on top.

To pop using a linked list, first check if HEAD is NULL which means the stack is empty. If not empty, save the value at HEAD. Move HEAD to HEAD.next. The old top node is now disconnected and can be discarded. Return the saved value.

Peek returns the top element without removing it. In the array approach, return the element at index TOP. In the linked list approach, return the value of HEAD. The isEmpty operation simply checks if TOP equals negative one for arrays or if HEAD equals NULL for linked lists.

The array approach has a fixed size and can overflow. The linked list approach is dynamic and grows as needed but uses extra memory for pointers. Both give constant time performance for push, pop, and peek operations.