Stacks on Stacks: A LIFO Love Story "PART 1"

"Why Being Last Can Be a Good Thing" - Implementation in C 📚

Jun 15, 2023

A stack is like a stack of pancakes. You can only add or remove pancakes from the top of the stack. If you want to add a pancake, you have to put it on top of the stack. If you want to remove a pancake, you have to take it from the top of the stack. Just like how you can't reach the bottom pancake without removing all the pancakes above it, you can't access the data in the middle of a stack without first removing all the data above it. So, if you're ever feeling hungry for some pancakes, just remember that a stack is the perfect way to organize them!

Stacks are used as a data structure because they provide a simple and efficient way to manage data that needs to be accessed in a specific order, known as a Last-In-First-Out (LIFO) order.

This means that the last item added to the stack is the first item that will be removed from it. This makes stacks useful for a wide variety of applications, such as managing function calls in a computer program, undoing actions in a text editor, or parsing expressions in a calculator.

Stacks are also efficient because they have a constant time complexity for adding or removing items from the top of the stack, making them a popular choice for many programming tasks.

Constant time O(1) is a term means that the time it takes to complete an operation does not increase as the size of the input grows. This is possible because the amount of work required to complete the operation is always the same, regardless of the size of the input.
Imagine you have a group of people standing in a line, and you want to ask the person in the middle of the line a question. This would take you a long time, because you would need to walk all the way to the middle of the line to ask the question.

Imagine you have a group of people standing in a line, and you want to ask the person in the middle of the line a question. This would take you a long time, because you would need to walk all the way to the middle of the line to ask the question.

Now, imagine instead that you have a group of people standing in a circle, and you want to ask the person standing directly in front of you a question. This would be much faster, because you only need to turn your head slightly to ask the question.

In this analogy, the line represents an operation with a time complexity of O(n), where n is the size of the input. The circle represents an operation with a time complexity of O(1), where the time it takes to execute the operation is constant, regardless of the size of the input.

So, when an algorithm or operation has a time complexity of O(1), it is like having a group of people standing in a circle, where the time it takes to perform the operation is always the same, no matter how many elements the operation needs to process.

One real-life technical scenario where a stack data structure is commonly used is in the implementation of a web browser's back button.
When a user navigates through different web pages, the browser stores the URLs of those pages in a stack. When the user clicks the back button, the browser pops the most recent URL from the stack and loads the corresponding web page.
This is a good example of a Last-In-First-Out (LIFO) data structure because the most recently visited web page is the one that the user is most likely to want to return to. The stack allows the browser to keep track of the user's browsing history in a way that is efficient and easy to manage.

Stacks in C → Can be created by:

Arrays.
Linked Lists

Array - implementation of stacks:

An array-based implementation of a stack is a common way to implement a stack data structure in computer programs. In this implementation, the stack is represented as an array, with a variable that keeps track of the index of the top of the stack. The elements of the stack are stored in the array, with the top of the stack being the last element added to the array.

Logic & main functions to manipulate Stack :

An array to store the elements of the stack, so declare a struct to represent the stack, with an array to store the elements and a variable top to keep track of the top of the stack📚

Check if the stack is empty, and check if the stack is full

Text within this block will maintain its original spacing when published

A check for overflow (addition to a filled array )in the push operation, so that the program can handle the error gracefully. When an attempt is made to push an element onto a stack that is already full, the program should display an error message to the user and terminate the operation, rather than attempting to add the element to the stack and causing an overflow, more comes after a while.

Push function, check if the stack is full. If it is, print an error message and return. Otherwise, increment the top of the stack by 1 and add the new element to the array at the new top position.
Pop ✂️ function, check if the stack is empty. If it is, print an error message and return. Otherwise, retrieve the element at the top of the stack, decrement the top of the stack by 1, and return the element.
Peek👀 function, check if the stack is empty. If it is, print an error message and return. Otherwise, retrieve the element at the top of the stack and return it.

In an array-based implementation of a stack, push and pop operations always take the same amount of time to execute, regardless of the number of elements in the stack. This is because pushing a new element onto the stack involves incrementing the top index and adding the element to the corresponding location in the array, and popping an element involves returning the element at the top index and decrementing the top index. These operations take a constant amount of time, making push and pop operations efficient for managing data in a stack.

Stack Overflow

Problem : In the context of an array-based implementation of a stack, overflow occurs when an attempt is made to add an element to a stack that has reached its maximum capacity. No more space in the array to store the new element, and attempting to add the element would result in overwriting other elements in the array. This can cause data loss, corruption of the stack, and other errors in the program.

Solution :

To prevent overflow, it's important to ensure that the array used to implement the stack has sufficient space to store all the elements that may be added to the stack. If the size of the stack is not known in advance, it may be necessary to use dynamic memory allocation to allocate additional space for the array as needed.

Both linked list and array-based implementations have their advantages and considerations when building a stack. Here are some factors to consider:

Dynamic Size: Linked lists have a dynamic size, meaning they can grow or shrink as needed. This can be beneficial if the stack size is unpredictable or varies significantly during runtime. Array-based implementations, on the other hand, have a fixed size defined during initialization.
Memory Allocation: Linked lists allocate memory dynamically for each node, as they are added or removed from the stack. This can be advantageous if memory usage needs to be optimized or if the stack size is unknown. Array-based implementations allocate a fixed block of memory for the entire stack upfront, which may be wasteful if the stack size is large but not fully utilized.
Random Access: Array-based implementations allow for constant-time random access to elements. This can be useful if you frequently need to access or modify elements at specific positions in the stack. Linked lists require traversing the list from the beginning to reach a specific element, resulting in linear time complexity for random access operations.
Efficiency: Array-based implementations typically have better cache locality, as the elements are stored consecutively in memory. This can lead to better performance due to fewer cache misses. Linked lists, on the other hand, may have more scattered memory access, resulting in potentially lower performance.
“cache locality : When a data element is accessed, not only is that specific element loaded into the cache, but also a "cache line" containing nearby memory locations.”

In summary, linked list-based implementations provide flexibility in terms of dynamic sizing and memory allocation, while array-based implementations offer constant-time random access and potential performance advantages due to cache locality. The choice between the two depends on the specific requirements and constraints of your application.

Linked List implementation of stacks in C

“Enforce behaviour of LIFO to Linked list to create the Stack “

Create same functions to manipulate it : push()- pop() - top() - isEmpty()”

Adding a new node at the beginning of a linked list is chosen over addition to tail (end) to build a stack for both the push and pop operations. When you add a new node at the beginning of the linked list, you update the reference to the new node, effectively making it the new top of the stack.

Here are a few reasons why adding a new node at the beginning of the linked list is advantageous for implementing a stack:

Constant Time Complexity: Adding a node at the beginning of a linked list takes constant time complexity, O(1). It doesn't depend on the size of the linked list since you only need to update the references of the new node and the previous top node.
No Traversal Required: Unlike adding a node at the end of a linked list, adding a node at the beginning doesn't require traversing the entire list to find the last node. This makes it more efficient and avoids unnecessary traversal operations.
Preserving LIFO Order: Adding a node at the beginning of the linked list ensures that the most recently added element becomes the top of the stack. This follows the Last-In-First-Out (LIFO) order characteristic of a stack.

It's worth noting that when using a linked list to implement a stack, you should always keep track of the reference to the top node. This allows easy access and manipulation of the top element without the need to traverse the entire linked list.

Functions implementation in stack:

https://ideone.com/KgVaZK

to be continued ….

Shaza’s Substack

Discussion about this post