COLLEGE OF COMPUTER STUDIES AND MULTIMEDIA ARTS
CCS0015L
(DATA STRUCTURES AND ALGORITHMS)
EXERCISE
4
STACKS
Student Name / Group Jose Augustine A. Rapirap
Name:
Name Role
Members (if Group):
TW03
Section:
Ronel Ramos
Professor:
I. PROGRAM OUTCOME/S (PO) ADDRESSED BY THE LABORATORY EXERCISE
Identify, analyze and solve computing problems using fundamental principles of mathematics and
computing sciences. [PO: B]
II. COURSE LEARNING OUTCOME/S (CLO) ADDRESSED BY THE LABORATORY EXERCISE
Apply the fundamental principles of data structures and algorithms: concepts of abstract data; types of
common data structures used; description, properties, and storage allocation of data structures. [CLO: 2]
III. INTENDED LEARNING OUTCOME/S (ILO) OF THE LABORATORY EXERCISE
At the end of this exercise, students must be able to:
Learn how to code operations on a static & dynamic stack.
Apply stacks in programs both as user defined ADT and as an STL.
IV. BACKGROUND INFORMATION
A stack is a data structure in which elements are added to or deleted from a single end called the top of the
stack. The elements last inserted is the first to be removed, therefore stack is said to follow the Last-In
First-Out principle, LIFO. In this context, the insert operation is more commonly known as push and delete
operation is known as pop. Other operations on a stack are to find the size of stack, return topmost
element, search for an element in the stack etc.
Stacks are used in: Function calls, Recursion, Evaluation of expressions by compilers, undo mechanism in
an editor, etc.
V. LABORATORY ACTIVITY
ACTIVITY 4.1: Missing Brace
Write a C++ program that finds the minimum number of replacements required to make the given string of
braces balanced. The program should use stack STL.
Sample Output:
Program: (save as [surname_4_1.cpp])
#include <iostream>
#include <stack>
CCS0015L-Data Structures and Algorithms Page 2
of 11
#include <string>
using namespace std;
int count_replacements(string str) {
stack<char> s;
int count = 0;
for (int i = 0; i < str.length(); i++) {
if (str[i] == '{') {
s.push(str[i]);
}
else if (str[i] == '}') {
if (s.empty()) {
count++;
}
else {
s.pop();
}
}
}
count += s.size();
return count;
}
int main() {
string str;
cout << "Enter a string of braces: ";
getline(cin, str);
int count = count_replacements(str);
cout << "Minimum number of replacements required: " << count << endl;
return 0;
}
Output:(screenshot of the output)
CCS0015L-Data Structures and Algorithms Page 3
of 11
ACTIVITY 4.2: Stack Operations
Complete the program below to implement the stack data structure. Look for the functions with //TODO.
Paste your completed source code in the Code portion then highlight the statement(s) that you filled in the
incomplete program with color yellow.
Operations to be carried out on a stack are push, pop, display. Declare a class with a constructor and the
following member functions: push(e), pop(), display(), operations(). Dynamically allocate memory to the
array via constructor and initialize top to -1 in it.
The member function details are:
• push(): check if the stack is full if so display ―stack full‖ else increment top and push the element in
position pointed by the top.
• pop(): check if the stack is empty if so display “Stack is empty. No elements to pop” else pop the
element pointed by the top, store it in a variable of same type and decrement top to point the top
most element in the stack.
• display(): Check if the stack is empty if not display the elements in the stack.
• operations(): Allows the user to select an operation and carry out the operation chosen by the user.
Given program:
#include <iostream>
using namespace std;
template <typename T>
class Stack {
private:
T* a;
int n;
int top;
public:
Stack(int size) {
n = size;
a = new T[n];
top = -1;
}
void push(T element) {
if(top == n - 1) {
cout << "Stack is full\n";
}
else {
++top;
CCS0015L-Data Structures and Algorithms Page 4
of 11
a[top] = element;
}
}
T pop() {
//TODO
}
void display() {
//TODO
}
void operations() {
int ch;
while(true) {
cout << "\nStack Operations Menu\n1- Push an element\n2- Pop\n3-
Display the elements\n4- Exit\nSelect an operation: ";
cin >> ch;
switch(ch) {
case 1: {
T element;
cout << "Enter the element to push: ";
cin >> element;
push(element);
break;
}
case 2: {
T val = pop();
if(val != -1) {
cout << "Popped element: " << val << endl;
}
break;
}
case 3: {
display();
break;
}
case 4: {
exit(0);
}
default: {
cout << "Invalid choice.\n";
}
}
}
}
};
int main() {
int size;
cout << "Enter the size of the stack: ";
cin >> size;
CCS0015L-Data Structures and Algorithms Page 5
of 11
Stack<int> s(size);
s.operations();
return 0;
}
Code:
#include <iostream>
using namespace std;
template <typename T>
class Stack {
private:
T* a;
int n;
int top;
public:
Stack(int size) {
n = size;
a = new T[n];
top = -1;
}
void push(T element) {
if (top == n - 1) {
cout << "Stack is full\n";
}
else {
++top;
a[top] = element;
}
}
T pop() {
if (top == -1) {
cout << "Stack is empty\n";
return T();
}
else {
T element = a[top];
--top;
return element;
}
}
void display() {
CCS0015L-Data Structures and Algorithms Page 6
of 11
if (top == -1) {
cout << "Stack is empty\n";
}
else {
cout << "Stack elements: ";
for (int i = top; i >= 0; --i) {
cout << a[i] << " ";
}
cout << endl;
}
}
};
int main() {
int size;
cout << "Enter the size of the stack: ";
cin >> size;
Stack<int> s(size);
int ch;
while (true) {
cout << "\nStack Operations Menu\n1- Push an element\n2- Pop\n3- Display the elements\n4- Exit\
nSelect an operation: ";
cin >> ch;
switch (ch) {
case 1: {
int element;
cout << "Enter the element to push: ";
cin >> element;
s.push(element);
break;
}
case 2: {
int val = s.pop();
if (val != -1) {
cout << "Popped element: " << val << endl;
}
break;
}
case 3: {
s.display();
break;
}
case 4: {
exit(0);
}
default: {
cout << "Invalid choice.\n";
CCS0015L-Data Structures and Algorithms Page 7
of 11
}
}
}
return 0;
}
Output:(screenshot of the output)
Validation: Execute the program and carry out multiple sequential push, pop and display operations to
understand the working of the program.
CCS0015L-Data Structures and Algorithms Page 8
of 11
VI. QUESTION AND ANSWER
Directions: Briefly answer the questions below.
Explain the advantages of stacks.
- It helps you to manage the data in the “LIFO” method
- It allows you to control and handle memory allocation and deallocation
- It helps to automatically clean up the objects
Discuss how stacks can be implemented.
Stacks can be implemented by an array or a linked list.
CCS0015L-Data Structures and Algorithms Page 9
of 11
VII. REFERENCES
Wittenberg, Lee.(2018). Data structures and algorithms in C++. s.l.: Mercury Learning
Baka, Benjamin(2017). Python data structures and algorithms : improve the performance and speed of
your applications. Birmingham, U.K : Packt Publishing
Downey, Allen.(2017). Think data structures : algorithms and information retrieval in Java. Sebastopol,
CA: O'Reilly
Chang, Kung-Hua(2017). Data Structures Practice Problems for C++ Beginners. S.l : Simple and
Example
Hemant Jain(2017). Problem Solving in Data Structures & Algorithms Using C++: Programming
Interview Guide. USA: CreateSpace Independent Publishing Platform
RUBRIC:
Criteria 4 3 2 1 Score
A completed
A completed solution is An incomplete
A completed
solution is implemented solution is
solution runs
tested and runs on the required implemented
without errors.
but does not platform, and on the required
It meets all the
meet all the uses the platform. It
specifications
specifications compiler does not
and works for
nd/or work for specified. It compile and/or
all test data.
all test data. runs, but has run.
logical errors.
Solution(x5)
The program Not all of the
Few of the
The program design selected
selected
design uses generally uses structures are
structures are
appropriate appropriate appropriate.
appropriate.
structures. The structures. Some of the
Program
overall program Program program
elements are
design is elements elements are
not well
appropriate. exhibit good appropriately
designed.
Program design. designed.
Design(x3)
CCS0015L-Data Structures and Algorithms Page 10
of 11
All required There are few
All required
parts of the parts of the Most of the
parts in the
document are document are parts of the
document are
complete and missing but the document are
present and
correct(code, rest are missing and
correct but not
output of complete and incorrect.
complete.
Completeness screenshots) correct.
of
Document(x2)
Total
CCS0015L-Data Structures and Algorithms Page 11
of 11
