Module II - Stack

Introduction to Stack Data Structure

A stack is a data structure which is used to store data in a linear fashion. It is an Abstract data
type (ADT) in which data is inserted and deleted from a single end which is the stack's top. It
follows a Last in, First out (LIFO) principle i.e. the data which is inserted most recently in the
stack will be deleted first from the stack. Given below is the pictorial representation of how a
stack looks like.

A stack is a abstract data type (ADT) which is used to store data in a linear fashion. A stack only
has a single end (which is stack's top) through which we can insert or delete data from it.

There are many different stack operations which can be applied on a stack. We will discuss most
of the operations in this article.
This pictorial representation shows how the stack data structure works: the recently added
element is always at the top and is the first to be accessed or removed.

Stack ADT

In the context of a stack, ADT stands for “Abstract Data Type.”Abstract Data Type (ADT) is an

abstraction that defines a set of operations on a data type, hiding the implementation details.

Stack ADT simplifies the way we think about stacks in programming. It’s like a blueprint that

outlines how stacks should work without getting into complicated details. It comprises of three

crucial elements: Data, Representation of Data, and Operations on Data.

Data

1. Space for Storing Elements: Represents the memory or storage needed to hold stack

elements.

2. Top Pointer: Indicates the current topmost element in the stack.

Representation
Stack Representation
A stack follows a Last in, First out principle (LIFO). This means the data inserted in the stack
last will be first to be removed. All operations, such as insertion (push) and deletion (pop), occur
at the top of the stack, and the top element is always the most recently element added.

Given below is the stack representation to show how data is inserted and deleted in a stack.

Stack Operations
There are various stack operations that are applicable on a stack. Stack operations are generally
used to extract information and data from a stack data structure.

Some of the stack operations are given below.

1. Insertion in Stack/Push Operation

The push operation adds a data element to the top of the stack. In array based stacks, the push
operation must first check if the stack is full before adding a new element. If the stack is full, a
stack overflow occurs and the push should not proceed. In a typical stack class implementation in
Java, you might see:

The process of putting a new data element onto stack is known as a Push Operation. Push
operation involves a series of steps

− Step 1 − Checks if the stack is full.

 Step 2 − If the stack is full, display “stack is FULL”and exit.

 Step 3 − If the stack is not full, increments top to point next empty space.
 Step 4 − Adds data element to the stack location, where top is pointing.

 Step 5 − Returns success

2. Deletion/Pop Operation
Accessing the content while removing it from the stack, is known as a Pop Operation. In an array
implementation of pop() operation, the data element is not actually removed, instead top is
decremented to a lower position in the stack to point to the next value. A Pop operation may
involve the following steps –

 Step 1 − Checks if the stack is empty.

 Step 2 − If the stack is empty, produces an error and exit.
 Step 3 − If the stack is not empty, accesses the data element at which top is pointing.
 Step 4 − Decreases the value of top by 1.
 Step 5 − Returns success
3. topElement() / peek()
TopElement / Peek is a function in the stack which is used to extract the element present at the
stack top.

4. isEmpty()
isEmpty is a boolean function in stack definition which is used to check whether the stack is
empty or not. It returns true if the stack is empty. Otherwise, it returns false. The isempty
operation checks for an empty stack, which is important to prevent errors such as stack
underflow during pop or peek operations.
5. isFull()
isFull is a function which is used to check whether the stack has reached its maximum limit of
insertion of data or not i.e. if 'maxLimit' is the maximum number of elements that can be stored
in the stack and if there are exactly maxLimit number of elements present in the stack currently,
then the function isFull() returns true. Otherwise, if the number of elements present in the stack
currently are less than 'maxLimit', then isFull() returns false.

6. size()
Size is a function in stack definition which is used to find out the number of elements that are
present inside the stack.

Implementation of Stack
1. Using Array: Involves a fixed-size array to store elements, with the top pointer tracking
the current position in the array.
2. Using Linked List: Utilizes a linked list structure, where each node holds an element,
and the top pointer points to the first node
Program :-
#include <stdio.h>

#include <stdlib.h>

#define MAX_SIZE 5 // Define the maximum capacity of the stack

int stack[MAX_SIZE]; // Array to store stack elements

int top = -1; // Index of the top element, initialized to -1 for an empty stack

// Function to check if the stack is full (Stack Overflow condition)

int isFull() {

return top == MAX_SIZE - 1; //

// Function to check if the stack is empty (Stack Underflow condition)

int isEmpty() {

return top == -1; //

// Function to add an element to the stack

void push(int value) {

if (isFull()) {

printf("Stack Overflow! Cannot push %d\n", value);

} else {

stack[++top] = value; // Increment top first, then add the element

printf("Pushed %d onto the stack\n", value);

// Function to remove the top element from the stack

int pop() {

if (isEmpty()) {

printf("Stack Underflow! Cannot pop from an empty stack\n");

return -1; // Return an error value

} else {

int poppedValue = stack[top]; // Retrieve the top element

top--; // Decrement top (effectively removing the element)

printf("Popped %d from the stack\n", poppedValue);

return poppedValue;

// Function to get the top element without removing it

int peek() {

if (isEmpty()) {

printf("Stack is Empty! No top element to display\n");

return -1; // Return an error value

} else {

return stack[top]; // Return the top element

// Function to display all elements in the stack

void display() {

if (isEmpty()) {

printf("Stack is Empty\n");

} else {
 printf("Stack elements (top to bottom): ");

for (int i = top; i >= 0; i--) {

printf("%d ", stack[i]);

printf("\n");

// Main function to drive the program with a menu

int main() {

int choice, value;

while (1) {

printf("\n*** Stack Implementation Menu ***\n");

printf("1. Push\n");

printf("2. Pop\n");

printf("3. Peek\n");

printf("4. Display\n");

printf("5. Exit\n");

printf("Enter your choice: ");

scanf("%d", &choice);

switch (choice) {

case 1:

printf("Enter the value to push: ");

scanf("%d", &value);

push(value);

break;
 case 2:

pop();

break;

case 3:

value = peek();

if (value != -1) {

printf("The top element is %d\n", value);

break;

case 4:

display();

break;

case 5:

exit(0); // Exit the program

default:

printf("Invalid choice! Please enter a number between 1 and 5\n");

return 0;

}
Multiple Stacks
In a standard stack, we use one array and one pointer (top). In a Multiple Stack implementation,
we divide a single array of size n into segments to accommodate 𝑚 stacks.
The goal is to ensure that:

1. Each stack operates independently (LIFO).

2. Memory is utilized efficiently (preventing one stack from overflowing while the array
still has empty space).

Types of Implementation

1. Two Stacks in One Array

This is the most common and efficient variation. Instead of dividing the array in the middle, we
let the stacks grow toward each other.

 Stack 1: Starts from the leftmost index (0) and moves toward the right.
 Stack 2: Starts from the rightmost index (n-1) and moves toward the left.
 Overflow Condition: When the two pointers meet (top1 + 1 == top2).

2. N-Stacks in One Array

For more than two stacks, the array is usually divided 𝑘 equal segments. Each stack 𝑖 has its own
top[i], bottom[i], and limit[i].
Overflow Condition:

When top1 + 1 == top2, there are no empty slots left between them.
 3. Implementation Logic (Two Stacks)

Operation Stack 1 Logic Stack 2 Logic

Initial State top1 = -1 top2 = size

Push top1++, then add element top2--, then add element

Pop Remove element, then top1-- Remove element, then top2++

Overflow top1 + 1 == top2 top1 + 1 == top2

4. Example in C++ (Pseudo-code)

Here is how you would structure a class to manage two stacks within a single array of size 10.

class TwoStacks {
int* arr;
int size;
int top1, top2;

public:
TwoStacks(int n) {
size = n;
arr = new int[n];
top1 = -1;
top2 = size;
}

// Push into Stack 1

void push1(int x) {
if (top1 < top2 - 1) {
arr[++top1] = x;
} else {
cout << "Stack Overflow";
}
}

// Push into Stack 2

void push2(int x) {
if (top1 < top2 - 1) {
arr[--top2] = x;
} else {
cout << "Stack Overflow";
}
 }

// Pop from Stack 1

int pop1() {
if (top1 >= 0) {
return arr[top1--];
}
return -1; // Stack Empty
}
};

5. Advantages & Disadvantages

 Pros:
o Space Efficiency: It prevents "false" overflows. If Stack 1 is small, Stack 2 can
use the extra space.
o Reduced Overhead: Only one array allocation is needed instead of multiple
small ones.
 Cons:
o Fixed Size: If the total array size is reached, no stack can grow further even if one
is empty.
o Complexity: Managing more than two stacks becomes complex because you may
need to "shift" stacks in memory to make room.

Note: If you need to implement 𝑘 stacks (more than 2), we usually use an additional array called
next[] to track the indices. This is known as a Linked List representation of Multiple Stacks.

Evaluation of Arithmetic Expressions

 A stack is a very effective data structure for evaluating arithmetic
expressions in programming languages.
 An arithmetic expression consists of operands and operators.
 In addition to operands and operators, the arithmetic expression may also
include parenthesis like "left parenthesis" and "right parenthesis".

Example 3.3: A + (B - C)
To evaluate the expressions, one needs to be aware of the standard precedence
rules for arithmetic expression. The precedence rules for the five basic arithmetic
operators are:

Evaluation of Arithmetic Expression requires two steps:

 First, convert the given expression into special notation.

 Evaluate the expression in this new notation.
 Notations for Arithmetic Expression

There are three notations to represent an arithmetic expression:

1. Infix Notation
2. Prefix Notation
3. Postfix Notation

1. Infix Notation The infix notation is a convenient way of writing an expression in which
each operator is placed between the operands. Infix expressions can be parenthesized or
un parenthesized depending upon the problem requirement

Example 3.4: A + B, (C - D) etc.

All these expressions are in infix notation because the operator comes between the
operands.

2. Prefix Notation The prefix notation places the operator before the operands.
This notation was introduced by the Polish mathematician and hence often referred to as
polish notation.

Example 3.5: + A B, -CD etc.

All these expressions are in prefix notation because the operator comes before the
operands.
3. Postfix Notation The postfix notation places the operator after the operands. This notation
is just the reverse of Polish notation and also known as Reverse Polish notation.
 Example 3.6: AB +, CD+, etc.

All these expressions are in postfix notation because the operator comes after the
operands. Table 3.3 illustrates the conversion of Arithmetic Expression into various
Notations

Examples :