Stack

A linear data structure that follows the LIFO principle

Introduction

A stack is a simple, linear data structure that follows the Last In, First Out (LIFO) principle. This means that the last element added to the stack will be the first one to be removed.

Types of Stack

1. Fixed Size Stack

A stack with a pre-defined maximum size, implemented using an array.

Features

  • Size is determined at the time of creation.

  • Cannot grow beyond its defined capacity.

Advantages

  • Size is predefined at creation, making it simple.

  • Efficient when the maximum size is known.

Disadvantages

  • Resizing is difficult and costly.

  • Wastes memory if not fully used.

2. Dynamic Size Stack

A stack that can grow or shrink dynamically as needed, implemented using linked lists or resizable arrays.

Features

  • Grows or shrinks based on the stack’s usage, so you don’t need to manually adjust the size.

  • Allocates memory as needed, avoiding wasted space.

Advantages

  • No memory wastage, uses only the space needed.

  • Can handle unexpected growth.

Disadvantages

  • Slightly more complex to implement.

Key Concept

LIFO Principle (Last In, First Out): The last element added to the stack will be the first one to be removed.

Example: Think of a stack of plates. When you add a plate, you place it on top of the stack. To remove a plate, you take the top plate off first.

Key Properties of Stack

Linear Data Structure:

  • A stack organizes data sequentially, with each element connected to the one before and after it (if applicable).

LIFO Principle:

  • Stands for Last In First Out, meaning the last element added to the stack is the first to be removed

Single Access Point:

  • All operations are performed at one end of the stack, called the top. You cannot access elements directly at the middle or bottom.

Dynamic or Fixed Size:

  • Array-based Stack: Has a fixed size and may require resizing when full.

  • Linked List-based Stack: Dynamically grows and shrinks as elements are added or removed.