Understanding the Stack ADT: LIFO Principles and Operations

Recommended resources

The freely available resources this lesson will direct you to.

Welcome to a new module in our course! So far, we have focused on algorithms: procedures for solving problems, like the sorting methods you just mastered. In the last lesson, you did an excellent job comparing those algorithms based on their performance trade-offs. Now, we shift our focus to data structures, the other essential pillar of programming. Algorithms operate on data, and the way we structure that data has a profound impact on an algorithm's efficiency and complexity.

In this lesson, you will be introduced to one of the most fundamental data structures: the Stack. Our goal is to describe the Stack as an Abstract Data Type (ADT), understand its "Last-In, First-Out" (LIFO) behavior, and learn about its primary operations: push, pop, and peek. This conceptual foundation is the first step before we dive into implementing a stack in C in our next lesson.

1. Abstract Data Types vs. Data Structures

Before we look at the stack itself, let's clarify an important concept: the difference between an Abstract Data Type (ADT) and a data structure.

An ADT is a conceptual model. It is defined by its behavior—what you can do with it (its operations) and what rules it follows. It's an interface. For example, a "List" ADT is defined by operations like add, remove, and get, but it doesn't specify how these operations are implemented.
A data structure is a concrete implementation. It's concerned with how data is organized in memory to fulfill the promises of an ADT. For example, a List ADT could be implemented using an array or a linked list. These are different data structures that achieve the same conceptual behavior.

The video below explains this distinction and introduces the stack as an ADT.

Introduction to Abstract Data Types: Stacks

The video "Introduction to Abstract Data Types: Stacks" by theteachr gives a clear and concise explanation of these concepts.

Please watch two short segments: First, watch the introduction from the beginning to LIFO strategy. This will define what an ADT is and introduce the stack's core principle. Then, skip ahead to the distinction between ADTs and data structures. This part reinforces the difference and correctly classifies the stack as an ADT.

As the video states, a stack is an ADT. Its defining characteristic is not how it's built (e.g., with an array), but how it behaves.

2. The Stack: Last-In, First-Out (LIFO)

The defining behavior of a stack is the LIFO principle, which stands for Last-In, First-Out. This means the last item you add to the stack is the very first item you can take out.

This is a very intuitive concept that appears all around us. The following video uses some excellent real-world analogies to make this idea concrete.

3.1 Stack in Data Structure | Introduction to Stack | Data Structures Tutorials

In "Stack in Data Structure" by Jenny's Lectures CS IT, the instructor explains the LIFO principle using simple examples.

Watch from the introduction. Pay close attention to the analogies of a stack of plates and a CD stand. Notice how in both cases, you can only add or remove an item from the top.

As you saw, you can't just pull a plate from the bottom of the pile without collapsing the whole thing. The only accessible plate is the one on top. This single point of access is called the top of the stack. All operations happen at the top.

This diagram illustrates the core LIFO principle. New elements are "pushed" onto the top, and elements are "popped" from the top. The last one in is always the first one out.

3. Primary Stack Operations

An ADT is defined by its operations. For a stack, there are three primary operations that you must know:

Push: Adds a new element to the top of the stack.
Pop: Removes the element from the top of the stack.
Peek (sometimes called Top): Returns the value of the top element without removing it.

Additionally, two helper operations are essential for managing the stack:

isEmpty: Checks if the stack has any elements.
isFull: Checks if the stack has reached its capacity (this is mainly relevant for fixed-size implementations, like with an array).

Stack in C - GeeksforGeeks

The article "Stack in C" from GeeksforGeeks provides a concise summary of these operations in a table.

Please read the introduction and focus on the table under the heading "Basic Operations in C". The table clearly defines each operation. Don't worry about the time/space complexity columns for now, though you might notice they are very efficient!

Let's trace these operations with a simple example. Imagine we have an empty stack that can hold integers.

push(10): The stack now contains 10. The top is 10.
```
| 10 | <-- top
+----+
```
push(20): The stack now contains 10 and 20. The top is now 20.
```
| 20 | <-- top
+----+
| 10 |
+----+
```
peek(): This operation returns the value 20. The stack remains unchanged.
pop(): This removes the top element, 20. The top now points to 10.
```
| 10 | <-- top
+----+
```
pop(): This removes the top element, 10. The stack is now empty.

4. Edge Cases: Overflow and Underflow

When working with stacks, especially when they are implemented with a fixed-size container like an array, two critical error conditions can occur:

Stack Overflow: This happens when you try to push an element onto a stack that is already full. There is no room for the new element.
Stack Underflow: This happens when you try to pop or peek on an empty stack. There is no element to remove or view.

A robust stack implementation must always check for these conditions to prevent errors.

3.1 Stack in Data Structure | Introduction to Stack | Data Structures Tutorials

Let's return to the video from Jenny's Lectures to see how these conditions are handled.

Watch the segment from underflow and overflow. The instructor demonstrates what happens when you try to pop from an empty stack (underflow) and push to a full stack (overflow) using a fixed-size array example.

5. Where Are Stacks Used?

Stacks are not just a theoretical concept; they are used everywhere in computer science. Here are a few examples that you've likely interacted with:

Function Call Management: When your C program calls a function, the computer pushes information about that function (its local variables, return address) onto the "call stack". When the function returns, it's popped off the stack. This is how nested function calls work.
Undo/Redo Functionality: In a text editor, when you type a character or perform an action, that action can be pushed onto a stack. When you hit "Undo", the application simply pops the last action from the stack and reverses it.
Browser History: The "Back" button in your web browser works like a stack. Each page you visit is pushed onto a stack. When you click "Back", the current page is popped, revealing the previous one.

Conclusion

In this lesson, you took the first step into the world of data structures by exploring the Stack ADT. You learned that its behavior, not its implementation, is what defines it.

Key Takeaways:

A Stack is an Abstract Data Type (ADT) that follows a Last-In, First-Out (LIFO) policy.
All operations on a stack happen at one end, known as the top.
The three primary operations are:
- push: Adds an element to the top.
- pop: Removes the element from the top.
- peek: Views the top element without removing it.
You must be aware of two critical error conditions: stack overflow (pushing to a full stack) and stack underflow (popping from an empty stack).

Preview of the Next Lesson:
Now that you understand the "what" and "why" of stacks, the next step is to learn the "how". In the next lesson, we will get practical and implement our own stack in C using a dynamically-sized array. You will write the code for the push, pop, and peek functions yourself.