Data Structure - 6 Stack

The Stack slide the Data Structures course include:
1. Definition of stack
2. Characteristic of stack
3. Basic operation of stack
4. Push operation
5. Pop operation
6. Peek operation
7. Is-empty operation
9. Size operation
10. Applications of stack
11. Advantage of a stack
12. Disadvantage of a stack

1. Department of Informatics
Faculty of Industrial Engineering
Universitas Pembangunan Nasional “Veteran” Yogyakarta
Struktur
Data
Andi Nurkholis, S.Kom., M.Kom.
Stack: Concept
& Implementation
September 22, 2025

2. Definition of Stack
Stack is an abstract data type (ADT) that serves as a container for storing
elements based on the LIFO principle (Last In, First Out). This principle means
that the element most recently inserted into the stack will be the first one to be
removed. A simple real-life example is a stack of plates in the kitchen: the plate
placed on top last will be the first one taken.
Stack is a data structure that stores a collection of elements, with two main
operations:
üPush: Adds an element to the top of the stack.
üPop: Removes an element from the top of the stack.

3. Characteristic ofStack
1.Linear and Structured
2.LIFO (Last In, First Out) Principle
3.Operations Restricted to the Top
Element
4.Top as the Indicator of the Active
Position

4. Characteristic ofStack
5.Limited Capacity (in Array
Implementation)
6.Dynamic Capability (in Linked List
Implementation)
7.Abstract Structure with Broad
Applications

5. Characteristic of Stack
1.Linear and Structured: Stack is a sequential linear data structure, with access
limited to the top element. It is easy to understand but has limited flexibility.
2.LIFO (Last In, First Out) Principle: The last element inserted is the first to be
removed, with push and pop operations performed only at the top.
3.Operations Restricted to the Top Element: A stack only allows manipulation
at the top. To access inner elements, the top elements must be popped first,
reinforcing its closed nature.
4.Top as the Active Position Indicator: In a stack, the top variable marks the
top element. It increases when a push occurs and decreases when a pop
occurs, determining the position of the most recent element.

6. Characteristic of Stack
5.Limited Capacity (in Array Implementation): If a stack uses an array, its
capacity is limited to a fixed size; exceeding this limit is called stack overflow,
while attempting to delete from an empty stack is called stack underflow.
6.Dynamic Capability (in Linked List Implementation): A stack implemented
with a linked list has flexible capacity, limited only by memory. This makes it
more space-efficient, although its implementation is more complex.
7.Abstract Structure with Wide Applications: Despite its simplicity, a stack has
broad applications. With its LIFO characteristic, it is used for activity history,
recursive function calls, mathematical expression evaluation, and algorithm
management such as backtracking and pathfinding.

7. Basic Operation ofStack
1.Push
2.Pop
3.Peek
4.IsEmpty
5.Size

8. Push Operation
1.Check the stack condition to ensure that no stack overflow occurs and
sufficient memory is available.
2.Increment the top variable by one level to mark the new position for the
element.
3.Store new data at position indicated by top or in the newly created node.
4.Update the pointer so that top correctly points to the new element as the
topmost element.
5.Confirm the insertion: the stack now contains the additional data, ready to
be accessed or managed.

9. Pop Operation
1.Check the stack condition to ensure it is not empty; if it is empty, a stack
underflow occurs.
2.Retrieve the data at the top, which is the topmost element to be removed.
3.Decrement the top variable by one level, or move the top pointer to the
previous node.
4.Delete the old element from memory (if using a linked list, free the node
with free).
5.Confirm the deletion: the stack now has a new top element.

10. Peek Operation
1.Check the stack condition to ensure it is not empty; if it is empty, the peek
operation cannot be performed.
2.Identify the position of top, which is the topmost element indicated by the
top variable.
3.Access the data at the top without changing its position or removing the
element.
4.Return the data value of the top element to calling function or process.
5.Confirm the result of the access: the stack remains intact and unchanged
after the peek operation.

11. IsEmpty Operation
1.Check the top variable to determine position of the top element in stack.
2.Compare the value of top with the initial condition (for example, top == -1
in an array, or head == NULL in a linked list).
3.Evaluate the result of the comparison to determine whether the stack
contains elements or not.
4.Return a boolean value: true if stack is empty, false if it contains elements.
5.Confirm the stack status so that other operations (push/pop/peek) can be
safely performed according to the condition.

12. Size Operation
1.Initialize a counter variable to store the number of elements in the stack.
2.Check the stack condition; if it is empty, immediately return the value 0.
3.Calculate the number of elements either by reading the value of top + 1
(for an array) or by traversing the nodes one by one (for a linked list).
4.Store the result of the calculation in the variable size.
5.Return the value of size, allowing the system to know the total number of
elements currently in the stack.

13. Application of Stack
1.Function Calls and Recursion: One of the main applications of a stack is the
call stack, which stores return addresses, local variables, and supports the
execution of recursive functions such as factorial computation.
2.Mathematical Expression Evaluation: A stack plays an important role in
expression evaluation, enabling the conversion and calculation of infix,
postfix, and prefix expressions with proper operator precedence.
3.Undo and Redo in Applications: The undo/redo feature utilizes two stacks:
the undo stack stores the most recent actions to be reversed, while the redo
stack allows restoring actions that were previously undone.

14. Application of Stack
4.Depth-First Search (DFS) on Graphs: DFS algorithm uses a stack for graph
exploration, where initial node is pushed, then popped and marked, followed
by pushing its neighbors until stack becomes empty.
5.Balanced Symbol Checking: A stack is used to verify the balance of
parentheses: push when encountering an opening bracket, pop when
encountering a closing bracket, and the expression is valid if the stack is
empty—an essential process for compilers.
6.Memory Management and Operating Systems: In operating systems, stacks
store context switching, handle interrupts by saving the last execution
address, and hold function parameters called by programs.

15. Advantage of Stack
1.Simple & Efficient: The stack structure is easy to understand, with push and
pop operations having a time complexity of O(1).
2.Supports Recursion & Functions: Manages stack frames for return
addresses and local variables, which is essential in recursive function calls.
3.Expression Evaluation & Parsing: Assists in handling mathematical
expressions and syntax checking, such as verifying balanced parentheses.
4.Flexible & Practical: Supports undo/redo functionality in applications and
can be implemented using either arrays or linked lists as needed.

16. Disadvantage of Stack
1.Restricted Access: Only the top element can be accessed directly, unlike
arrays or linked lists.
2.Capacity & Overhead: Array-based implementations have limited capacity,
while linked lists are more flexible but require extra memory for pointers.
3.Application Limitations: The LIFO nature of stacks makes them unsuitable
for random access or FIFO requirements.
4.Risk of Deep Recursion: Excessive recursive calls may cause stack overflow
due to too many stored stack frames.

17. Department of Informatics
Faculty of Industrial Engineering
Universitas Pembangunan Nasional “Veteran” Yogyakarta
Andi Nurkholis, S.Kom., M.Kom.
September 22, 2025
Done
Thank
You