Stack in C
FREE
Overview
In C, a Stack is a linear data structure that follows the LIFO (Last In First Out) approach to perform a series of basic operations like push, pop, peek, and traverse. A Stack can be implemented using an Array or Linked List.
Introduction to Stack in C
A Stack is an abstract linear data structure serving as a collection of elements that are inserted (push operation) and removed (pop operation) according to the Last in First Out (LIFO) approach. Insertion and deletion happen on the same end (top) in a Stack. The top of the stack is returned using the peek operation.
Notes: An abstract data type has some associated operations (like Push and Pop in stack), while its representation remains hidden.
Scaler Placement Report and Statistics
Scaler learners achieved 2.5x salary growth with average post-Scaler CTC reaching ₹23L.
What is the Stack Data Structure in C?
In C, the Stack data structure is an ordered, linear sequence of items. It is a LIFO (Last In First Out) data structure, which means that we can insert or remove an item at the top of the stack only. It is a sequential data type, unlike an array. In an array, we can access any of its elements using indexing, but we can only access the top most element in a stack.
The name "Stack" for this data structure comes from the analogy to a set of physical items stacked on top of each other. An example of this data structure would be a stack of plates: We can only add a plate to the top of the stack and take a plate from the top of the stack. A stack of coins or a stack of books can also be a real-life example of the stack data structure.
Types of Stack Data Structure
There are two commonly used types of stack in C:
-
Static Stack
-
Dynamic Stack
Static Stack
A Static Stack is generally implemented using an array and has a fixed capacity. Since the size is predefined, the stack can store only a limited number of elements. If we try to insert more elements after reaching the maximum capacity and the stack is full, it enters an overflow state, causing stack overflow.
A static stack is simple to implement, works well when the maximum size is known in advance, and is often memory-efficient. However, its fixed-size limit cannot expand and can cause overflow if exceeded.
Dynamic Stack
A Dynamic Stack can grow or shrink during runtime. It is generally implemented using a linked list and dynamic memory allocation. In this approach, each stack element is stored inside a node, and a pointer called top points to the first node.
A dynamic stack does not have a fixed size limit in advance, so it is more flexible. However, it uses extra memory for pointers and may consume more memory than an array-based stack.
How Stack Works in C
To understand how a stack works in C, we use a variable called top.
-
In an array implementation, top stores the index of the topmost element.
-
In a linked list implementation, top stores the address of the first node.
Initial State of Stack
When the stack is empty:
-
in array implementation, top = -1
-
in linked list implementation, top = NULL
Working of Push, Pop, and Peek
During a push operation, a new element is inserted at the top, and the top pointer or index is updated. During a pop operation, the topmost element is removed, and top moves to the next valid element. During a peek operation, the current top element is returned without removing it.
Since all these operations happen only at one end, stack operations are very fast.
Stack Operations in C
A stack supports several important operations.
1. Push Operation
The push operation is one of the basic operations that inserts a new element onto the top of the stack. After insertion, the element added becomes the new top element and the top pointer or index is updated.
2. Pop Operation
The stack pop operation removes the topmost element from the stack and returns it. After removal, the returned value is the popped item, and the next element becomes the new top. If pop is performed on an empty stack, stack underflow occurs.
Scaler Placement Report and Statistics
Scaler learners achieved 2.5x salary growth with average post-Scaler CTC reaching ₹23L.
3. Peek Operation
The peek operation returns the top element, that is, the element of the stack currently at the top, without removing it. It is useful when we want to inspect the current top value while keeping the stack unchanged.
Transform Your Career
Choose from our industry-leading programs designed for career success
Modern Software and AI Engineering Program
Master full-stack development with AI integration
+1000 moreModern Data Science and ML with specialisation in AI
Advanced data science techniques with AI specialization
+1000 moreAdvanced AIML with Specialisation in Agentic AI
Deep dive into AIML with focus on Agentic systems
+1000 moreDevOps, Cloud & AI Platform Engineering
Build and manage AI-powered cloud infrastructure
+1000 moreAI Engineering Advanced Certification by IIT-Roorkee
Premier AI engineering certification from IIT-Roorkee
4. isEmpty Operation
The isEmpty operation checks whether the stack contains any elements.
-
in array implementation, the stack is empty when top == -1
-
in linked list implementation, the stack is empty when top == NULL
5. isFull Operation
The isFull operation checks whether the stack has reached its maximum capacity. This operation mainly applies to array-based stacks.
6. Traverse Operation
The traverse or display operation prints all the elements of the stack, usually from top to bottom.
Time Complexity of Stack Operations
One of the biggest advantages of the stack in C is that most operations take constant time.
| Operation | Time Complexity |
|---|---|
| Push | O(1) |
| Pop | O(1) |
| Peek | O(1) |
| isEmpty | O(1) |
| isFull | O(1) |
Why is the Time Complexity O(1)?
All stack operations happen only at the top of the stack, so there is no need to traverse the entire structure. That is why push, pop, and peek are all highly efficient.
Implementing Stack in C
There are two standard ways to implement a stack in C:
-
using an array
-
using a linked list
These two implementations are the most common forms of stack implementation in C.
Stack Program in C using Array
We will be using an array to implement a Static Stack (Bounded Stack) as arrays are static in C.
A Static Stack has a bounded capacity. A static stack is called to be in an Overflow State if it is full (no elements can be further pushed into it).
Implementation
Output
In the above example, we are implementing a static stack with a capacity of 1000 in C using an array. The static stack performs the following operations: Push, Pop, Peek, isEmpty, and isFull. The program stops when the user chooses 0 as an option.
Stack Program in C using Linked List
We will be using a linked list to implement a Dynamic Stack as linked lists are dynamic data stuctures.
A Dynamic Stack does not have a bounded capacity, we can push as much as elements as we want into it.
Implementation:
Output
In the above example, we are implementing a dynamic stack in C using a linked list. The dynamic stack performs the following operations: Push, Pop, Peek, and isEmpty. The program stops when the user chooses as an option.
Applications of Stack in C
Stacks have many practical applications in programming and algorithms.
1. Function Call Management
Whenever a function is called, the system stores local variables, function parameters, return addresses, and execution state in the function call stack used in many programming languages, so execution returns correctly after each call.
2. Recursion
Recursive functions depend heavily on stacks because every recursive call creates a new stack frame.
3. Expression Conversion
Stacks are used to convert expressions such as:
-
Infix to Postfix
-
Infix to Prefix
-
Postfix to Infix
-
Prefix to Infix
4. Expression Evaluation
Stacks help evaluate postfix and prefix expressions efficiently while maintaining operator precedence.
Turn Learning into Career Growth
5. Parenthesis and Bracket Checking
Stacks are commonly used to check balanced symbols such as:
-
()
-
{}
-
[]
6. Compiler Syntax Parsing
Compilers use stacks to parse expressions and nested program structures.
7. Undo and Redo Operations
Text editors use stacks to implement undo and redo functionality.
8. Browser Back Button
Web browsers can maintain previously visited pages using stacks.
9. Backtracking Algorithms
Stacks are useful in problems such as maze solving, puzzle solving, and path exploration.
10. Depth First Search
Depth First Search (DFS) uses stacks to explore a graph path deeply before backtracking.
Advantages of Stack in C
A stack in C offers several advantages:
-
easy to understand and implement
-
operations are fast
-
most operations take O(1) time
-
useful in recursion and function calls
-
helpful in expression evaluation and compiler design
-
ideal for DFS and backtracking
-
can be implemented using arrays or linked lists
Disadvantages of Stack in C
A stack also has some limitations:
-
only the top element is directly accessible
-
array implementation has fixed size
-
linked list implementation uses extra memory
-
stack overflow may occur in static stacks
-
stack underflow may occur when popping from an empty stack
Common Errors in Stack
Stack overflow occurs when an insertion is attempted on a full stack.
Stack underflow occurs when deletion is attempted on an empty stack.
Both conditions should always be checked before performing push or pop operations.
Important Points to Remember
-
A stack is a linear data structure
-
It follows the LIFO principle
-
Insertion and deletion happen at the same end
-
top keeps track of the topmost element
-
Static stacks use arrays
-
Dynamic stacks use linked lists
-
Push and pop operations take O(1) time
Conclusion
A stack in C is one of the most important and widely used data structures in programming. It follows the Last In First Out (LIFO) principle, where insertion and deletion take place only from the top.
To summarize:
-
a stack is a linear data structure
-
it follows the LIFO rule
-
main operations include push, pop, peek, isEmpty, and isFull
-
stacks can be implemented using arrays or linked lists
-
array implementation is simple and memory-efficient
-
linked list implementation is flexible and dynamic
-
major operations take O(1) time
-
stacks are heavily used in recursion, compiler design, expression evaluation, DFS, browser history, undo/redo systems, and backtracking
Understanding the stack data structure in C builds a strong foundation for advanced data structures and algorithms.
FAQs on Stack in C
1. What is stack in C?
A stack in C is a linear data structure where insertion and deletion occur only from one end called the top. It follows the LIFO principle.
2. What are the main stack operations?
The main stack operations are:
-
push
-
pop
-
peek
-
isEmpty
-
isFull
3. What is stack overflow?
Stack overflow occurs when an element is pushed into a full stack.
4. What is stack underflow?
Stack underflow occurs when pop is performed on an empty stack.
5. How is stack implemented in C?
A stack in C can be implemented:
-
using arrays
-
using linked lists
6. What is the time complexity of push and pop?
Both push and pop operations take O(1) time.
7. What are the applications of stack in C?
Stacks are used in:
- function call stack
- recursion
- expression evaluation
- expression conversion
- bracket checking
- compiler parsing
- undo/redo systems
- browser history
- backtracking
- depth first search
Google
Amazon
Microsoft
Flipkart
Adobe1200+ more