Stack – Data Structure

A stack is a linear data structure that follows the last in, first out rule, commonly written as LIFO. The most recently inserted element is the first one removed. All insertions, removals, and inspections take place at one end called the top of the stack.

A stack can be compared with a pile of plates. A new plate is placed on top, and the top plate must be removed before a plate below it can be reached.

How the Stack Data Structure Follows LIFO

Suppose the values 10, 20, and 30 are pushed into a stack in that order. The stack then appears as follows:

Top -> 30
       20
       10

A pop operation removes 30 because it was the last value inserted. The new top becomes 20.

Popped value: 30
New top: 20

An element in the middle of a stack cannot be removed directly. Every element above it must first be popped.

Stack Operations: Push, Pop, Peek, isEmpty, and Size

The main stack operations are:

• Push: Adds an element to the top of the stack.
• Pop: Removes and returns the top element.
• Peek or stack top: Returns the top element without removing it.
• isEmpty: Checks whether the stack contains no elements.
• Size or count: Returns the number of elements stored in the stack.

Push an Element onto the Stack

The push operation adds an item at the top of the stack. After the operation, the new item becomes the top element.

In an array-based stack with a fixed capacity, a push can fail when the array is full. This condition is called stack overflow. In a linked-list stack, a push normally fails only when memory for a new node cannot be allocated.

Pop the Top Element from the Stack

The pop operation removes the current top element. The element immediately below it then becomes the new top.

Attempting to pop from an empty stack produces a stack underflow condition. A stack implementation should report this condition instead of accessing invalid memory.

Peek at the Stack Top

The peek operation, also called stack top, returns the top element without deleting it. The number of elements and the structure of the stack remain unchanged.

Types of Stack Implementations

Stacks are commonly classified by how their storage is managed:

• Array stack: Stores elements in contiguous array positions. It is simple and cache-friendly, but a fixed-size array can become full.
• Dynamic array stack: Uses a resizable array. Most push operations are constant time, although resizing occasionally requires copying elements.
• Linked-list stack: Stores each element in a node and links it to the node below. It grows as memory permits and does not require a predetermined capacity.
• Call stack: A runtime-managed stack used to store active function calls, parameters, local variables, and return information.

Linked-List Stack Data Structures in C

In this tutorial, the stack is implemented as a linked list. Two structures are used: a data node and a stack header.

The stack header stores:

1. A pointer to the top node.
2. A count of the number of elements currently in the stack.

Each node contains a pointer to user data and a link to the next node below it.

typedef struct node {
	void* data;
	struct node* link;
}NODE;

The data node contains data along with a link pointer to the other nodes, it making it as self-referential structures.

typedef struct {
	int count;
	NODE* top;
}STACK;

Although the existing examples use the language-cpp class, the syntax shown is also valid C when the required headers are included.

Linked-List Stack Algorithms and C Implementations

Create and Initialize a Stack

The create-stack operation allocates memory for the stack header and initializes an empty stack.

1. Allocate memory for the stack header.
2. Set the element count to 0.
3. Set the top pointer to NULL.
4. Return the stack header.

Existing Create-Stack Implementation

STACK* createstack(void) {
	STACK* stack;
	stack=(STACK*) malloc(sizeof(STACK));
	if(stack)
	{
		stack->count=0;
		stack->top=NULL;
	}
	return stack;
}

A C program using this function should include <stdlib.h> for malloc and NULL.

Push a Node onto a Linked-List Stack

The steps for pushing a new node are:

1. Allocate memory for a new node.
2. Store the input data in the new node.
3. Set the new node link to the current top node.
4. Update the stack top to the new node.
5. Increment the stack count.

A push must handle three situations:

• Insertion into an empty stack.
• Insertion into a stack that already contains nodes.
• Failure to allocate memory for the new node.

Push-Stack Algorithm

1. Allocate a new node.
2. If allocation fails, return false.
3. Store the input data in the new node.
4. Link the new node to the current top.
5. Make the new node the stack top.
6. Increment the stack count.
7. Return true.

Existing Push-Stack Implementation

bool pushstack(STACK* stack,void* datain) {
	NODE* newptr;
	if(!newptr)
		return false;
	newptr->data=datain;
	newptr->link=stack->top;
	stack->top=newptr;
	(stack->count)++;
	return true;
}

In the existing function, newptr is checked before memory is allocated for it. A corrected implementation allocates the node first:

bool pushstack_fixed(STACK* stack, void* datain)
{
    if (stack == NULL)
        return false;

    NODE* newptr = malloc(sizeof(NODE));
    if (newptr == NULL)
        return false;

    newptr->data = datain;
    newptr->link = stack->top;
    stack->top = newptr;
    stack->count++;
    return true;
}

Pop a Node from a Linked-List Stack

A pop removes the top node, returns its data pointer, updates the top pointer, releases the node memory, and decrements the element count.

Pop-Stack Algorithm

1. If the stack is empty, return an empty result.
2. Save the data stored in the top node.
3. Save the address of the top node.
4. Move the top pointer to the next node.
5. Release the removed node.
6. Decrement the stack count.
7. Return the saved data.

Existing Pop-Stack Implementation

void* popstack(STACK* stack) {
	void* dataoutptr;
	NODE* temp;
	if(stack->count==0)
		dataoutptr=NULL;
	else
	{
		temp=stack->top;
		dataoutptr=stack->top->data;
		stack->top=stack->top->link;
		free(temp);
		(stack->top)--;
		
	}
	return dataoutptr;
	
}

The existing function decrements stack->top instead of stack->count. Decrementing a pointer after the removed node has been freed is incorrect. The corrected operation is:

void* popstack_fixed(STACK* stack)
{
    if (stack == NULL || stack->top == NULL)
        return NULL;

    NODE* temp = stack->top;
    void* dataoutptr = temp->data;

    stack->top = temp->link;
    free(temp);
    stack->count--;

    return dataoutptr;
}

Read the Stack Top without Removing It

The stack-top operation retrieves data from the top node without changing the top pointer or element count.

Stack-Top Algorithm

1. If the stack is empty, return an empty result.
2. Otherwise, return the data stored in the top node.

Existing Stack-Top Implementation

void* stacktop(STACK* stack) {
	if(stack->count==0)
		return NULL;
	else
		return stack->top->data;
	
}

For defensive programming, a production version should also verify that the stack pointer itself is not NULL.

Check Whether the Stack Is Empty

The empty-stack operation returns a Boolean result indicating whether the stack contains zero elements.

Empty-Stack Algorithm

1. If the stack count is 0, return true.
2. Otherwise, return false.

Existing Empty-Stack Implementation

bool emptystack(STACK* stack) {
	return (stack->count==0);
}

Determine Whether a Linked Stack Is Full

A linked-list stack does not have a fixed capacity. It is effectively full when memory for another node cannot be allocated. In practice, the push operation should detect allocation failure directly rather than allocating memory in a separate full-stack test.

Full-Stack Algorithm

1. Attempt to obtain memory for a node.
2. If memory is unavailable, return true.
3. Otherwise, release the test allocation and return false.

Existing Full-Stack Implementation

bool fullstack(STACK* stack) {
	NODE* temp;
	if((temp=(NODE*)malloc (sizeof(*(stack->top)))));
	{
		free(temp);
		return false;
	}
	return true;
}

The semicolon after the if condition in the existing function ends the condition immediately, so the following block always runs. A direct allocation check can be written as follows, although handling failure inside push remains preferable:

bool fullstack_fixed(void)
{
    NODE* temp = malloc(sizeof(NODE));

    if (temp == NULL)
        return true;

    free(temp);
    return false;
}

Return the Number of Stack Elements

The stack-count operation returns the number of elements currently stored.

Stack-Count Algorithm

1. Return the count stored in the stack header.

Existing Stack-Count Implementation

int stackcount(STACK* stack) {
	return stack->count;
}

Destroy a Linked-List Stack Safely

Destroying a stack requires visiting every node, releasing its memory, and finally releasing the stack header.

Destroy-Stack Algorithm

1. While the stack is not empty, save the top node.
2. Move the top pointer to the next node.
3. Release the saved node.
4. After all nodes are released, free the stack header.
5. Return NULL.

Existing Destroy-Stack Implementation

STACK* destroystack(STACK* stack)
{
	NODE* temp;
	if(stack) {
		while(stack->top!=NULL) {
			free(stack->top->data);
			temp=stack->top;
			stack->top=stack->top->link;
			free(temp);
		}
		free(stack);
	}
	return NULL;
}

The existing implementation assumes that the stack owns every object referenced by data. That assumption is not always valid. If the caller owns the stored data, the stack should free only its nodes:

STACK* destroystack_nodes_only(STACK* stack)
{
    if (stack != NULL)
    {
        while (stack->top != NULL)
        {
            NODE* temp = stack->top;
            stack->top = temp->link;
            free(temp);
        }

        free(stack);
    }

    return NULL;
}

When the stack owns dynamically allocated data, a destructor callback can be used so that each data object is released correctly.

Complete Linked-List Stack Example in C

The following example implements an integer stack with push, pop, peek, size, and cleanup operations.

#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct StackNode {
    int value;
    struct StackNode* next;
} StackNode;

typedef struct {
    StackNode* top;
    size_t size;
} IntStack;

void initialize_stack(IntStack* stack)
{
    stack->top = NULL;
    stack->size = 0;
}

bool push(IntStack* stack, int value)
{
    StackNode* node = malloc(sizeof(StackNode));
    if (node == NULL)
        return false;

    node->value = value;
    node->next = stack->top;
    stack->top = node;
    stack->size++;
    return true;
}

bool pop(IntStack* stack, int* value)
{
    if (stack->top == NULL)
        return false;

    StackNode* removed = stack->top;
    *value = removed->value;
    stack->top = removed->next;
    stack->size--;
    free(removed);
    return true;
}

bool peek(const IntStack* stack, int* value)
{
    if (stack->top == NULL)
        return false;

    *value = stack->top->value;
    return true;
}

void clear_stack(IntStack* stack)
{
    int discarded;
    while (pop(stack, &discarded))
    {
    }
}

int main(void)
{
    IntStack stack;
    int value;

    initialize_stack(&stack);

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

    if (peek(&stack, &value))
        printf("Top: %d\n", value);

    while (pop(&stack, &value))
        printf("Popped: %d\n", value);

    clear_stack(&stack);
    return 0;
}

The program produces:

Top: 30
Popped: 30
Popped: 20
Popped: 10

Stack Operation Time and Space Complexity

Stack operation	Array implementation	Linked-list implementation
Push	O(1), except occasional resizing in a dynamic array	O(1)
Pop	O(1)	O(1)
Peek	O(1)	O(1)
isEmpty	O(1)	O(1)
Size	O(1) when a count is stored	O(1) when a count is stored
Search	O(n)	O(n)

Both implementations require O(n) storage for n elements. A linked-list stack also stores one link pointer per node, while an array stack may reserve unused capacity.

Stack Overflow and Stack Underflow

• Stack overflow in an array stack: A push is attempted after the fixed-capacity array becomes full.
• Allocation failure in a linked stack: A new node cannot be created because memory allocation fails.
• Stack underflow: A pop or peek is attempted when no elements are present.
• Call-stack overflow: Too many nested or recursive function calls consume the runtime call-stack limit.

Applications of Stack Data Structures

Stacks are useful when processing must proceed in the reverse order of insertion or when a program needs to return to an earlier state.

• Function calls and recursion: Active calls are stored on the call stack until they return.
• Expression evaluation: Stacks are used to evaluate postfix expressions and convert between infix, prefix, and postfix notation.
• Parenthesis and syntax matching: Opening symbols are pushed and matched with closing symbols.
• Undo and redo: Editors can store previous actions so they can be reversed in LIFO order.
• Browser navigation: Previously visited pages can be stored for Back and Forward operations.
• Backtracking: Candidate states are stored so an algorithm can return to an earlier decision point.
• Depth-first search: An explicit stack can track vertices that remain to be explored.
• Reversing data: Items pushed in one order are popped in the opposite order.

Using a Stack to Reverse Data

When values are pushed in their original order and then popped, they are produced in reverse order. This property can be used to reverse characters, collections, or traversal results.

Using a Stack for Parenthesis Matching

A parser can push every opening parenthesis, bracket, or brace. When a closing symbol is found, the parser checks whether it matches the symbol at the stack top.

Parse Parenthesis Example

Parse parenthesis algorithm is for pairing the opening and closing parenthesis. If they are left alone,then it will display an error message according to the error.

Algorithm

1. loop(any data is there)
   1. read(character)
   2. if(opening parenthesis is there)
      1. push(stack,character)
   3. else
      1. if(closing parenthesis)
         1. if(emptystack(stack))
            1. print(closing paranthesis not matched)
         2. else
            1. popstack(stack)
         3. end if
      2. end if
   4. end if
2. end loop
3. if(not emptystack(stack))
   1. print(opening parenthesis not matched)

A complete parenthesis checker should also verify symbol type. For example, a closing square bracket must match an opening square bracket rather than any opening symbol.

Using a Stack for Postfix Expression Evaluation

In postfix notation, an operator appears after its operands. Each operand is pushed. When an operator is encountered, the required operands are popped, the operation is evaluated, and the result is pushed back.

Postfix-Evaluation Algorithm

1. create stack(stack)
2. loop(for each character)
   1. if(character is operand)
      1. pushstack(stack,character)
   2. else
      1. popstack(stack,oper2)
      2. popstack(stack,oper1)
      3. operator=character
      4. set value to calculate(oper1,operator,oper2)
      5. pushstack(stack,value)
3. end loop
4. popstack(stack,result)
5. return(result)

By implementing the above algorithm we will get sample input and output as:

• Sample input:52/4+5*2+
• Sample output:32

The sample treats each character as a single-digit operand. For multi-digit numbers, the expression must first be tokenized so that values such as 25 are read as one operand rather than two separate digits.

Using a Stack for Backtracking

Backtracking algorithms store previous decisions or states on a stack. When the current path cannot produce a solution, the most recent state is popped and another choice is tried.

The eight queens problem is one example. Eight queens must be placed on a chessboard so that no queen attacks another queen.

The algorithm attempts to place a queen in each row. When no safe column is available, it returns to the most recently placed queen, moves it, and continues the search.

Eight queen problem

Algorithm queens8(boardsize)

Position chess queen on a game board so that no queen can capture any other queen .

1. createstack(stack)
2. set row to 1
3. set col to 0
4. loop(row<=boardsize)
   1. loop(col<=boardsize and row<=boardsize)
      1. increment col
      2. if(not guarded(row,col))
         1. place queen at row-col intesection on board
         2. pushstack(row-col into stack)
         3. increment row
         4. set col to 0
      3. end if
      4. loop(col>=boardsize)
         1. popstack(row-col from stack)
         2. remove queen from row-col intersection on board
      5. end loop
   2. end loop
5. end loop
6. printboard(stack)
7. return

Stack and Queue Differences

Feature	Stack	Queue
Processing rule	Last in, first out	First in, first out
Insertion operation	Push at the top	Enqueue at the rear
Removal operation	Pop from the top	Dequeue from the front
Accessible end	One end	Two designated ends
Common applications	Recursion, undo, parsing, and backtracking	Scheduling, buffering, and breadth-first search

Stack Data Structure FAQs

Is a stack LIFO or FIFO?

A stack is LIFO: last in, first out. The most recently pushed element is the first element popped.

What is the stack rule in data structures?

The stack rule is that insertion and deletion occur only at the top. Elements below the top cannot be accessed directly without removing the elements above them.

What are the main stack operations?

The main operations are push, pop, peek, isEmpty, and size. Some implementations also provide clear, search, or capacity operations.

What are common applications of a stack?

Common applications include function-call management, recursion, expression evaluation, syntax matching, undo and redo, browser history, depth-first search, and backtracking.

Which is better for a stack: an array or a linked list?

An array is suitable when capacity is known or contiguous storage is preferred. A linked list is suitable when the stack should grow dynamically and the extra pointer memory per element is acceptable.

Stack Tutorial Editorial QA Checklist

• Confirm that LIFO is explained with insertion and removal at the stack top.
• Verify that push, pop, peek, isEmpty, and count are defined accurately.
• Check that stack overflow and underflow are distinguished correctly.
• Confirm that linked-list push allocates a node before writing to it.
• Verify that pop decrements the element count rather than modifying the top pointer arithmetically.
• Check that node ownership and stored-data ownership are explained before freeing data pointers.
• Compile newly added C examples with compiler warnings enabled and test empty-stack operations.
• Verify that stack and queue behavior are not confused in examples or complexity tables.