Page 45 - Data Structures Interactive Book

Chapter 5

5.1 Introduction to Stacks

A stack is a linear data structure that follows the Last-In, First-Out (LIFO) principle. This

means that the last element inserted into the stack is the first one to be removed. Stacks are

widely used in computer science for managing function calls, evaluating expressions, and
checking balanced symbols. Conceptually, a stack is similar to a pile of books: the last book

placed on top is the first one to be removed.

5.1.1 Definition and Characteristics

A stack is defined by two primary operations: push, which adds an element to the top,
and pop, which removes the top element. Other operations include peek/top, which retrieves

the top element without removing it, and checks for whether the stack is empty or full. Stacks

are characterized by their simplicity and efficiency in handling sequential operations.

5.1.2 Definition and Characteristics

Stacks are used in many areas of computer science:

• Expression evaluation: converting and evaluating postfix, prefix, and infix

expressions.

• Balanced parentheses checking: ensuring that every opening bracket has a

matching closing bracket.
• Function call management: recursion relies on stacks to store return addresses

and local variables.

• Undo operations: text editors use stacks to reverse recent actions.

5.2 Implementation of Stacks

Stacks can be implemented using arrays or linked lists, each with its own advantages.

45