Stack in Data Structures

Introduction to Stack in Data Structures.

Introduction to Stack in Data Structures

It has been a while since we started this DSA course. We have explored the array ADT, linked lists, and their variants, along with their implementations and operations. From this tutorial onwards, we will begin learning about stack data structures.

Introduction:

A stack is a linear data structure where any operation is performed in LIFO (Last In First Out) order. This means that the element that enters the container last will be the first one to leave. It is essential that elements above a specific element in a stack must be removed first before accessing that element.

Think of a stack as a basket-type container. Just like any basket, our stack has a limit. Elements can only be pushed into the stack until it reaches its capacity. Attempting to push more elements than the limit results in a condition known as stack overflow.

Applications of Stack:

A function reserves space in the memory stack until it returns. Any function called within another function is placed above the parent function in the stack. Therefore, the embedded function completes first, followed by the parent function. This illustrates the LIFO principle, where the function called last ends first.
Infix to postfix conversion (and other similar conversions) will be explored in the upcoming tutorials.
Parenthesis matching and many more applications...

Stack ADT:

To create a stack, we need a pointer to the topmost element to keep track of which element is currently at the top. This allows us to perform various operations efficiently. Additionally, we require space for other elements to be stored along with their data.

Here are some basic operations we typically perform on stacks:

push( ): To push an element onto the stack.
pop( ): To remove the topmost element from the stack.

peek(index): To return the value at a given index.
isempty() / isfull(): To determine whether the stack is empty or full, enabling efficient push and pop operations.

Implementation:

A stack can be implemented using both arrays and linked lists. We’ll explore both methods in the upcoming tutorials.

A stack is a collection of elements with specific operations that follow the LIFO (Last In First Out) discipline. Remember this principle as we delve into all aspects of stacks, starting from the basics.

Implementing Stack Using Array in Data Structures

In the last tutorial, we covered the stack data structure and its applications in various programming scenarios. We also discussed some operations possible on a stack. Today, we’ll implement these concepts using arrays, although linked lists are also an option.

Recall that a stack is a collection of elements that follows the LIFO (Last In First Out) principle. The element that gets pushed last is the first one to be removed from the stack.

Stack Using an Array

Arrays are linear data structures where elements are indexed, allowing constant time access to elements via their index. To implement a stack using an array, we will maintain a variable that stores the index of the top element.

So, when implementing stacks using arrays, there are a few key considerations to keep in mind:

A fixed-size array: The size can be larger than the expected size of the stack to ensure we have enough space.
An integer variable to store the index of the top element: This variable represents the last element added to the array. It is set to -1 when the stack is empty.

We will create a structure to encapsulate all these functionalities. Let’s explore how to do this.

struct stack{
    int size;
    int top;
    int* arr;
}

The struct we created includes members for the size of the array, the index of the top element, and a pointer to the array.

To use this struct:

Declare a variable of type struct stack.
Set the top element to -1.
Reserve memory in the heap using malloc.

Here is an example of how to define a stack:

    struct stack S;
    S.size = 80;
    S.top = -1;
    S.arr = (int*)malloc(S.size*sizeof(int));

We have used an integer array above, although it is just for the sake of simplicity. You have the freedom to customize your data types according to your needs.

We can now move on to implementing the stack ADT, particularly their operations. Here are the operations we will cover:

push( )

By pushing, we mean inserting an element at the top of the stack. While using arrays, we have the index to the top element of the array. So, we’ll insert the new element at the index (top + 1) and increase the top by 1. This operation takes constant time, O(1). It’s important to note that this operation is valid as long as (top + 1) is a valid index and the array has available space.

pop( )

Pop means to remove the last element entered in the stack, which is located at the index top. This operation is straightforward; we simply decrease the value of top by 1, and we are done. The popped element can be used as needed.

Doubly Linked Lists

Implementing Stack Using Array