Image

UNIVERSITY OF NAIROBI
FACULTY OF ENGINEERING
DEPARTMENT OF ELECTRICAL AND INFORMATION ENGINEERING

DS
DATA STRUCTURES

FEE 3132: Data Structures and Algorithms

Lecture Notes:

Stack Data Structure

Prepared by: Dr. Davies Rene Segera

Email: [email protected]
Office: Engineering Building, Room 203
Office Hours: Monday & Wednesday, 14:00-16:00

COURSE INFORMATION
Semester: March - July 2025
Class Schedule: Tuesday 08:00-10:00, Thursday 14:00-16:00
Lab Sessions: Friday 14:00-16:00
Prerequisites: Introduction to Programming (C++)

March 10, 2025

 Image
University of Nairobi Stack Data Structure

À Learning Objectives
After going through these notes, students will be able to:

• Define and explain the stack data structure and its LIFO principle
• Identify real-world applications of stacks
• Implement a stack using arrays in C++
• Perform basic stack operations: push(), pop(), peek()
• Verify stack states using isEmpty() and isFull()
• Apply stack operations to solve simple problems
• Analyze the time and space complexity of stack operations

Contents

1 Introduction to Stacks 2
1.1 What is a Stack? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Conceptual Understanding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2 Stack Representation 3
2.1 Stack Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

3 Basic Operations on Stacks 3

3.1 Stack Insertion: push() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3.2 Stack Deletion: pop() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3.3 Retrieving Top Element: peek() . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.4 Checking Stack State . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

4 Complete Stack Implementation in C++ 7

5 Stack Visualization 9

6 Applications of Stacks 9
6.1 Example: Balancing Parentheses . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

7 Complexity Analysis 11

8 Take-Away Points 12

9 Assignments 12

10 References 13

Dr. Davies Rene Segera 1 Electrical & Information Engineering

 Image
University of Nairobi Stack Data Structure

1 Introduction to Stacks

1.1 What is a Stack?

A stack is a linear data structure where elements are stored in the LIFO (Last In First
Out) principle. The last element inserted would be the first element to be deleted. A stack is an
Abstract Data Type (ADT) that is commonly used in most programming languages.

Definition
Stack Data Structure:
A Stack is a linear data structure that allows insertion and deletion of elements only at
one end, referred to as the top. It follows the LIFO/FILO pattern:

• LIFO: Last In, First Out

• FILO: First In, Last Out

It is named "stack" because it has similar operations as real-world stacks, for example:

Top

Plate 4 Push
Plate 3
Pop
Plate 2
Plate 1

Bottom

Figure 1: A stack of plates - A real-world analogy of a Stack

1.2 Conceptual Understanding

Despite its simple structure, a stack is considered a complex data structure because it uses
other data structures for its implementation, such as:

• Arrays
• Linked lists
• Structures and pointers

Think of a stack as a container where you can only:

• Add items to the top (push)

• Remove items from the top (pop)
• View the top item without removing it (peek)

Dr. Davies Rene Segera 2 Electrical & Information Engineering

 Image
University of Nairobi Stack Data Structure

2 Stack Representation

2.1 Stack Structure

A stack allows data operations at one end only. At any given time, we can only access the
top element of a stack.

TOP
Push
Element 4 (Top)
Pop
Element 3

Element 2
Element 1 (Bottom)

Stack in Memory

Figure 2: Visual representation of a Stack with its operations

The key components of a stack are:

• Stack Array: The array that holds the elements

• Top Pointer: Points to the topmost element within the stack
• Maximum Size: The capacity of the stack (in fixed-size implementations)

. Important Note
When implementing a stack using an array:

• The initial value of top is -1 (indicating an empty stack)

• For a stack of size n, the valid range for top is [-1, n-1]
• When top = -1, the stack is empty
• When top = n-1, the stack is full

3 Basic Operations on Stacks

Stack operations are typically performed for:

• Initialization
• Usage
• De-initialization

The most fundamental operations in the stack ADT include:

Dr. Davies Rene Segera 3 Electrical & Information Engineering

 Image
University of Nairobi Stack Data Structure

3.1 Stack Insertion: push()

Ð Algorithm
Push Operation:
1: function Push(data)
2: if stack is full then
3: Display error: "Stack Overflow"
4: return false
5: end if
6: increment top
7: stack[top] ← data
8: return true
9: end function

 Example
Push Visualization:

15 top = 4
Push(15)
123 123
62 62
10 10
44 44

Before Push(15) After Push(15)

1 // Function to check if stack is full

2 bool isFull() {
3 if(top == MAXSIZE - 1)
4 return true;
5 else
6 return false;
7 }
8
9 // Function to insert into the stack
10 bool push(int data) {
11 if(!isFull()) {
12 top = top + 1;
13 stack[top] = data;
14 return true;
15 } else {
16 cout << "Could not insert data, Stack is full." << endl;
17 return false;
18 }
19 }

Listing 1: Push Implementation in C++

Dr. Davies Rene Segera 4 Electrical & Information Engineering

 Image
University of Nairobi Stack Data Structure

3.2 Stack Deletion: pop()

Ð Algorithm
Pop Operation:
1: function Pop
2: if stack is empty then
3: Display error: "Stack Underflow"
4: return error value
5: end if
6: data ← stack[top]
7: decrement top
8: return data
9: end function

 Example
Pop Visualization:

15 top = 4 Returned value: 15

Pop()
123 123 top = 3
62 62
10 10
44 44

Before Pop() After Pop()

1 // Function to check if stack is empty

2 bool isEmpty() {
3 if(top == -1)
4 return true;
5 else
6 return false;
7 }
8
9 // Function to delete from the stack
10 int pop() {
11 int data;
12 if(!isEmpty()) {
13 data = stack[top];
14 top = top - 1;
15 return data;
16 } else {
17 cout << "Could not retrieve data, Stack is empty." << endl;
18 return -1; // Return a sentinel value
19 }
20 }

Listing 2: Pop Implementation in C++

Dr. Davies Rene Segera 5 Electrical & Information Engineering

 Image
University of Nairobi Stack Data Structure

3.3 Retrieving Top Element: peek()

Ð Algorithm
Peek Operation:
1: function Peek
2: if stack is empty then
3: Display error: "Stack is empty"
4: return error value
5: end if
6: return stack[top]
7: end function

1 // Function to return the topmost element

2 int peek() {
3 if(!isEmpty()) {
4 return stack[top];
5 } else {
6 cout << "Stack is empty." << endl;
7 return -1; // Return a sentinel value
8 }
9 }

Listing 3: Peek Implementation in C++

3.4 Checking Stack State

⋆ Tips & Tricks

Stack State Verification:

• Always check for stack overflow before pushing

• Always check for stack underflow before popping
• Use isEmpty() and isFull() helper functions to make your code cleaner

1 // Function to check if stack is empty

2 bool isEmpty() {
3 if(top == -1)
4 return true;
5 else
6 return false;
7 }
8
9 // Function to check if stack is full
10 bool isFull() {
11 if(top == MAXSIZE - 1)
12 return true;
13 else
14 return false;
15 }

Listing 4: Stack State Check Functions in C++

Dr. Davies Rene Segera 6 Electrical & Information Engineering

 Image
University of Nairobi Stack Data Structure

4 Complete Stack Implementation in C++

Let’s examine a complete implementation of a stack class in C++:

1 #include <iostream>
2 using namespace std;
3
4 class Stack {
5 private:
6 int MAXSIZE;
7 int *stack;
8 int top;
9
10 public:
11 Stack(int size) {
12 MAXSIZE = size;
13 stack = new int[MAXSIZE];
14 top = -1;
15 }
16
17 ~Stack() {
18 delete[] stack;
19 }
20
21 bool isEmpty() {
22 return (top == -1);
23 }
24
25 bool isFull() {
26 return (top == MAXSIZE - 1);
27 }
28
29 bool push(int data) {
30 if(!isFull()) {
31 top++;
32 stack[top] = data;
33 return true;
34 } else {
35 cout << "Stack Overflow!" << endl;
36 return false;
37 }
38 }
39
40 int pop() {
41 if(!isEmpty()) {
42 int data = stack[top];
43 top--;
44 return data;
45 } else {
46 cout << "Stack Underflow!" << endl;
47 return -1;
48 }
49 }
50
51 int peek() {
52 if(!isEmpty()) {
53 return stack[top];
54 } else {
55 cout << "Stack is empty!" << endl;
56 return -1;
57 }
58 }
59

Dr. Davies Rene Segera 7 Electrical & Information Engineering

 Image
University of Nairobi Stack Data Structure

60 void display() {
61 if(!isEmpty()) {
62 cout << "Stack elements: ";
63 for(int i = 0; i <= top; i++) {
64 cout << stack[i] << " ";
65 }
66 cout << endl;
67 } else {
68 cout << "Stack is empty!" << endl;
69 }
70 }
71 };

Listing 5: Complete Stack Class Implementation

 Example
Main Program Using Stack Class:
int main() {
// Create a stack of size 5
Stack s(5);

// Push elements
s.push(44);
s.push(10);
s.push(62);
s.push(123);
s.push(15);

// Display the stack

s.display();

// Try pushing one more (should show overflow)

s.push(99);

// Peek at top element

cout << "Top element: " << s.peek() << endl;

// Pop all elements

cout << "Popped elements: ";
while(!s.isEmpty()) {
cout << s.pop() << " ";
}
cout << endl;

// Try popping from empty stack (should show underflow)

s.pop();

return 0;
}

Output:

Stack elements: 44 10 62 123 15

Stack Overflow!
Top element: 15
Popped elements: 15 123 62 10 44
Stack Underflow!

Dr. Davies Rene Segera 8 Electrical & Information Engineering

 Image
University of Nairobi Stack Data Structure

5 Stack Visualization

The following diagram illustrates how the stack operations work in memory:

STACK DATA STRUCTURE OPERATIONS

PUSH OPERATION
push(15) 15 top
Before: 123 After:
123
62 62
10 10 STACK PROPERTIES
44 44

LIFO (Last In First Out) Single point of access (top) O(1) time complexity for all operations Fixed size in ar
POP OPERATION 15 pop() returns 15
Before: 123 After:
123 top
62 62
10 10
44 44

Figure 3: Visualization of Stack Operations

6 Applications of Stacks

Stacks have numerous applications in computer science and programming:

STACK APPLICATIONS

Function Call Expression

Management Evaluation

Parentheses
Undo Mechanism
Matching

Memory Man-
Browser History
agement

Figure 4: Common Applications of Stack Data Structure

6.1 Example: Balancing Parentheses

One of the most common applications of stacks is checking for balanced parentheses in
expressions.

Dr. Davies Rene Segera 9 Electrical & Information Engineering

 Image
University of Nairobi Stack Data Structure

 Example
Balanced Parentheses Algorithm:

1.
✗ Create an empty stack
✓
2. Scan the expression from left to right
3. If the current character is an opening bracket (’(’, ’[’, ’{’), push it onto the stack
4. If the current character is a closing bracket (’)’, ’]’, ’}’), check if the stack is empty:
• If empty, the expression is unbalanced
• If not empty, pop the top element and check if it’s the matching opening bracket
• If it doesn’t match, the expression is unbalanced
5. After scanning the expression, if the stack is empty, the expression is balanced

1 #include <iostream>
2 #include <stack>
3 #include <string>
4 using namespace std;
5
6 bool areParenthesesBalanced(string expr) {
7 stack<char> s;
8
9 for(int i = 0; i < expr.length(); i++) {
10 if(expr[i] == ’(’ || expr[i] == ’[’ || expr[i] == ’{’) {
11 s.push(expr[i]);
12 continue;
13 }
14
15 // If current character is not an opening bracket,
16 // then it must be a closing bracket
17 if(s.empty())
18 return false;
19
20 char check;
21 switch(expr[i]) {
22 case ’)’:
23 check = s.top();
24 s.pop();
25 if(check == ’{’ || check == ’[’)
26 return false;
27 break;
28
29 case ’}’:
30 check = s.top();
31 s.pop();
32 if(check == ’(’ || check == ’[’)
33 return false;
34 break;
35
36 case ’]’:
37 check = s.top();
38 s.pop();
39 if(check == ’(’ || check == ’{’)
40 return false;
41 break;
42 }
43 }
44

Dr. Davies Rene Segera 10 Electrical & Information Engineering

 Image
University of Nairobi Stack Data Structure

45 // Check if stack is empty

46 return (s.empty());
47 }
48
49 int main() {
50 string expr = "{[()]}";
51 if(areParenthesesBalanced(expr))
52 cout << "Balanced" << endl;
53 else
54 cout << "Not Balanced" << endl;
55
56 expr = "{[(])}";
57 if(areParenthesesBalanced(expr))
58 cout << "Balanced" << endl;
59 else
60 cout << "Not Balanced" << endl;
61
62 return 0;
63 }

Listing 6: Balanced Parentheses Implementation

7 Complexity Analysis

ø Key Concepts
Time Complexity:

• push(): O(1) - Constant time complexity

• pop(): O(1) - Constant time complexity
• peek(): O(1) - Constant time complexity
• isFull(): O(1) - Constant time complexity
• isEmpty(): O(1) - Constant time complexity

Space Complexity:

• O(n) - Where n is the maximum size of the stack

Advantages Disadvantages Best Used For

• Easy to implement • Fixed size (array imple- • Expression evaluation

• Memory efficient (no mentation) • Function call manage-
pointers) • No random access ment
• O(1) operations • Not suitable for all prob- • Undo mechanisms
• Simple to understand lems • Syntax parsing
• Waste of memory if over- • Conversion algorithms
flow rare

Dr. Davies Rene Segera 11 Electrical & Information Engineering

 Image
University of Nairobi Stack Data Structure

8 Take-Away Points

⋆ Key Takeaways

1. A stack is a linear data structure that follows the LIFO (Last In First Out) principle.
2. The main operations on a stack are push() (insertion), pop() (deletion), and peek()
(viewing top element).
3. A stack’s state is monitored through isEmpty() and isFull() methods.
4. Stacks can be implemented using arrays (fixed size) or linked lists (dynamic size).
5. All basic stack operations have O(1) time complexity.
6. Common applications include: function call management, expression evaluation, and
parentheses matching.
7. Stack overflow occurs when trying to push onto a full stack.
8. Stack underflow occurs when trying to pop from an empty stack.

9 Assignments

Assignment
Assignment 1: Basic Implementation
Implement a Stack class in C++ with all the basic operations (push, pop, peek, isEmpty,
isFull). Add a method to display the stack and test your implementation with various
scenarios.

Assignment
Assignment 2: Reverse a String
Write a C++ program to reverse a string using a stack. Your program should take a string
as input and output the reversed string.
Example:

Input: "Hello World"

Output: "dlroW olleH"

Assignment
Assignment 3: Balanced Expressions
Extend the parentheses balancing program to handle expressions with parentheses, brackets,
and braces, and also validate if the operators and operands are properly balanced.
Example:

Input: "[(a+b)*(c-d)]" -> Valid

Input: "[(a+b)*(c-d)" -> Invalid
Input: "(a+b))" -> Invalid

Dr. Davies Rene Segera 12 Electrical & Information Engineering

 Image
University of Nairobi Stack Data Structure

Assignment
Assignment 4: Stack Sorting
Design an algorithm to efficiently sort a stack in ascending order. You can use additional
stacks if needed, but no other data structures. Implement and test your algorithm.

Assignment
Assignment 5: Queue using Stacks
Implement a Queue using two Stacks. Your implementation should include the basic queue
operations: enqueue, dequeue, front, and isEmpty.

10 References

References

[1] Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms
(3rd ed.). MIT Press.

[2] Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley Professional.

[3] Weiss, M. A. (2011). Data Structures and Algorithm Analysis in C++ (4th ed.). Pearson.

[4] Malik, D. S. (2010). C++ Programming: From Problem Analysis to Program Design (5th
ed.). Course Technology.

[5] TutorialsPoint. (n.d.). Data Structures and Algorithms - Stack. Retrieved from
https://www.tutorialspoint.com/data_structures_algorithms/stack_algorithm.htm

Dr. Davies Rene Segera 13 Electrical & Information Engineering