Image

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

DS
DATA STRUCTURES

EIE 210: Data Structures and Algorithms

Lecture Notes:

Stack Implementation in C++

Prepared by: Dr. Davies Rene Segera

Email: dsegera@uonbi.ac.ke
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 (EIE 110)

March 4, 2025
 Image
University of Nairobi Data Structures: Stack

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

• Understand the concept of a Stack data structure (LIFO/FILO principle)

• Describe standard operations on a stack (push, pop, peek, etc.)
• Implement a stack using arrays in C++
• Differentiate between stack overflow and stack underflow
• Write a menu-driven C++ program for stack operations

Dr. Davies Rene Segera 1 Electrical & Information Engineering

 Image
University of Nairobi Data Structures: Stack

Contents

1 Introduction 3

2 Visualizing the Stack 4

3 Approach to Implementing a Stack in C++ 5

4 Stack Operations in Detail 6

5 C++ Code Implementation 7

5.1 Explanation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

6 Example Run (Menu-Driven) 10

7 Key Observations and Tips 11

8 Practice Problems 12
8.1 Problem 1: Dynamic Stack Size . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
8.2 Problem 2: Stack Using Linked List . . . . . . . . . . . . . . . . . . . . . . . . . 12
8.3 Problem 3: Expression Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . 12

9 Conclusion 13

10 References and Further Reading 14

Dr. Davies Rene Segera 2 Electrical & Information Engineering

 Image
University of Nairobi Data Structures: Stack

1 Introduction

A stack is a fundamental data structure in computer science that follows a Last-In-First-Out

(LIFO) or First-In-Last-Out (FILO) access pattern. The most recent item placed on the stack is
always the first one to be removed.

Definition
Definition: A Stack is an ordered list in which insertion and deletion of items is possible
only at one end (called the top).

Stacks have numerous applications, such as:

• Function call management in operating systems (call stack)

• Undo/Redo mechanisms in text editors
• Expression evaluation and syntax parsing

ø Key Concepts
Key Concepts:

• The top pointer (or index) indicates the current highest (last) element.
• Push: Insert a new item on top.
• Pop: Remove the topmost item.
• Underflow: Attempt to pop from an empty stack.
• Overflow: Attempt to push onto a full stack.

Dr. Davies Rene Segera 3 Electrical & Information Engineering

 Image
University of Nairobi Data Structures: Stack

2 Visualizing the Stack

Top Index 4

Index 3 Push

Index 2 Pop

Index 1

Index 0

Figure 1: Stack Representation with 5 Positions

When the stack is empty, top is often initialized to -1 (indicating no valid index). As items
are pushed, top increments; as items are popped, top decrements.

Dr. Davies Rene Segera 4 Electrical & Information Engineering

 Image
University of Nairobi Data Structures: Stack

3 Approach to Implementing a Stack in C++

There are multiple ways to implement a stack:

• Using arrays (fixed size)

• Using dynamic allocation (flexible size)
• Using linked lists

In this set of notes, we focus on an array-based stack with a fixed maximum size (e.g., 5
elements). Our approach:

1. Create a class Stack with a private int array (size 5) and a private int top .

2. Initialize top = -1 in the constructor.

3. Push operation checks if the stack is full (top == 4), else increments top and assigns the
new value.
4. Pop operation checks if the stack is empty ( top == -1 ), else returns the current top
value and decrements top .
5. isEmpty, isFull help handle boundary conditions (underflow/overflow).
6. peek(i), change(i, val), count(), and display() provide additional functionality.
7. Menu-driven main program: Use a do-while or while loop with a switch for user
selections.

Dr. Davies Rene Segera 5 Electrical & Information Engineering

 Image
University of Nairobi Data Structures: Stack

4 Stack Operations in Detail

1. isEmpty(): Returns true if top == -1 , false otherwise.

2. isFull(): Returns true if top == size-1 , false otherwise.

3. push(int val):
• Check isFull() ; if full, print Stack Overflow.
• Otherwise, do top++ and arr[top] = val .
4. pop():
• Check isEmpty() ; if empty, print Stack Underflow.

• Otherwise, capture arr[top] into a temporary, set arr[top] to 0, then do top– and
return the captured value.
5. peek(int pos): Returns the value at index pos (does not remove it).

6. change(int pos, int val): Replaces the value at pos with val .

7. count(): Returns top + 1 (the number of elements currently on the stack).

8. display(): Prints the stack contents from top index down to zero index.

Dr. Davies Rene Segera 6 Electrical & Information Engineering

 Image
University of Nairobi Data Structures: Stack

5 C++ Code Implementation

Below is a simplified version of the code from the transcript, showing how to implement a
stack with all the operations described:
1 #include <iostream>
2 using namespace std;
3
4 class Stack {
5 private:
6 int arr[5]; // Fixed-size array for stack
7 int top; // Tracks the top element index
8
9 public:
10 // Constructor
11 Stack() {
12 top = -1;
13 for(int i = 0; i < 5; i++) {
14 arr[i] = 0;
15 }
16 }
17
18 // 1. Check if stack is empty
19 bool isEmpty() {
20 if(top == -1) return true;
21 else return false;
22 }
23
24 // 2. Check if stack is full
25 bool isFull() {
26 if(top == 4) return true;
27 else return false;
28 }
29
30 // 3. Push method
31 void push(int val) {
32 if(isFull()) {
33 cout << "Stack Overflow" << endl;
34 } else {
35 top++;
36 arr[top] = val;
37 }
38 }
39
40 // 4. Pop method
41 int pop() {
42 if(isEmpty()) {
43 cout << "Stack Underflow" << endl;
44 return 0;
45 } else {
46 int popValue = arr[top];
47 arr[top] = 0;
48 top--;
49 return popValue;
50 }
51 }
52
53 // 5. Count
54 int count() {
55 return (top + 1);
56 }
57
58 // 6. Peek

Dr. Davies Rene Segera 7 Electrical & Information Engineering

 Image
University of Nairobi Data Structures: Stack

59 int peek(int pos) {

60 if(isEmpty()) {
61 cout << "Stack Underflow" << endl;
62 return 0;
63 } else {
64 return arr[pos];
65 }
66 }
67
68 // 7. Change
69 void change(int pos, int val) {
70 arr[pos] = val;
71 cout << "Value changed at location " << pos << endl;
72 }
73
74 // 8. Display
75 void display() {
76 cout << "All values in the Stack are:" << endl;
77 for(int i = 4; i >= 0; i--) {
78 cout << arr[i] << endl;
79 }
80 }
81 };
82
83 // Main function
84 int main() {
85 Stack s1;
86 int option, position, value;
87
88 do {
89 cout << "What operation do you want to perform? Select Option. Enter 0 to exit."
<< endl;
90 cout << "1. Push()" << endl;
91 cout << "2. Pop()" << endl;
92 cout << "3. isEmpty()" << endl;
93 cout << "4. isFull()" << endl;
94 cout << "5. peek()" << endl;
95 cout << "6. count()" << endl;
96 cout << "7. change()" << endl;
97 cout << "8. display()" << endl;
98 cout << "9. Clear Screen" << endl << endl;
99
100 cin >> option;
101 switch(option) {
102 case 0:
103 break;
104 case 1:
105 cout << "Enter an item to push in the stack: ";
106 cin >> value;
107 s1.push(value);
108 break;
109 case 2:
110 cout << "Pop Function Called - Popped Value: " << s1.pop() << endl;
111 break;
112 case 3:
113 if(s1.isEmpty())
114 cout << "Stack is Empty" << endl;
115 else
116 cout << "Stack is not Empty" << endl;
117 break;
118 case 4:
119 if(s1.isFull())
120 cout << "Stack is Full" << endl;

Dr. Davies Rene Segera 8 Electrical & Information Engineering

 Image
University of Nairobi Data Structures: Stack

121 else
122 cout << "Stack is not Full" << endl;
123 break;
124 case 5:
125 cout << "Enter the position of item you want to peek: ";
126 cin >> position;
127 cout << "Peek Function Called - Value at position " << position << " is " <<
s1.peek(position) << endl;
128 break;
129 case 6:
130 cout << "Count Function Called - Number of Items in the Stack: " << s1.count()
<< endl;
131 break;
132 case 7:
133 cout << "Change Function Called - " << endl;
134 cout << "Enter position of item you want to change: ";
135 cin >> position;
136 cout << "Enter value of item you want to change: ";
137 cin >> value;
138 s1.change(position, value);
139 break;
140 case 8:
141 cout << "Display Function Called - " << endl;
142 s1.display();
143 break;
144 case 9:
145 system("cls"); // or system("clear") on some systems
146 break;
147 default:
148 cout << "Enter a valid option number." << endl;
149 }
150 } while(option != 0);
151
152 return 0;
153 }

Listing 1: Stack class with array-based implementation in C++

5.1 Explanation

• Stack() constructor: Initializes top = -1 and sets all array elements to 0.

• push(): Before inserting, checks if the stack is full. If not, increments top and places the
new element there.
• pop(): Before removing, checks if the stack is empty. If not, returns the topmost element,
resets that spot to 0, and decrements top.
• isEmpty() and isFull(): Simple checks on the top index to detect boundary conditions.
• count(): Returns the number of elements in the stack (top+1).
• peek(): Returns the item at a given position pos. Does not remove it.
• change(): Allows updating any position pos with a new value.
• display(): Prints all elements (from index 4 down to 0) so that the top appears first.
• main(): Provides a menu-driven interface, enabling a user to enter choices and interactively
call stack operations.

Dr. Davies Rene Segera 9 Electrical & Information Engineering

 Image
University of Nairobi Data Structures: Stack

6 Example Run (Menu-Driven)

 Example
Sample interaction:

What operation do you want to perform? Select Option. Enter 0 to exit.

1. Push()
2. Pop()
3. isEmpty()
4. isFull()
5. peek()
6. count()
7. change()
8. display()
9. Clear Screen

1
Enter an item to push in the stack: 10

1
Enter an item to push in the stack: 20

4
Stack is not Full

8
Display Function Called -
All values in the Stack are:
0
0
0
20
10

2
Pop Function Called - Popped Value: 20

8
Display Function Called -
All values in the Stack are:
0
0
0
0
10

...
0 <-- Exits the program

Dr. Davies Rene Segera 10 Electrical & Information Engineering

 Image
University of Nairobi Data Structures: Stack

7 Key Observations and Tips

. Important Note
• Stack Overflow occurs when pushing onto a full stack.
• Stack Underflow occurs when popping from an empty stack.
• Always check boundary conditions using isEmpty() and isFull() before performing
pop and push.
• The top index is crucial for fast insertions/removals in O(1) time (no shifting required
like in normal arrays).

⋆ Tips & Tricks

Advice for Testing:

• Test boundary scenarios:

a) Empty Stack: Pop or peek should give Underflow.
b) Full Stack: Push should give Overflow.
• Test normal conditions with push and pop to ensure elements are ordered correctly.
• Try changing values at valid and invalid positions.
• Observe the output of display() after every operation.

Dr. Davies Rene Segera 11 Electrical & Information Engineering

 Image
University of Nairobi Data Structures: Stack

8 Practice Problems

8.1 Problem 1: Dynamic Stack Size

Ñ Practice Problem
Modify the stack program to accept the size of the stack array at runtime (dynamic
allocation). Then implement the same operations:

• isEmpty(), isFull(), push(), pop(), display(), etc.

8.2 Problem 2: Stack Using Linked List

Ñ Practice Problem
Implement a stack using a singly linked list:

• No fixed maximum size (limited only by memory).

• Use a pointer top to the head of the list.
• push() inserts at the beginning.
• pop() removes from the beginning.

8.3 Problem 3: Expression Evaluation

Ñ Practice Problem
Using an array-based stack, write a program that evaluates a postfix arithmetic expression
(e.g., 3 4 + 5 *).

• Push numbers onto the stack.

• When an operator is encountered, pop two values, apply the operator, then push the
result back.

Dr. Davies Rene Segera 12 Electrical & Information Engineering

 Image
University of Nairobi Data Structures: Stack

9 Conclusion

In this lecture, we examined how to implement a stack data structure in C++ using a simple
array-based approach. Key points include:

• Stacks follow a LIFO model (Last In, First Out).

• Push and Pop are primary operations, each with O(1) complexity.
• Boundary checks with isEmpty() and isFull() prevent underflow/overflow errors.
• Additional operations like peek(), change(), and count() provide expanded utility.
• A menu-driven program enables user-friendly testing and demonstration.

⋆ Tips & Tricks

In upcoming lessons, we will compare stack implementations using linked lists, explore
stack applications such as reverse Polish notation parsing, and discuss advanced usage in
recursion.

Dr. Davies Rene Segera 13 Electrical & Information Engineering

 Image
University of Nairobi Data Structures: Stack

10 References and Further Reading

• Data Structures and Algorithms in C++ by Adam Drozdek

• Cplusplus.com for C++ language references
• GeeksforGeeks: Stack Data Structure for additional code examples

Dr. Davies Rene Segera 14 Electrical & Information Engineering