How to Implement a Stack in C With Code Examples

A stack represents a fundamental data structure built on the Last-In, First-Out (LIFO) principle. Imagine a stack of plates where you naturally add and remove from the top. In C programming, you’ll need to implement stack functionality yourself, as it’s not a built-in feature. This gives you direct control over how your stack behaves and performs. Stacks play a dual role in your programming toolkit: they quietly manage function calls through the system’s call stack, while serving as powerful algorithmic tools for expression evaluation and backtracking challenges.

This article will take you through a complete journey to understanding the stack in C programming. You’ll start by understanding the core operations such as push, pop, and peek, that define stack behavior. From there, you’ll build working implementations using two distinct approaches: array-based structures for fixed-size needs and dynamic linked lists for flexible memory management. You’ll also explore the performance characteristics and trade-offs of each method, equipping you with the knowledge to make informed architectural decisions based on your specific requirements and the practical scenarios where stacks deliver optimal solutions.

• A stack is a fundamental Last-In, First-Out (LIFO) data structure, meaning the last item added is the first one removed.
• C does not have a built-in stack type; you must implement it yourself, typically using either a fixed-size array or a dynamic linked list.
• The core operations that define any stack are push (add to top), pop (remove from top), and peek (view top).
• The array-based stack is generally faster due to better CPU cache locality, but it risks stack overflow errors.
• The linked-list-based stack is more flexible because its size is dynamic, but it has a small performance and memory overhead per element.
• Proper error handling is critical: always check for Stack Overflow before pushing to an array-based stack and Stack Underflow before popping or peeking from any stack.
• For linked lists, you must manually free the memory of popped nodes to prevent memory leaks.
• Stacks are used everywhere in computing, from managing function calls and browser history to enabling undo/redo functionality.

At its core, a stack maintains a collection of elements with strictly controlled access patterns. You can only interact with the element at the “top” of the stack, making it a restricted but highly predictable data structure. This limitation becomes a strength, providing clear behavioral guarantees that make stacks invaluable for specific computational tasks.

Stacks solve everyday programming problems in surprisingly simple ways. Some common examples include:

• Browser History: The “Back” button in your web browser works like a stack. Each page you visit is pushed onto the stack, and when you click “Back,” the most recent page is popped off.
• Undo/Redo Functionality: In applications like text editors or graphic design software, each action you take is pushed onto a stack. Hitting “Undo” pops the last action from the stack to reverse it.
• Function Call Stack: Programming languages use a stack to manage function calls. When a function is called, it’s pushed onto the call stack. When it finishes, it’s popped off, and control returns to the function below it.

Understanding how a stack works centers on mastering its fundamental operations. These operations define your stack’s behavior and provide the interface for manipulating the data it stores. Each operation follows the same LIFO principle we’ve been discussing, creating a consistent and predictable programming experience.

push()

The push operation is used to add a new element to the stack. This element is placed at the very top, becoming the new “topmost” item. Think of it as placing another book on top of a pile. This operation increases the stack’s size by one. In a fixed-size stack, it’s essential to first check if the stack is full to avoid a stack overflow, an error that occurs when there’s no space for the new element.

pop()

The pop operation performs two actions at once: it removes the topmost element from the stack and returns that element’s value. This is the only way to remove elements. After a pop, the element that was previously second from the top becomes the new top. If you try to pop from an empty stack, you’ll encounter a critical error known as a stack underflow, as there is no element to remove or return.

peek()

The peek operation (sometimes called top) allows you to inspect the value of the topmost element without removing it. It’s a read-only action, like looking at the title of the top book in a pile without lifting it off. This is incredibly useful when you need to know what the next item is to make a decision, but you aren’t ready to remove it from the stack yet. Like pop, attempting to peek at an empty stack will also result in a stack underflow.

isEmpty()

The isEmpty operation is a simple utility function that returns True if the stack contains zero elements and False otherwise. It serves as a crucial safety check. Before calling pop or peek, you should always use isEmpty to confirm the stack actually has an element to act upon, thereby preventing underflow errors and potential program crashes.

isFull()

The isFull operation is the counterpart to isEmpty. It checks if the stack has reached its maximum capacity and returns True if it has, and False if there is still room. This operation is only relevant for stacks with a fixed, predefined size, such as those implemented using an array. It acts as a guard for the push operation, allowing you to prevent stack overflow errors.

In summary:

These operations form your complete stack toolkit. Each one serves a specific purpose, and together they give you everything you need to implement stack-based solutions in your programs. The beauty lies in their simplicity—five straightforward operations that can solve surprisingly complex programming challenges.

One of the most straightforward ways to implement a stack is by using an array. This approach is simple to understand and efficient for many use cases. We use a static, fixed-size array to store the elements and an integer variable, often called top, to keep track of the last inserted element.

Explanation of the struct and Logic

To represent our stack, we’ll define a C struct. This structure will bundle together all the necessary components:

1. top: An integer that holds the index of the topmost element in the array. We initialize top to -1 to signify that the stack is initially empty.
2. capacity: An unsigned integer that stores the maximum number of elements the stack can hold. This is the fixed size of our array.
3. array: A pointer to an integer (int*). This pointer will point to the block of memory we dynamically allocate for our array, where the stack elements will be stored.

The core logic revolves around the top index:

• Push: When we add an element, we first increment top, then place the new element at array[top].
• Pop: When we remove an element, we retrieve the element from array[top] and then decrement top.
• Empty Check: The stack is empty if top is -1.
• Full Check: The stack is full if top is equal to capacity - 1.

This array-based implementation is highly efficient because accessing elements by their index is a very fast operation.

Here is a complete C program that defines an array-based stack and demonstrates its core operations in a main function.

#include <stdio.h>
#include <stdlib.h> // For malloc and free
#include <limits.h> // For INT_MIN

// A structure to represent a stack
struct Stack {
    int top;
    unsigned capacity;
    int* array;
};

// Function to create a stack of given capacity.
struct Stack* createStack(unsigned capacity) {
    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
    if (!stack) {
        return NULL; 
    }
    stack->capacity = capacity;
    stack->top = -1; 
    
    stack->array = (int*)malloc(stack->capacity * sizeof(int));
    if (!stack->array) {
        free(stack); 
        return NULL;
    }
    return stack;
}

int isFull(struct Stack* stack) {
    return stack->top == stack->capacity - 1;
}

int isEmpty(struct Stack* stack) {
    return stack->top == -1;
}

void push(struct Stack* stack, int item) {
    if (isFull(stack)) {
        printf("Stack Overflow\n");
        return;
    }
    stack->array[++stack->top] = item;
    printf("%d pushed to stack\n", item);
}

int pop(struct Stack* stack) {
    if (isEmpty(stack)) {
        printf("Stack Underflow\n");
        return INT_MIN;
    }
    return stack->array[stack->top--];
}

int peek(struct Stack* stack) {
    if (isEmpty(stack)) {
        printf("Stack is empty\n");
        return INT_MIN;
    }
    return stack->array[stack->top];
}

void freeStack(struct Stack* stack) {
    if (stack) {
        free(stack->array);
        free(stack); 
    }
}

int main() {
    struct Stack* stack = createStack(5);
    if (!stack) {
        printf("Failed to create stack.\n");
        return 1;
    }

    push(stack, 10);
    push(stack, 20);
    push(stack, 30);

    printf("\nTop element is %d\n", peek(stack));

    printf("%d popped from stack\n", pop(stack));
    printf("After popping, top element is %d\n\n", peek(stack));

    push(stack, 40);
    push(stack, 50);
    push(stack, 60); 
    
    push(stack, 70); // This will cause a stack overflow

    printf("\nPopping all elements:\n");
    while(!isEmpty(stack)) {
        printf("%d popped from stack\n", pop(stack));
    }

    pop(stack); // This will cause a stack underflow

    freeStack(stack);

    return 0;
}

The code uses a struct Stack to group three things: a pointer to an integer array (used to store the elements), the stack’s maximum size, and an index called top to track the most recent item. The createStack function allocates memory and sets top to -1 to show the stack is empty. To add an item, top is increased, and the item is stored at that position. To remove an item, the value at the current top index is returned, and then top is decremented. All stack operations are done by updating this top index, and the freeStack function cleans up the memory to avoid leaks.

Output:

10 pushed to stack
20 pushed to stack
30 pushed to stack

Top element is 30
30 popped from stack
After popping, top element is 20

40 pushed to stack
50 pushed to stack
60 pushed to stack
Stack Overflow

Popping all elements:
60 popped from stack
50 popped from stack
40 popped from stack
20 popped from stack
10 popped from stack
Stack Underflow

While an array is a simple way to build a stack, it has a significant limitation: a fixed size. We must define its capacity beforehand, which can lead to wasted memory or a "Stack Overflow" error if we exceed the limit.

A linked list provides a more flexible and dynamic solution. A linked list-based stack can grow and shrink as needed at runtime, limited only by the available system memory.

Explanation of the Node struct and Pointer Logic

The foundation of this implementation is the Node. Each node in our linked list will be a small structure containing two things:

1. data: The actual value (e.g., an integer) we want to store.
2. next: A pointer to the next Node in the stack.

To manage the stack, we only need a single pointer, let’s call it top. This top pointer always points to the head of the linked list, which represents the most recently added element. If top is NULL, the stack is empty.

The logic for the stack operations becomes about manipulating the head of the list:

• push:
  1. Create a new node.
  2. Set the next pointer of this new node to point to the current top node.
  3. Update the top pointer to point to our newly created node.
• pop:
  1. Check if the stack is empty (top == NULL).
  2. Store the data from the top node to be returned later.
  3. Create a temporary pointer to the top node so we don’t lose it.
  4. Move the top pointer to the next node in the list (top = top->next).
  5. Free the memory of the original top node using the temporary pointer.
• isEmpty: The stack is empty if top is NULL.
• isFull: This concept doesn’t apply. The stack is never “full” in the traditional sense. A push operation only fails if the system runs out of memory (malloc returns NULL).

The following C program implements a stack using a linked list and demonstrates its core functions.

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

struct StackNode {
    int data;
    struct StackNode* next;
};

struct StackNode* newNode(int data) {
    struct StackNode* stackNode = (struct StackNode*)malloc(sizeof(struct StackNode));
    if (!stackNode) {
        printf("Heap Overflow\n");
        return NULL;
    }
    stackNode->data = data;
    stackNode->next = NULL;
    return stackNode;
}

int isEmpty(struct StackNode* top) {
    return !top;
}

void push(struct StackNode** top_ref, int data) {
    struct StackNode* stackNode = newNode(data);
    if (!stackNode) return; 

    stackNode->next = *top_ref; 
    *top_ref = stackNode;      
    printf("%d pushed to stack\n", data);
}

int pop(struct StackNode** top_ref) {
    if (isEmpty(*top_ref)) {
        printf("Stack Underflow\n");
        return INT_MIN; 
    }
    struct StackNode* temp = *top_ref; 
    int popped = temp->data;           
    *top_ref = (*top_ref)->next;       
    
    free(temp); 
    
    return popped;
}

int peek(struct StackNode* top) {
    if (isEmpty(top)) {
        printf("Stack is empty\n");
        return INT_MIN; 
    }
    return top->data;
}

int main() {
    struct StackNode* top = NULL;

    push(&top, 10);
    push(&top, 20);
    push(&top, 30);

    printf("\nTop element is %d\n", peek(top));

    printf("%d popped from stack\n", pop(&top));

    printf("Top element is now %d\n", peek(top));
    
    printf("\nPopping all elements...\n");
    while(!isEmpty(top)) {
        printf("%d popped from stack\n", pop(&top));
    }

    pop(&top);

    return 0;
}

This code builds a stack using a linked list of StackNode structures. The top pointer always points to the first node, which holds the most recent item. If top is NULL, the stack is empty. To push an item, a new node is created and added to the front of the list. To pop, top is moved to the next node, and the old node is freed from memory. This approach allows the stack to grow and shrink as needed, using only as much memory as required.

Output:

10 pushed to stack
20 pushed to stack
30 pushed to stack

Top element is 30
30 popped from stack
Top element is now 20

Popping all elements...
20 popped from stack
10 popped from stack
Stack Underflow

Choosing between an array-based and a linked list-based stack depends entirely on the specific requirements of your application. Each implementation has distinct trade-offs in terms of memory, flexibility, and performance.

Trade-offs: A Direct Comparison

This table summarizes the key differences between the two approaches.

Performance Considerations

While both implementations are highly efficient, there are subtle but important performance differences to consider.

Big O Notation

The primary stack operations (push, pop, and peek) are all O(1) (constant time) operations in both array and linked list implementations.

• Array-Based: Operations only involve accessing the element at the top index. This is a direct memory access, which takes the same amount of time regardless of the stack’s size.
• Linked List-Based: Operations only involve manipulating the top node (the head of the list). Since we always have a direct pointer to the head, we never need to traverse the list. This also takes a constant amount of time.

Theoretically, in terms of complexity, both are equally fast.

Cache Locality

The significant performance difference comes from cache locality. Modern CPUs use a small, fast memory cache to speed up access to frequently used data. It’s much faster for a CPU to access data that is stored sequentially in memory (good cache locality) than data that is scattered randomly.

• Array-Based Stack: This implementation has excellent cache locality. Since the entire stack is stored in one contiguous block of memory, when one element is accessed, its neighbors are often loaded into the CPU cache automatically. This makes subsequent operations on nearby elements extremely fast.

• Linked List-Based Stack: This implementation typically has poor cache locality. Each node is allocated separately on the heap and can reside anywhere in memory. Accessing the next node in memory (top = top->next) can still result in a cache miss.

While both are O(1) on paper, the array-based stack is often faster in practice due to its superior cache locality. If you can predict the maximum size of your stack and performance is critical, an array is usually the better choice. If you need dynamic sizing and cannot risk a stack overflow, a linked list is the safer, more flexible option.

Writing a correct stack implementation goes beyond just the basic logic. Paying attention to edge cases and memory management is crucial for creating robust, bug-free code.

Common Mistakes to Avoid

Many of the bugs in stack implementations stem from a few common, easy-to-make errors. Here’s what to watch out for.

Off-by-One Errors in the top Index

This is the most frequent bug in array-based stacks. Since arrays are 0-indexed, the top variable must be managed precisely.

• Initialization: top should be initialized to -1, not 0. This correctly signifies an empty stack. Starting at 0 implies there is already one element at index 0.
• Full Check: A stack is full when top is equal to capacity - 1, not capacity. Forgetting the -1 leads to attempting to write one element past the allocated memory boundary.
• Push/Pop Order: Confusing pre-increment (++top) with post-increment (top++) can be disastrous. The correct logic is to increment top before adding the element (stack[++top] = item;) and to decrement top after retrieving the element (item = stack[top--];).

Forgetting to Check for Stack Overflow/Underflow

These checks are not optional suggestions; they are critical for program stability.

• Stack Overflow: Attempting to push an element onto a full array-based stack will write data out of bounds. This is a classic buffer overflow, which can corrupt adjacent memory, leading to unpredictable crashes and creating serious security vulnerabilities.
• Stack Underflow: Attempting to pop or peek from an empty stack is even more immediately fatal. It results in trying to access an invalid memory address (e.g., array[-1] or NULL->data), causing a segmentation fault that will crash your program instantly.

Memory Leaks in Linked Lists

This mistake is specific to linked list-based stacks. Every push operation allocates memory with malloc(). It is your responsibility to free that memory during a pop.

• The Error: A common mistake is to simply move the top pointer to the next node (top = top->next;) and forget about the original top node. When you do this, the pointer to the old node is lost, but its memory remains allocated. This is a memory leak. Over time, repeated leaks will consume all available memory and crash the application.
• The Fix: Always use a temporary pointer to hold the current top node, advance the real top pointer, and then call free() on the temporary pointer.

Dereferencing NULL Pointers

This is the primary danger in a linked list implementation. Dereferencing a NULL pointer, i.e., trying to access a member of a pointer that is NULL (e.g., NULL->data), causes an immediate program crash.

• How it Happens: This most often occurs when you call pop() or peek() on an empty stack where top is already NULL. The isEmpty() check is your first line of defense.
• Another Cause: It can also happen if malloc() fails to allocate memory (returns NULL) and your code doesn’t check for this failure before trying to use the newly created node.

Best Practices for Robust Stack Code

Following established conventions and practices will make your code more reliable, reusable, and easier for others to understand.

• Consistent Error Handling: Decide on a single, consistent strategy for handling errors like underflow or memory allocation failures. For example, you could have pop and peek return a special value like INT_MIN on error. Another approach is to pass a pointer for an error code variable to your functions. The key is consistency. Mixing different error-handling methods (returning error codes, printing to the console, and exiting) makes your stack API unpredictable and difficult for other programmers to use correctly.

• Using unsigned for Capacity/Size: A stack’s capacity or element count can logically never be negative. Representing these values with a standard int is inefficient and less clear. Instead, use an unsigned int or, even better, size_t. The size_t type is the standard C type for sizes of objects and memory regions. Using it clearly communicates that the value represents a size and is non-negative, making your code’s intent more explicit and robust.

• Writing Modular Code: Don’t write your entire program in one file. Separate the stack’s implementation from its usage. The standard practice is to place the struct definition and function declarations (the API) in a header file (e.g., stack.h). The actual code for those functions goes into a source file (e.g., stack.c). Any program that needs to use your stack can then simply #include "stack.h". This promotes reusability, improves maintainability, and provides a clean abstraction layer—the user of your stack shouldn’t have to care if it’s implemented with an array or a linked list.

1. What is a stack in C programming?

A stack in C is a conceptual data structure, not a built-in type. It stores a collection of elements and operates on a Last-In, First-Out (LIFO) principle. This means the last element added to the stack is the first one to be removed. Think of it as a stack of plates; you add new plates to the top and also remove them from the top. You implement it yourself using an array or a linked list, creating functions like push() to add items and pop() to remove them.

2. Which is better: stack with array or linked list?

Neither is universally “better”; the best choice depends on your needs:

• Use an array-based stack if you can estimate the maximum number of elements and performance is critical. Arrays offer better cache locality, making them faster in practice, but they have a fixed size and risk “stack overflow.”
• Use a linked-list-based stack if you need a dynamic size that can grow or shrink and you want to avoid overflow errors. This offers more flexibility but has a small memory and performance overhead for pointers with each element.

3. How to prevent stack overflow in C?

You can prevent overflow in an array-based stack by always checking if the stack is full before pushing a new element. Implement and use an isFull() function that checks if top == capacity - 1. If it’s full, you refuse to push the element. Alternatively, use a linked-list implementation, which doesn’t have this overflow problem.

4. What is stack vs queue in C?

A stack and a queue are both abstract data structures, but they follow opposite principles.

• Stack (LIFO): Last-In, First-Out. Like a stack of plates. You add to the top (push) and remove from the top (pop).
• Queue (FIFO): First-In, First-Out. Like a checkout line. You add to the back (enqueue) and remove from the front (dequeue).

5. What is stack or heap in C?

The stack and heap are two different regions of memory where a C program stores its data. They should not be confused with the stack data structure.

• The Stack (Call Stack): This is a region of memory used for static allocation. It’s highly organized and managed automatically by the compiler to store local variables and function call information. It’s very fast but limited in size.
• The Heap: This is a large pool of memory used for dynamic allocation. You must manage it manually using functions like malloc() and free(). It’s more flexible and much larger than the stack but slightly slower to access.

Our linked-list-based stack implementation stores its nodes on the heap. An array-based stack can be declared locally (on the call stack) or dynamically (on the heap) depending on how it is created.

6. Can a stack be implemented with a dynamic array?

Yes, and it’s an excellent hybrid approach. A dynamic array starts with an initial capacity. When a push operation occurs on a full stack, the implementation automatically:

1. Allocates a new, larger array (e.g., double the size).
2. Copies all elements from the old array to the new one.
3. Frees the old array.
4. Adds the new element.

This provides the performance benefits of contiguous memory like an array while offering the flexible, growing nature of a linked list.

7. What is the difference between pop and peek?

The difference is whether the stack is modified.

• pop(): Removes the topmost element from the stack and returns its value. It is an operation that changes the stack’s state.
• peek(): Returns the value of the topmost element without removing it. It is a read-only operation that leaves the stack unchanged.

8. Why is stack overflow a problem in arrays but not linked lists?

Stack overflow is an issue specific to fixed-size data structures.

• Array-based stacks have a fixed capacity defined at creation. Once you’ve pushed capacity number of elements, the array is full. Trying to push one more element causes an “overflow” because there is no allocated space for it.
• Linked-list-based stacks do not have a predefined capacity. When you push a new element, they dynamically allocate memory for a new node. They can continue to grow as long as there is available system memory on the heap. Therefore, they don’t “overflow” in the traditional sense; they can only fail if the entire system runs out of memory.

Learning how to implement a stack in C is a great way to build skills in memory management, performance trade-offs, and clean code design. This article took you through everything: from the basic LIFO concept to building stacks from scratch.

We covered two main methods: the fast but fixed-size array-based stack, and the more flexible linked list-based stack. Along the way, you learned how to compare their performance, manage memory safely, and avoid common mistakes. With these skills, you’re now ready to write stack code that’s both efficient and reliable—an important step toward mastering more advanced data structures and real-world programming.

Ready to keep learning? Now that you understand stacks, expand your C programming skills with these excellent articles:

• How to Create a Queue in C (With Code Examples)
• Initialize an Array in C
• fgets() and gets() in C Programming