GDcademy
Stacks in DSA: All You Need to Know to Get Started - Part 01

Stacks in DSA: All You Need to Know to Get Started - Part 01

Gourab Das's photo
Gourab Das
·

5 min read

Table of contents

1.Basics of stack

Definition of Stack:

  • A stack is a non-primitive linear data structure. [A stack is called a non-primitive linear data structure because it organizes and manages multiple data elements sequentially (linear), derived from primitive types, and supports specific operations like push and pop]

  • It is an ordered list where addition (push) and deletion (pop) of items occur only at one end, called the Top of Stack (TOS).

Last-In-First-Out (LIFO) Principle:

  • The last element added to the stack is the first to be removed.

  • This principle is why stacks are called LIFO lists.

Real-Life Stack Examples :

  1. Steel Tiffin Boxes:

    • Adding a tiffin box to the top of the stack is pushing, and taking one from the top is popping.

  2. Thali Stack in Marriage or Pandal:

    • Plates are stacked one on top of the other; the last plate added (on top) is used first.

  3. Chai Glasses at Tea Stalls:

    • Glasses are stacked after washing (push) and picked from the top for serving (pop).

  4. Pooja Thalis:

    • In temples, pooja thalis are stacked for distribution, and the last one placed is taken first.

  5. Laddus in Boxes:

    • When laddus are placed in a box, the last laddu added to the top is the first one removed.

  6. Notebook Pile in Stationery Shops:

    • A pile of notebooks where the last placed notebook on top is sold first.

Stack Behavior:

  • The base of the stack remains fixed.

  • Adding elements increases the stack top.

  • Removing elements decreases the stack top.

  • all elements of a stack are homogenous that is they are all of the same type.

  • Multiple Occurrences of the same elements is permitted as per the characteristics of the stack.

Implementation of Stacks:

  • Stacks can be implemented in two ways:

    1. Static Implementation (using arrays).

    2. Dynamic Implementation (using linked lists).

Static Implementation:

  • Technique:

    • Uses arrays to create a stack.

  • Advantages:

    • Simple to implement.

  • Disadvantages:

    1. The size of the stack must be predefined and cannot be changed during execution.

    2. Inefficient memory utilization:

      • If the stack contains fewer elements than allocated, memory is wasted.

      • If the stack exceeds its size, no new elements can be added.

Dynamic Implementation:

  • Technique:

    • Uses linked lists to implement stacks.

    • Push and pop operations are performed at one end of the list.

  • Advantages:

    • Solves the size limitation issue of arrays.

    • Memory is allocated dynamically as needed.

  • Representation:

    • The stack is represented as a singly linked list.

    • Each node contains:

      1. Data.

      2. A pointer to the next node in the list.

         struct Node {
     int data;
     struct Node* next;
 };

2.Stack ADT

The term Stack ADT (Abstract Data Type) is used instead of just stack to emphasize the abstract nature of the data structure. Here's why -

  1. Abstraction:

    • A Stack ADT defines the behavior (operations and rules) of a stack without specifying how it should be implemented. It focuses on what the stack does rather than how it does it.

    • When you say stack, it can refer to the concrete data structure, which is an actual implementation using an array, linked list, or other techniques.

  2. Generalization:

    • The Stack ADT represents a general concept of a stack, independent of the specific implementation details.

    • Saying stack ADT allows us to discuss the principle and operations behind stacks, regardless of whether they are implemented with arrays, linked lists, or other data structures.

  3. Flexibility:

    • The term ADT allows flexibility to use different implementation methods while still adhering to the same stack operations (like push, pop, peek, etc.).

In summary, Stack ADT focuses on the abstract set of operations and their behavior, while stack refers to the actual implementation. The ADT term makes it clear that the focus is on the concept rather than the details of the implementation.

An Abstract Data Type (ADT) can be defined for any data structure. The key idea behind an ADT is that it specifies what operations are possible on the data structure, without defining how these operations are implemented.

Definition : A Stack ADT is an abstract data type that defines a collection of elements with two main operations: push (add to the top) and pop (remove from the top), following the Last In, First Out (LIFO) principle.

Uses of Stack ADT

  1. Expression Evaluation (Infix, Postfix, Prefix):

    • The Stack ADT is used to evaluate mathematical expressions, especially in postfix (Reverse Polish Notation) or prefix (Polish Notation), where operands and operators are processed in a specific order using the stack's LIFO nature.

  2. Function Call Management (Recursion):

    • The Stack ADT is utilized by compilers for managing function calls and recursion. Each function call is pushed onto the stack, and when a function finishes executing, it is popped off the stack, ensuring proper order and memory management.

  3. Undo/Redo Functionality:

    • In applications like word processors or image editors, the Stack ADT is employed to implement undo and redo functionality. The previous states of the application are pushed onto the stack, allowing the user to pop to undo actions or push to redo them.

  4. Balanced Parentheses/Brackets Checking:

    • The Stack ADT is commonly used to verify whether parentheses, brackets, or braces are balanced in an expression. Opening symbols are pushed onto the stack, and closing symbols are popped from the stack to ensure proper matching.

  5. Depth-First Search (DFS) in Graphs:

    • The Stack ADT is central to the Depth-First Search (DFS) algorithm in graph traversal. Nodes are pushed onto the stack, and the algorithm explores nodes deeper before backtracking, with the stack managing the exploration state.

More About Stack ADT – Coming Soon in Part 2!

Stacks are an essential data structure in computer science, and we've only scratched the surface with their core concepts and uses. In Part 2 of this blog, we’ll dive deeper into advanced applications, implementations, and real-world use cases of Stack ADT. Stay tuned for more insights on how stacks power various algorithms and systems, and how you can leverage them in your projects.

Don't miss out! Follow our blog on Hashnode for updates and to explore more about Stack ADT and other exciting topics in the world of data structures.

Stay tuned! 🌟

DSAstack