CO2402 Advanced Programming with C++ Lecture 5 Notes

CO2402: Advanced Programming
with C++ Lecture 5


Introduction to Stacks

1. What is a Stack?

o A stack is a linear data structure that follows the Last In, First
Out (LIFO) principle. It allows elements to be added and
removed only from one end, known as the "top" of the stack.

o Metaphor: A stack of plates where you can only add or
remove the top plate.

2. Importance of Stacks

o Stacks are fundamental in computer science and are used in
various applications, including:
o Call Stack: Manages function calls and returns in most
programming languages.
o Depth-First Search: A graph traversal algorithm.
o Infix to Postfix/Prefix Conversion: In arithmetic
expression parsing.
o Undo/Redo Features: Common in editors and browsers.



Implementing a Stack in C++

1. Basic Structure
o Data Representation: A stack can be implemented using an
array. The array stores the elements, and an integer
variable keeps track of the stack's top position.