Stack in Data Structure

What is a Stack in Data Structure?

A stack is a linear data structure in which objects are stacked on top of each other and can only be accessed from the top. Elements are placed in LIFO (Last-In-First-Out) or FILO (First-In, Last-Out) order.

LIFO & FIFO Principle of Stack

LIFO is the acronym for 'last in, first out' and refers to the stack data structure. In a LIFO data structure, the most recently added member to the stack is processed first. In contrast, FIFO stands for 'first in, first out' & uses a queue data structure.

Implementation of Stack

There are two main methods for implementing a stack:

1. Array
2. Linked List

1. Array

Array-based stacks have a limited size, thus you can only add or remove elements up to the array's size. 

2. Linked List

Linked list-based stacks have no defined size, so you can add and remove as many elements as you wish.

Types of Stack

There are 2 types of Stack:

1. Fixed Size Stack
2. Dynamic Size Stack

1. Fixed Size Stack

Fixed-size stacks have a fixed capacity and cannot be changed. When attempting to add an element to a full stack, an overflow error occurs, whereas removing an element from an empty stack causes an underflow error.

2. Dynamic Size Stack

The Dynamic Size Stack can change its size as needed. Expands when full to accommodate new parts; contracts when empty. Implemented linked lists for simple scaling.

Basic Stack Operations

• Push: To place an element into the stack
• Pop: To remove an element from the stack, use the pop operation.
• Top: Top returns the stack's top element.
• IsEmpty: IsEmpty returns true if the stack is empty, else false.
• Size: Size returns the stack's size.
• Count(): Returns the total number of elements on a stack.
• Change(): Changes the element at the specified place.
• Display(): Prints all entries on the stack.

Working of the Stack in Data Structures

• A stack is a linear data structure that uses the Last In, First Out (LIFO) principle.
• Elements are added to and removed from the top of the stack.
• Push is used to add an element, while pop is used to remove the top element.
• Peek allows you to examine the top element without deleting it.
• When arrays or linked lists are used, stack operations such as push, pop, and peek have a temporal complexity of O(1).

Complexity Analysis of Stack Operation

Applications of Stack

• Function Calls and Recursion: The compiler keeps the return address and parameters on the stack, which are retrieved upon function completion.
• Expression Evaluation: The stack helps to evaluate arithmetic expressions by pushing operands and operators and resolving subexpressions.
• Parsing: Stack keeps track of symbol stacking (such as brackets) in parsing algorithms.
• Undo/Redo Operations: The stack holds application states for undo/redo capabilities in software.
• Backtracking: Stack helps in the storage and retrieval of path information during search algorithms, making backtracking more efficient.

Advantages of Stack

• Simplicity: Stacks are easy to implement, making them user-friendly.
• Memory Efficiency: They use contiguous memory allocation, which optimizes memory usage.
• Quick Access: Elements are immediately accessible from the top, which is useful for tasks such as expression parsing.
• Recursion Support: Stacks make recursive computations easier by storing function calls and associated states.
• Compiler Usage: Important in compiler design for parsing and syntax analysis of computer languages.

Disadvantages of Stack

• Limited Storage: As stacks have a restricted capacity, data loss occurs when they overflow.
• No Random Access: Access is limited to the top, with no direct access to the middle elements.
• Overflow and Underflow: If you add or remove too many items, the program will crash.
• Memory Concerns: The stack's contiguous memory utilization may result in fragmentation or leaks.