ADT Stack and Its Operations

1. Introduction

A Stack is a linear data structure in which insertion and deletion of elements take place only at one end, called the TOP.

A stack follows the principle:

$$\boxed{\text{LIFO — Last In, First Out}}$$

This means that the element inserted last is the first element to be removed.

A simple real-life example is a stack of plates. A new plate is placed on the top, and the plate removed first is also the one at the top.

---

2. Definition of Stack

A stack is a linear data structure in which insertion and deletion are performed at the same end, known as the TOP.

The two fundamental operations are:

• PUSH – inserts an element into the stack.

• POP – removes an element from the stack.

Other commonly used operations include:

• PEEK/TOP – accesses the top element without removing it.

• isEmpty() – checks whether the stack contains no elements.

• isFull() – checks whether an array-based stack has reached its capacity.

---

3. Characteristics of a Stack

Important characteristics of a stack are:

1. It is a linear data structure.

2. It follows LIFO ordering.

3. Insertion occurs at the TOP.

4. Deletion occurs at the TOP.

5. Only the top element can normally be accessed directly.

6. A stack can be implemented using an array or a linked list.

7. An array implementation has a fixed capacity unless dynamic resizing is provided.

8. A linked-list implementation can grow and shrink dynamically, subject to available memory.

---

4. Stack as an Abstract Data Type (ADT)

An Abstract Data Type (ADT) defines a data structure by specifying its data and the operations that can be performed on it, without requiring a particular implementation.

For a Stack ADT, we specify operations such as:

$$Stack = \{PUSH,\ POP,\ PEEK,\ isEmpty,\ isFull\}$$

The Stack ADT does not require that the stack be implemented using an array. It can also be implemented using a linked list.

Stack ADT

Operation	Purpose
push(x)	Inserts x into the stack
pop()	Removes and returns the top element
peek()	Returns the top element without removing it
isEmpty()	Checks whether stack is empty
isFull()	Checks whether stack is full in a bounded implementation

This separation between what the structure does and how it is implemented is the central idea of an ADT.

---

5. Representation of Stack

A stack can mainly be represented in two ways:

1. Array representation

2. Linked-list representation

For B.Tech DSA using C, both implementations are important.

---

6. Stack Using Array

In an array implementation, stack elements are stored in an array.

A variable called top keeps track of the current top position.

For an initially empty stack:

$$top=-1$$

For example, consider a stack containing:

10, 20, 30, 40

Here:

• 10 is the bottom element.

• 40 is the top element.

• top points to the position containing 40.

For an array of capacity MAX:

int stack[MAX];
int top = -1;

---

7. Important Stack Conditions

Two special conditions must be considered in an array-based stack.

7.1 Stack Overflow

Overflow occurs when we try to insert an element into a stack that is already full.

For an array of size MAX:

$$top = MAX-1$$

indicates that the stack is full.

Example:

MAX = 5
top = 4

A further PUSH operation causes Stack Overflow.

---

7.2 Stack Underflow

Underflow occurs when we try to remove an element from an empty stack.

For an empty array-based stack:

$$top=-1$$

A POP operation at this point causes Stack Underflow.

---

8. PUSH Operation

PUSH is the operation used to insert a new element at the top of the stack.

Suppose the stack contains:

10, 20, 30

and we perform:

PUSH(40)

The new stack becomes:

10, 20, 30, 40

The top is moved to the new element.

---

8.1 Algorithm for PUSH

Algorithm: PUSH(STACK, TOP, ITEM)

Step 1: Check whether the stack is full.

Step 2: If TOP == MAX - 1, report Overflow and terminate the operation.

Step 3: Otherwise increment TOP.

$$TOP = TOP + 1$$

Step 4: Store the item:

$$STACK[TOP] = ITEM$$

Step 5: Stop.

Pseudocode

PUSH(STACK, TOP, ITEM)

1. If TOP = MAX - 1
       Print "Stack Overflow"
       Return

2. TOP = TOP + 1

3. STACK[TOP] = ITEM

4. Return

---

9. C Implementation of PUSH

void push(int stack[], int *top, int max, int item)
{
    if (*top == max - 1)
    {
        printf("Stack Overflow\n");
        return;
    }

    (*top)++;
    stack[*top] = item;
}

Explanation

The condition:

if (*top == max - 1)

checks whether the stack is full.

Then:

(*top)++;

moves top to the next available position.

Finally:

stack[*top] = item;

stores the new element.

---

10. POP Operation

POP is the operation used to remove an element from the top of the stack.

Suppose the stack is:

10, 20, 30, 40

After:

POP()

40 is removed.

The stack becomes:

10, 20, 30

---

10.1 Algorithm for POP

Algorithm: POP(STACK, TOP)

Step 1: Check whether the stack is empty.

Step 2: If TOP == -1, report Underflow and terminate.

Step 3: Store the top element.

$$ITEM = STACK[TOP]$$

Step 4: Decrease TOP.

$$TOP = TOP - 1$$

Step 5: Return ITEM.

Pseudocode

POP(STACK, TOP)

1. If TOP = -1
       Print "Stack Underflow"
       Return

2. ITEM = STACK[TOP]

3. TOP = TOP - 1

4. Return ITEM

---

11. C Implementation of POP

int pop(int stack[], int *top)
{
    if (*top == -1)
    {
        printf("Stack Underflow\n");
        return -1;
    }

    int item = stack[*top];
    (*top)--;

    return item;
}

---

12. PEEK Operation

PEEK returns the element currently present at the top of the stack without removing it.

For example:

Stack:

40  ← TOP
30
20
10

PEEK() returns:

40

The stack remains unchanged.

Algorithm

PEEK(STACK, TOP)

1. If TOP = -1
       Print "Stack is Empty"
       Return

2. Return STACK[TOP]

C Implementation

int peek(int stack[], int top)
{
    if (top == -1)
    {
        printf("Stack is Empty\n");
        return -1;
    }

    return stack[top];
}

Complexity

$$T(n)=O(1)$$

---

13. isEmpty Operation

The isEmpty() operation checks whether the stack contains any element.

For an array-based stack:

$$top=-1$$

means that the stack is empty.

Algorithm

isEmpty(TOP)

If TOP = -1
    Return TRUE
Else
    Return FALSE

C

int isEmpty(int top)
{
    return top == -1;
}

Complexity

$$O(1)$$

---

14. isFull Operation

The isFull() operation checks whether an array-based stack has reached its maximum capacity.

For an array of size MAX:

$$top=MAX-1$$

means the stack is full.

C

int isFull(int top, int max)
{
    return top == max - 1;
}

Complexity

$$O(1)$$

---

15. Complete Stack Program Using Array

The following program demonstrates the major Stack ADT operations.

#include <stdio.h>

#define MAX 5

int stack[MAX];
int top = -1;

void push(int item)
{
    if (top == MAX - 1)
    {
        printf("Stack Overflow\n");
        return;
    }

    stack[++top] = item;
    printf("%d pushed into stack\n", item);
}

int pop()
{
    if (top == -1)
    {
        printf("Stack Underflow\n");
        return -1;
    }

    return stack[top--];
}

int peek()
{
    if (top == -1)
    {
        printf("Stack is Empty\n");
        return -1;
    }

    return stack[top];
}

void display()
{
    if (top == -1)
    {
        printf("Stack is Empty\n");
        return;
    }

    printf("Stack elements:\n");

    for (int i = top; i >= 0; i--)
    {
        printf("%d\n", stack[i]);
    }
}

int main()
{
    push(10);
    push(20);
    push(30);
    push(40);

    display();

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

    printf("Deleted element = %d\n", pop());

    display();

    return 0;
}

Possible Output

10 pushed into stack
20 pushed into stack
30 pushed into stack
40 pushed into stack

Stack elements:
40
30
20
10

Top element = 40
Deleted element = 40

Stack elements:
30
20
10

---

16. Complexity Analysis of Stack Operations

For an array-based stack:

Operation	Time Complexity	Auxiliary Space
PUSH	O(1)	O(1)
POP	O(1)	O(1)
PEEK	O(1)	O(1)
isEmpty	O(1)	O(1)
isFull	O(1)	O(1)

The stack itself requires:

$$O(n)$$

space when it contains up to n elements.

The important point is that each basic stack operation takes constant time in a standard array implementation.

---

17. Stack Using Linked List

A stack can also be implemented using a linked list.

Each node contains:

• Data

• Pointer to the next node

The head node is treated as TOP.

Node Definition in C

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

A pointer:

struct Node *top = NULL;

represents an empty stack.

---

18. PUSH in Linked-List Stack

A new node is created and placed at the beginning of the linked list.

Algorithm

1. Create a new node.
2. If memory is unavailable, report overflow.
3. Store ITEM in the new node.
4. Set newNode->next = TOP.
5. Set TOP = newNode.
6. Return.

C Implementation

void push(struct Node **top, int item)
{
    struct Node *newNode;

    newNode = (struct Node *)malloc(sizeof(struct Node));

    if (newNode == NULL)
    {
        printf("Stack Overflow\n");
        return;
    }

    newNode->data = item;
    newNode->next = *top;

    *top = newNode;
}

---

19. POP in Linked-List Stack

The first node is removed from the linked list.

Algorithm

1. Check whether TOP = NULL.
2. If yes, report Underflow.
3. Store TOP in a temporary pointer.
4. Store the data.
5. Move TOP to the next node.
6. Free the old node.
7. Return the data.

C Implementation

int pop(struct Node **top)
{
    if (*top == NULL)
    {
        printf("Stack Underflow\n");
        return -1;
    }

    struct Node *temp = *top;
    int item = temp->data;

    *top = (*top)->next;

    free(temp);

    return item;
}

---

20. Array Stack vs Linked-List Stack

Feature	Array Stack	Linked-List Stack
Memory allocation	Usually fixed	Dynamic
Size	Limited by capacity	Grows subject to available memory
Implementation	Simpler	More complex
Memory overhead	Low	Extra pointer per node
PUSH	O(1)	O(1)
POP	O(1)	O(1)
Overflow	When capacity is reached	When memory allocation fails
Memory utilization	May have unused allocated capacity	Allocated per node

---

21. Applications of Stack

Stacks are widely used in computer science.

Important applications include:

21.1 Function Calls

When a function is called, information required to return from the function is maintained using the call stack.

21.2 Recursion

Recursive function calls use stack memory to maintain activation records.

21.3 Expression Conversion

Stacks are used for:

• Infix to postfix conversion

• Infix to prefix conversion

21.4 Expression Evaluation

Stacks are used to evaluate:

• Postfix expressions

• Prefix expressions

21.5 Parentheses Matching

A stack can be used to check balanced symbols such as:

()
{}
[]

21.6 Undo/Redo Operations

Many applications use stack-like structures to maintain previous states.

21.7 Backtracking

Stacks can support backtracking problems such as maze traversal and certain search procedures.

21.8 Depth First Search

DFS can be implemented using an explicit stack or recursion.

---

22. Example: Stack Operations

Consider an initially empty stack.

Perform:

PUSH(10)
PUSH(20)
PUSH(30)
POP()
PUSH(40)
PEEK()

Step-by-step

Operation	Stack	TOP
Initial	Empty	-1
PUSH(10)	10	0
PUSH(20)	10, 20	1
PUSH(30)	10, 20, 30	2
POP()	10, 20	1
PUSH(40)	10, 20, 40	2
PEEK()	10, 20, 40	2

Therefore:

$$PEEK()=40$$

The element 30 was removed by the POP() operation.

---

23. Important Properties of PUSH and POP

A fundamental property of a stack is:

The element that is inserted last is removed first.

Suppose:

PUSH(A)
PUSH(B)
PUSH(C)

Then:

POP() → C
POP() → B
POP() → A

Thus:

$$A \rightarrow B \rightarrow C$$

is inserted in that order, but:

$$C \rightarrow B \rightarrow A$$

is removed.

This is the essence of LIFO.

---

24. Advantages of Stack

1. Simple and easy-to-understand data structure.

2. PUSH and POP are generally O(1).

3. Useful for recursion and function-call management.

4. Useful for expression conversion and evaluation.

5. Useful in backtracking algorithms.

6. Can be implemented using arrays or linked lists.

7. Provides controlled access to data through the top.

---

25. Limitations of Stack

1. Direct access to arbitrary elements is not normally supported.

2. Array implementation has a capacity limitation.

3. Overflow can occur in a bounded array implementation.

4. Underflow occurs when POP is attempted on an empty stack.

5. Linked-list implementation requires additional memory for pointers.

6. Searching for an arbitrary element is generally O(n).

---

26. Stack Operation Summary

Operation	Function	Time Complexity
PUSH	Insert at top	O(1)
POP	Remove from top	O(1)
PEEK	Read top element	O(1)
isEmpty	Check empty condition	O(1)
isFull	Check full condition	O(1)
Display/Traversal	Visit all elements	O(n)
Search	Find an element	O(n)

---

27. Key Points to Remember

• A stack is a linear data structure.

• Stack follows LIFO.

• Insertion is called PUSH.

• Deletion is called POP.

• PEEK reads the top element without removing it.

• top = -1 represents an empty array-based stack.

• top = MAX - 1 represents a full array-based stack.

• Overflow occurs when insertion is attempted on a full bounded stack.

• Underflow occurs when deletion is attempted on an empty stack.

• Stack can be implemented using an array or linked list.

• PUSH and POP generally take O(1) time.

• Stack is extensively used in recursion, expression processing, parentheses matching, backtracking, and DFS.