Data Structure & Algorithm

Lab

Stacks (static and dynamic implementation)

Lab Journal – 02
(OC-Lab 02)

1
1 Objectives
 This lab is intended to introduce students to the concept of Stacks and its
implementation.
 The students will implement the Stack and employ it in solving the given problems
statically and using a linklist dynamically.

LAB TASKS & EXERCISES

Task 2.1: Give the answers to the following
• Show the contents of stack (at each step) once the following sequence of
statements are executed.
Stack S;

Ans,

For first three steps A , B and C will be added in the stack in order

C(2 index)

B(1 index)

2
A(0 index)

The pop function will delete the value inserted previously first in last out since it is
called twice B and C will be removed

A(0 index)

Again D and E are inserted using the push function

E(2 index)

D(1 index)

A(0 index)

And they are removed again

3
A(0 index)

Task 2.2: Write a C++ program to implement the following static stack algorithm such
that:

 An array to be declared globally

 Array length to be defined as a macro
 Use switch statement in the main function for calling different functions
under a do-while repetition structure.
 Define push() function to push elements in the stack
 Determine whether stack is currently full (Stack overflow)
 If not: Add new item to the top of the stack.
 Define pop () function to remove elements from the stack
 Define top () function to return top value of stack.
 Determine whether stack is currently empty (Stack underflow)
 If not: remove item from the top of the stack.
 Display (): display stack items on the screen after operation of pushing and
popping.

Solution:
#include<iostream>
using namespace std;

const int macro = 10;

int arr[macro];
int top = -1;
void isFull() {
if (top >= macro - 1) {
cout << "the stack is full." << endl;
}

4
}

void isEmpty() {
if (top == -1) {
cout << "the stack is empty." << endl;
}
}

void push(int a) {
if (top >= macro - 1) {
isFull();
}
else {
top++;
arr[top] = a;
}
}

void pop() {
if (top == -1) {
isEmpty();
}
else {
arr[top--];
}
}

void getTop() {
if (top != -1) {
cout << "Top element: " << arr[top] << endl;
}
else {
isEmpty();
}
}

void display() {
if (top == -1) {
isEmpty();
}
else {
cout << "Stack elements: ";
for (int i = 0; i <= top; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
}

int main() {
int choice, value;
do {
cout << "\nStack Operations Menu:"<<endl;
cout << "1. Push"<<endl;
cout << "2. Pop"<<endl;
cout << "3. Display Top Element"<<endl;
cout << "4. Display Stack"<<endl;
cout << "5. Exit"<<endl;
cout << "Enter your choice: "<<endl;
cin >> choice;

5
switch (choice) {
case 1:
cout << "Enter a value to push: ";
cin >> value;
push(value);
break;
case 2:
pop();
break;
case 3:
getTop();
break;
case 4:
display();
break;
case 5:
cout << "Exit" << endl;
break;
default:
cout << "Invalid choice" << endl;
}
} while (choice != 5);

return 0;
}

6
Task 2.3:
Write a program using struct to perform the push and pop operations on the stack such
that:
 A stack structure to be declared with array and top variable as its members.
 Perform the push, Pop and list_element operations by using pointer of type struct as
a parameter for all functions.
Solution: #include<iostream>
using namespace std;

struct stack {
int arr[10];

7
int top = -1;
};

void push(stack* a,int value) {

if (a->top >= 9) {
cout<<"stack is full";
}
else {
a->top++;
a->arr[a->top] = value;
}
}

void pop(stack*a) {
if (a->top == -1) {
cout << "stack is empty";
}
else {
a->arr[a->top--];
}
}
void listelement(stack* a) {

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

cout << a->arr[i] << endl;
}
}

int main() {
stack a;
int n;
int c;
for (int i = 0; i < 10; i++) {
cout << "enter the values you want to add in the stack" << endl;
cin >> n;
push(&a, n);
}
cout << "enter the number of elements you want to pop: ";
cin >> c;
for (int i = 0; i < c; i++) {
pop(&a);
}
listelement(&a);
}

8
Task 2.4:

Calculate the sum of the marks of all the students of a group. In the program declare an
integer array dynamically and allocated it some space in memory equal to the size
which would be occupied by length number of integers. Note: value for length
variable shall also be taken at run time. Delete the array at the end.

Solution: #include<iostream>
using namespace std;

int main() {
int length;
int marks;
int sum=0;
cout << "Enter the amount of students: ";
cin >> length;
int* arr = new int[length];
for (int i = 0; i < length; i++) {
cout << "enter the marks of the students:" << endl;
cin >> marks;
arr[i] = marks;
sum += arr[i];

9
}
cout << "the sum of marks is: " << sum;
delete[]arr;
}

Exercise 01:
Write a program to implement a stack dynamically using a linklist with all the functions
representing different operations of stack. Define member functions push (), Pop () and
display outside the class.
Solution:
Exercise 02:
Write a C++ program that reverses the stack (using an array) elements.
 Push elements in the stack:
 Stack elements: 1 2 3 4 5 6 7
 Display the reverse elements of the stack:
 Stack elements: 7 6 5 4 3 2 1
Solution:
#include<iostream>
using namespace std;
const int n = 7;
class stack {
int arr[n];
int top = -1;
public:
void push(int a) {
if (top >= 6) { cout << "stack is full"; }
else
top++;
arr[top] = a;
}
void display() {
for (int i = 0; i < n; i++) {
cout << arr[i] << endl;
}
}
void reverse() {
for (int i = 0; i < n/2; i++) {
int temp = arr[i];
arr[i] = arr[n - 1 - i];

10
arr[n - 1 - i] = temp;
}
}
};

int main() {
stack s;
for (int i = 1; i <= 7; i++) {
s.push(i);
}
cout << "Normal order:" << endl;
s.display();
cout << endl << "reversed order:" << endl;
s.reverse();
s.display();

***************************END OF LAB JOURNAL***************************

11