Stack Operations

A stack is a linear data structure that operates on the Last In, First Out (LIFO) principle. All operations are performed at one end called the TOP. The TOP keeps track of the most recently inserted element, and every insertion or deletion happens only at this position.

Understanding stack operations is essential because they define how data is stored, accessed, and removed in a controlled manner.

List of Stack Operations

The fundamental operations that govern the working of a stack are:

• push() – Used to insert an element onto the top of the stack
• pop() – Used to remove the top element from the stack
• peek() / top() – Used to view the top element without removing it
• isEmpty() – Used to check whether the stack is empty
• isFull() – Used to check whether the stack is full (in array implementation)
• size() – Used to determine the number of elements in the stack
• display() – Used to print all elements of the stack (from top to bottom)

Each of these operations plays a specific role in maintaining the structure and behavior of the stack. Together, they provide a complete interface for performing insertion, deletion, and access operations efficiently.

1. PUSH Operation (Insertion of Element)

The push operation is used to insert a new element into the stack. When an element is pushed, it is always placed at the top of the stack, making it the most recent element.

Before performing a push operation, it is necessary to check whether the stack has space available. If the stack is already full and we try to insert another element, it leads to a condition known as stack overflow.

Key Points

• Adds element at the TOP
• Increases the TOP pointer
• Requires overflow checking

Algorithm

if TOP == MAX - 1 then
   print "Stack Overflow"
else
   TOP = TOP + 1
   STACK[TOP] = item
end if

Example

Suppose MAX = 3

• Initial: STACK = [ ], TOP = -1
• push(10) → STACK = [10], TOP = 0
• push(20) → STACK = [10, 20], TOP = 1
• push(30) → STACK = [10, 20, 30], TOP = 2

Now, pushing another element will cause overflow.

2. POP Operation (Deletion of Element)

The pop operation removes the topmost element from the stack. Since the stack follows LIFO, the last inserted element is the first one to be removed.

Before performing a pop operation, we must ensure that the stack is not empty. If we attempt to remove an element from an empty stack, it results in stack underflow.

Key Points

• Removes element from TOP
• Decreases the TOP pointer
• Requires underflow checking

Algorithm

if TOP == -1 then
   print "Stack Underflow"
else
   item = STACK[TOP]
   TOP = TOP - 1
   return item
end if

Example

• STACK = [10, 20, 30], TOP = 2
• pop() → removes 30
• New STACK = [10, 20], TOP = 1

3. PEEK Operation (Access Top Element)

The peek operation is used to view the top element of the stack without removing it. This operation is useful when we want to know the most recent element but do not want to modify the stack.

Key Points

• Does not modify stack
• Returns top element only
• Requires empty check

Algorithm

if TOP == -1 then
   print "Stack is Empty"
else
   return STACK[TOP]
end if

Example

• STACK = [10, 20, 30], TOP = 2
• peek() → returns 30
• Stack remains unchanged

4. isEmpty Operation (Check Empty Stack)

The isEmpty operation checks whether the stack contains any elements. It is commonly used before performing pop or peek operations to prevent errors.

A stack is considered empty when the TOP pointer is equal to -1.

Key Points

• Used for safety checking
• Prevents underflow
• Returns boolean result

Algorithm

if TOP == -1 then
   return TRUE
else
   return FALSE
end if

Example

• TOP = -1 → Stack is empty
• TOP = 2 → Stack is not empty

5. isFull Operation (Check Full Stack)

The isFull operation determines whether the stack has reached its maximum capacity. This operation is especially important in array-based stack implementations.

If the TOP pointer reaches the last index of the array, the stack is considered full.

Key Points

• Prevents overflow
• Used before push()
• Applicable in fixed-size stacks

Algorithm

if TOP == MAX - 1 then
   return TRUE
else
   return FALSE
end if

Example

For MAX = 5:

• TOP = 4 → Stack is full
• TOP = 3 → Stack is not full

6. SIZE Operation (Number of Elements)

The size operation returns the total number of elements currently present in the stack. Since indexing starts from 0 and TOP starts from -1, the number of elements is always TOP + 1.

Key Points

• Simple calculation
• No traversal needed
• Works in constant time

Algorithm

return TOP + 1

Example

• TOP = -1 → Size = 0
• TOP = 0 → Size = 1
• TOP = 2 → Size = 3

Stack Implementation in C – All Operations

A stack can be implemented using different methods, but one of the most common approaches is using an array. In this implementation, we use an array to store elements and a variable called TOP to keep track of the current top position of the stack.

Initially, the stack is empty, so TOP is set to -1. As elements are added or removed, the value of TOP changes accordingly.

#include <stdio.h>
#define MAX 5   // Maximum size of stack

int stack[MAX];   // Stack array
int top = -1;     // Initially stack is empty

// Check if stack is full
int isFull() {
    if (top == MAX - 1)
        return 1;
    else
        return 0;
}

// Check if stack is empty
int isEmpty() {
    if (top == -1)
        return 1;
    else
        return 0;
}

// PUSH operation
void push(int item) {
    if (isFull()) {
        printf("Stack Overflow! Cannot insert %d\n", item);
    } else {
        top = top + 1;
        stack[top] = item;
        printf("%d pushed into stack\n", item);
    }
}

// POP operation
int pop() {
    if (isEmpty()) {
        printf("Stack Underflow! Cannot remove element\n");
        return -1;
    } else {
        int item = stack[top];
        top = top - 1;
        printf("%d popped from stack\n", item);
        return item;
    }
}

// PEEK operation
int peek() {
    if (isEmpty()) {
        printf("Stack is empty\n");
        return -1;
    } else {
        return stack[top];
    }
}

// SIZE operation
int size() {
    return top + 1;
}

// DISPLAY operation
void display() {
    if (isEmpty()) {
        printf("Stack is empty\n");
    } else {
        printf("Stack elements are:\n");
        for (int i = top; i >= 0; i--) {
            printf("%d\n", stack[i]);
        }
    }
}

// Main function
int main() {
    push(10);
    push(20);
    push(30);

    display();

    printf("Top element is: %d\n", peek());

    pop();
    display();

    printf("Current size: %d\n", size());

    return 0;
}

Explanation of the Program

This program demonstrates how all stack operations work together in a complete implementation.

• Array (stack[MAX])
  Stores the elements of the stack.
• Top Variable (top)
  Tracks the position of the last inserted element.
  • top = -1 → stack is empty
  • top = MAX - 1 → stack is full

Time and Space Complexity of Stack Operations

In an array-based stack, all operations are performed using a TOP pointer, which directly accesses elements without traversal. Because of this, most stack operations are highly efficient.

1. PUSH Operation

The push operation involves:

• Checking if the stack is full
• Incrementing the TOP pointer
• Inserting the element

These steps take a constant number of operations regardless of input size.

Time Complexity: O(1)

2. POP Operation

The pop operation:

• Checks if the stack is empty
• Removes the top element
• Decrements the TOP pointer

No loops or recursion are involved.

Time Complexity: O(1)

3. PEEK Operation

Peek simply:

• Accesses the element at TOP

Time Complexity: O(1)

4. isEmpty Operation

This operation:

• Checks whether TOP == -1

Time Complexity: O(1)

5. isFull Operation

This operation:

• Checks whether TOP == MAX - 1

Time Complexity: O(1)

6. SIZE Operation

This operation:

• Returns TOP + 1

Time Complexity: O(1)

7. DISPLAY Operation

The display operation:

• Traverses all elements from TOP to bottom

Time Complexity: O(n)

(where n = number of elements in stack)

Summary of Time Complexity

Space Complexity

Array-Based Stack

The space complexity depends on the size of the array used to store elements.

• The stack uses a fixed-size array of size MAX
• No additional memory is used apart from a few variables

Space Complexity: O(n)
(where n = MAX size of stack)

Auxiliary Space

• No extra space is required for operations
• Only a few variables (top, temporary variables) are used

Auxiliary Space: O(1)

Overall Understanding with Real-Life Analogy

Think of a stack like a pile of books:

• Adding a book → push()
• Removing the top book → pop()
• Looking at the top book → peek()
• Checking if no books → isEmpty()
• Checking if pile is full → isFull()
• Counting books → size()

Conclusion

Stack operations are simple yet powerful:

• All operations are performed at one end (TOP)
• Strictly follow LIFO principle
• Efficient with O(1) time complexity for all operations

They are widely used in:

• Function calls (recursion)
• Expression evaluation
• Backtracking algorithms
• Syntax parsing