Data Structures Lab: Array-based Implementation of a Stack in C++

Objective:

The objective of this lab is to help computer science students understand the concept of a stack
and its operations. This lab will use a basic array-based implementation of a stack in C++,
focusing on the following key stack operations:

 Push: Add an element to the stack.

 Pop: Remove the top element from the stack.
 Peek/Top: Retrieve the top element without removing it.
 isEmpty: Check if the stack is empty.
 isFull: Check if the stack is full.

Prerequisites:

 Basic understanding of arrays and object-oriented programming in C++.

 Knowledge of how a stack operates (Last In, First Out - LIFO).

Instructions

1. Introduction to Stacks: A stack is a data structure that follows the LIFO principle,
where elements are added (pushed) and removed (popped) from the top. Think of it like
stacking books; you can only access the book at the top of the stack.
2. Array-based Stack: We'll use an array to simulate a stack where the index position
represents the position of elements in the stack. We need a variable ( top) to keep track of
the topmost element.

Step-by-step Implementation:

1. Step 1: Define the Stack Class

o Create a class Stack that will contain the array and the necessary functions to
operate the stack.

#include <iostream>
using namespace std;

#define MAX 5 // Maximum size of the stack

class Stack {
private:
int arr[MAX]; // Array to store stack elements
int top; // To keep track of the top element

1|Page
public:
// Constructor to initialize the stack
Stack() {
top = -1; // Stack is initially empty
}

// Push operation to add an element to the stack

void push(int element) {
if (isFull()) {
cout << "Stack Overflow! Cannot push " << element << endl;
} else {
top++; // Increment the top index
arr[top] = element; // Add element to the top
cout << "Pushed: " << element << endl;
}
}

// Pop operation to remove an element from the stack

void pop() {
if (isEmpty()) {
cout << "Stack Underflow! Nothing to pop." << endl;
} else {
cout << "Popped: " << arr[top] << endl;
top--; // Decrement the top index
}
}

// Peek operation to view the top element of the stack

int peek() {
if (isEmpty()) {
cout << "Stack is empty!" << endl;
return -1; // Return a dummy value
} else {
return arr[top]; // Return the top element
}
}

// Check if the stack is empty

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

// Check if the stack is full

bool isFull() {
return top == MAX - 1;
}
};

2. Step 2: Demonstrating Stack Operations

o Create a main() function that demonstrates the stack operations such as push,
pop, and peek.

int main() {
Stack stack; // Create a stack object

// Perform push operations

2|Page
 stack.push(10);
stack.push(20);
stack.push(30);
stack.push(40);
stack.push(50);

// Try to push into a full stack

stack.push(60);

// Peek at the top element

cout << "Top element is: " << stack.peek() << endl;

// Perform pop operations

stack.pop();
stack.pop();
stack.pop();

// Peek again after popping

cout << "Top element after popping is: " << stack.peek() << endl;

// Try to pop from an empty stack

stack.pop();
stack.pop();
stack.pop(); // This should display "Stack Underflow"

return 0;
}

Step 3: Explanation of Code

1. Class Definition:
o The class Stack encapsulates the stack operations and an array (arr) to store the
elements. The top variable keeps track of the last element pushed onto the stack.
If top is -1, it indicates that the stack is empty.
2. Stack Operations:
o push(): Adds an element to the stack if it is not full. It first checks if the stack is
full using the isFull() method. If not, it increments the top and adds the
element to the array.
o pop(): Removes the top element if the stack is not empty. The function
decrements the top index after printing the popped value.
o peek(): Returns the top element without removing it. It uses isEmpty() to check
if the stack is empty before trying to return the top value.
3. Stack Overflow and Underflow:
o If you attempt to push an element when the stack is full, the program will print a
"Stack Overflow" message.
o If you attempt to pop an element when the stack is empty, the program will print a
"Stack Underflow" message.

3|Page
Step 4: Sample Output
Pushed: 10
Pushed: 20
Pushed: 30
Pushed: 40
Pushed: 50
Stack Overflow! Cannot push 60
Top element is: 50
Popped: 50
Popped: 40
Popped: 30
Top element after popping is: 20
Popped: 20
Popped: 10
Stack Underflow! Nothing to pop.

Lab Exercise Instructions:

1. Implement the above program in a C++ environment.

2. Test the push(), pop(), peek(), isFull(), and isEmpty() operations.
3. Experiment by changing the size of the stack and the number of elements pushed.

Conclusion:

In this lab, we implemented a stack using an array in C++, focusing on its core operations: push,
pop, and peek. This basic implementation helps students understand how stacks work and lays
the groundwork for more complex stack-based applications in data structures.

4|Page
Data Structures Lab: Linked List Implementation of a Stack in C++

Objective:

The goal of this lab is to demonstrate the Linked List implementation of a Stack and its
operations using C++. This approach provides a dynamic way to manage a stack as opposed to
the fixed-size array-based implementation. We will focus on the following operations:

 Push: Add an element to the top of the stack.

 Pop: Remove the top element from the stack.
 Peek/Top: Retrieve the top element without removing it.
 isEmpty: Check if the stack is empty.

Prerequisites:

 Basic understanding of pointers and linked lists in C++.

 Knowledge of how a stack operates (Last In, First Out - LIFO).

Instructions:

1. Introduction to Stacks: A stack is a data structure that follows the LIFO principle,
where elements are added (pushed) and removed (popped) from the top. The linked list
implementation dynamically allocates memory as needed.
2. Linked List-based Stack: In this implementation, each element in the stack is stored in a
node, and each node points to the next node. A pointer top keeps track of the top node in
the stack.

Step-by-step Implementation:

1. Step 1: Define the Node Structure

o We first define a Node structure that represents each element in the stack.

#include <iostream>
using namespace std;

// Define the structure of a node in the linked list

struct Node {
int data; // Data stored in the node
Node* next; // Pointer to the next node
};

2. Step 2: Define the Stack Class

5|Page
 o The Stack class contains the necessary functions to implement the stack
operations using a linked list.

class Stack {
private:
Node* top; // Pointer to the top node in the stack

public:
// Constructor to initialize the stack
Stack() {
top = nullptr; // Initially, the stack is empty
}

// Push operation to add an element to the stack

void push(int value) {
Node* newNode = new Node(); // Create a new node
newNode->data = value; // Assign the value
newNode->next = top; // New node points to the previous top
top = newNode; // The new node is now the top
cout << "Pushed: " << value << endl;
}

// Pop operation to remove the top element from the stack

void pop() {
if (isEmpty()) {
cout << "Stack Underflow! Nothing to pop." << endl;
} else {
Node* temp = top; // Store the current top
cout << "Popped: " << top->data << endl;
top = top->next; // Move top to the next node
delete temp; // Free memory of the old top node
}
}

// Peek operation to view the top element of the stack

int peek() {
if (isEmpty()) {
cout << "Stack is empty!" << endl;
return -1;
} else {
return top->data; // Return the data at the top node
}
}

// Check if the stack is empty

bool isEmpty() {
return top == nullptr;
}
};

3. Step 3: Demonstrating Stack Operations

o Create a main() function that demonstrates the stack operations.

int main() {
Stack stack; // Create a stack object

6|Page
 // Perform push operations
stack.push(10);
stack.push(20);
stack.push(30);

// Peek at the top element

cout << "Top element is: " << stack.peek() << endl;

// Perform pop operations

stack.pop();
stack.pop();

// Peek again after popping

cout << "Top element after popping is: " << stack.peek() << endl;

// Check if the stack is empty

stack.pop();
if (stack.isEmpty()) {
cout << "Stack is now empty." << endl;
}

// Try to pop from an empty stack

stack.pop(); // This should display "Stack Underflow"

return 0;
}

Step 4: Explanation of Code

1. Node Structure:
o The Node structure defines each element in the stack. It contains two fields: data
to store the element value and next to point to the next node in the stack.
2. Stack Class:
o Push: Adds a new node to the stack. The newNode is created dynamically, its
data is set to the value passed, and it is linked to the previous top node. The new
node becomes the top of the stack.
o Pop: Removes the top node from the stack. It first checks if the stack is empty. If
not, it stores the top node in a temporary variable, moves the top pointer to the
next node, and deletes the old top node.
o Peek: Returns the value at the top of the stack without removing it. It returns -1 if
the stack is empty.
o isEmpty: Checks if the stack is empty by comparing the top pointer to nullptr.
3. Dynamic Memory:
o Since we're using a linked list, memory for each new node is allocated
dynamically using new. When nodes are popped, the memory is freed using
delete.

Step 5: Sample Output

Pushed: 10

7|Page
Pushed: 20
Pushed: 30
Top element is: 30
Popped: 30
Popped: 20
Top element after popping is: 10
Popped: 10
Stack is now empty.
Stack Underflow! Nothing to pop.

Lab Exercise Instructions:

1. Implement the above program in a C++ environment.

2. Test the push(), pop(), peek(), and isEmpty() operations.
3. Explore how the stack dynamically grows with each push and shrinks with each pop.

Conclusion:

In this lab, students learned how to implement a stack using a linked list in C++. This dynamic
approach allows the stack to grow and shrink as needed, without worrying about a fixed size.
The lab focused on core stack operations and memory management in C++.

8|Page