Stack Operations in Data Structure

Takeaways

Operations in stack:

push(), pop(), peek(), isEmpty(), isFull(), size()

Introduction to Stack Data Structure

A stack is a data structure which is used to store data in a linear fashion. It is an Abstract data type (ADT) in which data is inserted and deleted from a single end which is the stack's top. It follows a Last in, First out (LIFO) principle i.e. the data which is inserted most recently in the stack will be deleted first from the stack. Given below is the pictorial representation of how a stack looks like.

[IMAGE 1 FINISH SAMPLE]

We also have a separate article where the stack data structure is discussed in detail: Stacks in Data Structure. This pictorial representation shows how the stack data structure works: the recently added element is always at the top and is the first to be accessed or removed.

We also have a separate article where the stack data structure is discussed in detail: Stacks in Data Structure.

Stack Representation

A stack follows a Last in, First out principle (LIFO). This means the data inserted in the stack last will be first to be removed. All operations, such as insertion (push) and deletion (pop), occur at the top of the stack, and the top element is always the most recently element added.

Given below is the stack representation to show how data is inserted and deleted in a stack.

[IMAGE 2 FINISH SAMPLE]

Stack Operations

There are various stack operations that are applicable on a stack. Stack operations are generally used to extract information and data from a stack data structure.

Some of the stack operations are given below.

1. push()

The push operation adds a data element to the top of the stack. In array based stacks, the push operation must first check if the stack is full before adding a new element. If the stack is full, a stack overflow occurs and the push should not proceed. In a typical stack class implementation in Java, you might see:

[IMAGE 3 FINISH SAMPLE]

Given below is the syntax of the push function in the stack.

2. pop()

The pop operation removes the top element from the stack. The pop operation must check if the stack is empty before removing an element to avoid stack underflow. Stack underflow occurs when attempting to pop from an empty stack. In code:

[IMAGE 4 FINISH SAMPLE]

Given below is the syntax of the pop function in the stack.

3. topElement() / peek()

TopElement / Peek is a function in the stack which is used to extract the element present at the stack top.

[IMAGE 5 FINISH SAMPLE]

In C++, we use the top()function to extract the element present at the stack's top. Given below is the syntax of the top function in the stack.

4. isEmpty()

isEmpty is a boolean function in stack definition which is used to check whether the stack is empty or not. It returns true if the stack is empty. Otherwise, it returns false. The isempty operation checks for an empty stack, which is important to prevent errors such as stack underflow during pop or peek operations.

[IMAGE 6 FINISH SAMPLE]

5. isFull()

isFull is a function which is used to check whether the stack has reached its maximum limit of insertion of data or not i.e. if 'maxLimit' is the maximum number of elements that can be stored in the stack and if there are exactly maxLimit number of elements present in the stack currently, then the function isFull() returns true. Otherwise, if the number of elements present in the stack currently are less than 'maxLimit', then isFull() returns false.

Given below is the syntax for the isFull function in the stack.

6. size()

Size is a function in stack definition which is used to find out the number of elements that are present inside the stack.

[IMAGE 7 FINISH SAMPLE]

Given below is the syntax of the size function in stack.

Array Based Stacks vs Linked List Based Stacks

Array based stacks use a fixed size array (e.g., private int arr) to store elements, and require managing int top and int size or private int capacity. They are limited by their maximum capacity and can experience stack overflow if the stack is full. Linked list based stacks, on the other hand, use nodes and only a pointer to the top node, allowing dynamic resizing and no fixed size limitation. Linked list implementations are more flexible but may use more memory per data element.

Example: Stack Implementation in C

This demonstrates stack implementation in C, using int stack, int top, and int data.

Stacks can be implemented in various programming languages such as C, C++, Java, Python, and JavaScript, using either arrays or linked lists.

Application: Evaluate Arithmetic Expressions

Stacks are commonly used to evaluate arithmetic expressions, such as in the Shunting Yard algorithm for converting infix to postfix notation.

• A stack is a data structure which is used to store data in a linear fashion.

• Stack follows a Last in, First out (LIFO) principle i.e. the data which is inserted most recently in the stack will be deleted first from the stack.

• There are many stack operations that can be performed on a stack. Some of them are push(), pop(), peek(), isEmpty(), isFull(), size().

• To implement stack efficiently, you can use either arrays (for array based stacks) or linked lists (for linked list based stacks). In Python, lists can be used to stack efficiently.

Applications of Stacks

Stacks play a vital role in computer science and are widely used in various programming scenarios due to their efficient Last-In-First-Out (LIFO) behavior. Here are some of the most common applications of the stack data structure:

• Managing Function Calls (Call Stack): In most programming languages, the call stack is used to keep track of active function calls. When a function is called, its details are pushed onto the stack, and when the function returns, its information is popped off. This helps manage recursive algorithms and nested function calls efficiently.

• Expression Evaluation and Syntax Parsing: Stacks are essential for evaluating arithmetic expressions, especially those written in postfix (Reverse Polish Notation) or for converting infix expressions to postfix or prefix. Expression evaluation stacks help in parsing and calculating the result by following the correct order of operations.

• Backtracking Algorithms: Many algorithms, such as solving mazes, puzzles, or implementing undo features, use stacks to remember previous states. When backtracking, the most recently added state is popped from the stack, allowing the program to return to a previous point.

• Browser History Management: Web browsers use stacks to manage the history of visited pages. Each new page visited is pushed onto the stack, and when the user clicks the “back” button, the most recent page is popped, taking the user to the previous page.

• Memory Management: Stacks are used for memory allocation in programming, especially for storing local variables and function parameters. The stack structure ensures that memory is allocated and deallocated in the correct order.

• Undo/Redo Operations: Many applications, such as text editors, use stacks to implement undo and redo functionality. Each action is pushed onto a stack, and undo operations pop the last action to revert changes.

• Balancing Symbols: Stacks are used to check for balanced parentheses, brackets, and braces in code editors and compilers. As each opening symbol is encountered, it is pushed onto the stack, and when a closing symbol appears, the stack is checked to ensure it matches the most recent opening symbol.

These examples highlight how the stack data structure is fundamental in implementing efficient, real-world solutions that rely on the first out lifo principle. Whether managing function calls or enabling user-friendly features like undo, stacks are an indispensable tool in computer science.