Stack in Data Structure

A stack in data structure, following the Last In First Out (LIFO) principle, is a crucial linear data structure for sequential task completion. Imagine entering a crowded elevator last and exiting first; this mirrors stack behavior. Understanding this, we'll explore the formal definition of a stack data structure in C++.

Some Key Points Related to Stack Data Structure

• Stacks are dynamic in nature; this means that they do not have a fixed size and their size can be increased or decreased depending upon the number of elements.
• In stacks, only one end is available to perform actions like insertion or deletion of the elements
• Stacks follow LIFO, which is Last In, First Out mechanism. Inserting an element is known as push, and deleting an element is known as pop

Working of Stack in Data Structure

Stack in data structure are essential linear data structures that adhere to the Last-In-First-Out (LIFO) principle, meaning the most recently added element is the first one to be removed. This structure is akin to a stack of plates, where only the top plate is accessible for removal or addition of a new plate.

Consider a stack with a capacity for 5 elements. Initially, this stack is empty:

Elements are added (pushed) to the stack sequentially. For instance, adding the elements 1, 2, 3, 4, and 5 fills the stack from bottom to top, with 5 being the last element added and positioned at the top:

This process demonstrates the stack's capacity limit, in this case, 5. Once it reaches its capacity, no further elements can be added unless some are removed.

Removal (popping) of elements from the stack occurs from the top, in reverse order of their addition. After one pop operation, the stack that previously held 5 elements will have 4, with the last element (5) removed:

This behavior exemplifies the LIFO mechanism, where the stack allows both addition (push) and removal (pop) of elements from its top, adhering to its predefined capacity.

Standard Stack Operations in Data Structure

Standard stack operations facilitate interaction with this LIFO (Last-In-First-Out) data structure, each performing a specific function:

• Push: It adds an element to the top , increasing its size by one.
• Pop: It removes the element from the top, decreasing its size by one and returning the removed element.
• Peek or Top: Retrieves the top element of the stack without removing it, allowing a look at the value without modifying the stack.
• IsEmpty: Checks if the stack is empty, returning true if there are no elements and false otherwise.
• IsFull: (In the context of a fixed-size stack) Checks if the stack has reached its maximum capacity, returning true if no more elements can be added.
• Size: It returns the number of elements/ size of the stack, providing a count of how many items are stored.

Push Operation

The process of inserting new data into a stack is known as push. The push (x) operation takes the element to be added as a parameter

The steps involved in a push operation are –

1. Before inserting the element, check whether the stack is full.
2. If the stack is full, print “stack overflow” and terminate the program.
3. If the stack is not full, add data into the stack.
4. We can repeat the above steps until the maximum capacity of the stack is achieved.
   Recall the above example of the elevator, the event of people walking into the elevator closely relates to pushing the elements into a stack.

POP Operation

The process of deleting the topmost element from the stack is known as pop.

The steps involved in a pop operation are –

1. Before removing the topmost element, check whether the stack is empty
2. If the stack is empty, print “Stack underflow” and terminate the program
3. If the stack is not empty, access the topmost element and let the top point to the element just before it
4. We can repeat the above until all the elements from the stack are removed

In the example of the elevator, a person moving out from it resembles what we call a pop operation.

Peek Operation

This operation on a stack returns the topmost element in a stack. This operation is also known as the peek() operation on the stack.

Applications of Stack in Data Structure

The application of stack in data structure are:

1. In code editors – Stacks are used in various code editors like VS Code, Atom, etc. to match the opening & closing tags in the languages like HTML, XML, etc.

2. In matching bracket pairs – This is one of the most famous application of stack in data structure. Stacks help us in identifying if the bracket pairs in a sentence or string are complete or missing.

3. In browsers – You are reading this article in your web browser, what will happen if you press the back button present at the left-hand corner of your screen? It would take you back to your last visited website or link. It is done using stacks. Every time you visit a new link, it is stored in the stack. And, every time you press the back button, the current link is popped out from the lifo stack, and the previous link is made available.

4. In compilers – Stacks are used heavily by the browsers to convert infix expressions to postfix expressions. It is done because the compilers can not read an expression directly. E.g., if there is an expression – 5 + (1 + 4/2), the compiler cannot process it like humans. Thus, it solves this expression by converting it into a postfix or prefix expression

Dive into the World of Efficient Coding – Enroll in Scaler Academy's DSA Course Today and Learn from Industry Experts!

Read More

• Divide and Conquer Algorithm