School of Computer Science Engineering and Technology

Course- B. Tech Type- Core Course

Code- CSET243 Course Name-DSA using C++
Year- 2024 Semester- Odd
Date-24-08-2024 Batch- 3rd Sem
Tutorial: 05

COURSE-SPECIFIC LEARNING OUTCOMES (CO)

CO1: Articulate the design, use and associated algorithms of fundamental and abstract data structures

CO2: Examine various operations performed on and using Stack and Queue data structures.

CO3: Demonstrate hands-on experience on implementing different data structures

CO4: Build optimized solutions for real-word programming problems using efficient data structures.

Objective 1: How to perform a given operation using Stack(s).

Objective 2: How to perform a given operation using Queue(s).

Tut No. Name CO 1 CO 2 CO 3 CO4

1 Tutorial:5.1 √

Section 1 Easy (3 Questions)

Question1. If the elements “A”, “B”, “C” and “D” are placed in a queue and are deleted one at a
time, in what order will they be removed?
a) ABCD
b) DCBA
c) DCAB
d) ABDC
Answer: a
Explanation: Queue follows FIFO approach. i.e. First in First Out Approach. So, the order of
removal elements are ABCD.

Question2. A normal queue, if implemented using an array of size MAX_SIZE, gets full when?
a) Rear = MAX_SIZE – 1
b) Front = (rear + 1)mod MAX_SIZE
c) Front = rear + 1
d) Rear = front
Answer: a
Explanation: When Rear = MAX_SIZE – 1, there will be no space left for the elements to be
added in queue. Thus queue becomes full.
Question3. What is the value of the postfix expression 6 3 2 4 + – *?
a) 1
b) 40
c) 74
d) -18
Answer: d
Explanation: Postfix Expression is (6*(3-(2+4))) which results -18 as output.

Section 2 Medium (3 Questions)

Question1. Given a string, reverse it using stack.

Example:
Input: str = “GeeksQuiz”
Output: ziuQskeeG

Input: str = “abc”

Output: cba

Solution:

Code:
// C program to reverse a string using stack
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// A structure to represent a stack

struct Stack {
int top;
unsigned capacity;
char* array;
};

// function to create a stack of given

// capacity. It initializes size of stack as 0
struct Stack* createStack(unsigned capacity)
{
struct Stack* stack
= (struct Stack*)malloc(sizeof(struct Stack));
stack->capacity = capacity;
stack->top = -1;
stack->array
= (char*)malloc(stack->capacity * sizeof(char));
return stack;
}

// Stack is full when top is equal to the last index

int isFull(struct Stack* stack)
{
return stack->top == stack->capacity - 1;
}

// Stack is empty when top is equal to -1

int isEmpty(struct Stack* stack)
{
return stack->top == -1;
}

// Function to add an item to stack.

// It increases top by 1
void push(struct Stack* stack, char item)
{
if (isFull(stack))
return;
stack->array[++stack->top] = item;
}
// Function to remove an item from stack.
// It decreases top by 1
char pop(struct Stack* stack)
{
if (isEmpty(stack))
return INT_MIN;
return stack->array[stack->top--];
}

// A stack based function to reverse a string

void reverse(char str[])
{
// Create a stack of capacity
// equal to length of string
int n = strlen(str);
struct Stack* stack = createStack(n);

// Push all characters of string to stack

int i;
for (i = 0; i < n; i++)
push(stack, str[i]);

// Pop all characters of string and

// put them back to str
for (i = 0; i < n; i++)
str[i] = pop(stack);
}

// Driver program to test above functions

int main()
{
char str[] = "GeeksQuiz";

reverse(str);
printf("Reversed string is %s", str);

return 0;
}
Question2. Given an expression string exp, write a program to examine whether the pairs and
the orders of “{“, “}”, “(“, “)”, “[“, “]” are correct in the given expression.

Example:
Input: exp = “[()]{}{[()()]()}”
Output: Balanced
Explanation: all the brackets are well-formed

Input: exp = “[(])”

Output: Not Balanced
Explanation: 1 and 4 brackets are not balanced because
there is a closing ‘]’ before the closing ‘(‘

Solution:

Code:

// C++ program to check for balanced brackets.

#include <bits/stdc++.h>
using namespace std;

// Function to check if brackets are balanced

bool areBracketsBalanced(string expr)
{
// Declare a stack to hold the previous brackets.
stack<char> temp;
for (int i = 0; i < expr.length(); i++) {
if (temp.empty()) {

// If the stack is empty

// just push the current bracket
temp.push(expr[i]);
}
else if ((temp.top() == '(' && expr[i] == ')')
|| (temp.top() == '{' && expr[i] == '}')
|| (temp.top() == '[' && expr[i] == ']')) {

// If we found any complete pair of bracket

// then pop
temp.pop();
}
 else {
temp.push(expr[i]);
}
}
if (temp.empty()) {

// If stack is empty return true

return true;
}
return false;
}

// Driver code
int main()
{
string expr = "{()}[]";

// Function call
if (areBracketsBalanced(expr))
cout << "Balanced";
else
cout << "Not Balanced";
return 0;
}

Question 3. Given a stack of integers, sort it in ascending order using another temporary stack.

Examples:

Input : [34, 3, 31, 98, 92, 23]

Output : [3, 23, 31, 34, 92, 98]

Input : [3, 5, 1, 4, 2, 8]

Output : [1, 2, 3, 4, 5, 8]

Solution:

Code:
// C++ program to sort a stack using an
// auxiliary stack.
#include <bits/stdc++.h>
using namespace std;
// This function return the sorted stack
stack<int> sortStack(stack<int> &input)
{
stack<int> tmpStack;

while (!input.empty())
{
// pop out the first element
int tmp = input.top();
input.pop();

// while temporary stack is not empty and top

// of stack is lesser than temp
while (!tmpStack.empty() && tmpStack.top() < tmp)
{
// pop from temporary stack and push
// it to the input stack
input.push(tmpStack.top());
tmpStack.pop();
}

// push temp in temporary of stack

tmpStack.push(tmp);
}

return tmpStack;
}

// main function
int main()
{
stack<int> input;
input.push(34);
input.push(3);
input.push(31);
input.push(98);
input.push(92);
input.push(23);

// This is the temporary stack

stack<int> tmpStack = sortStack(input);
cout << "Sorted numbers are:\n";

while (!tmpStack.empty())
{
 cout << tmpStack.top()<< " ";
tmpStack.pop();
}
}

Section 3 Hard (3 Questions)

Question1. Given a stack, the task is to reverse the stack using the queue data structure.

Examples:

Input: Stack: (Top to Bottom) [10 -> 20 -> 30 -> 40]

Output: Stack: (Top to Bottom) [40 -> 30 -> 20 -> 10]

Input: Stack: [6 -> 5 -> 4]

Output: Stack: [4 -> 5 -> 6]

Solution:

Pseudocode:
// C++ code to reverse a stack using queue
#include <bits/stdc++.h>
using namespace std;

void reverse(stack<int>& stk)

{
queue<int> qu;

// Enqueue all into queue

while (!stk.empty()) {
qu.push(stk.top());
stk.pop();
}

// Now stack is empty thus push all

// elements back into the
// stack - FIFO order
while (!qu.empty()) {
 stk.push(qu.front());
qu.pop();
}
}

// Driver Code
int main()
{
stack<int> stk;
stk.push(40);
stk.push(30);
stk.push(20);
stk.push(10);

// Function Call
reverse(stk);

// 40 30 20 10 (top to bottom)
cout << "After Reverse : (Top to Bottom)"
<< "\n";
while (!stk.empty()) {
cout << stk.top() << " ";
stk.pop();
}
cout << "\n";

return 0;
}

Question2. Given a postfix expression, the task is to evaluate the postfix expression.

Input: str = “2 3 1 * + 9 -“

Output: -4

Explanation: If the expression is converted into an infix expression, it will be 2 + (3 * 1) – 9 = 5

– 9 = -4.

Input: str = “100 200 + 2 / 5 * 7 +”

Output: 757

Solution:

Pseudocode:
// C++ program to evaluate value of a postfix expression
#include <bits/stdc++.h>
using namespace std;

// The main function that returns value

// of a given postfix expression
int evaluatePostfix(string exp)
{
// Create a stack of capacity equal to expression size
stack<int> st;

// Scan all characters one by one

for (int i = 0; i < exp.size(); ++i) {

// If the scanned character is an operand

// (number here), push it to the stack.
if (isdigit(exp[i]))
st.push(exp[i] - '0');

// If the scanned character is an operator,

// pop two elements from stack apply the operator
else {
int val1 = st.top();
st.pop();
int val2 = st.top();
st.pop();
switch (exp[i]) {
case '+':
st.push(val2 + val1);
break;
case '-':
st.push(val2 - val1);
break;
case '*':
st.push(val2 * val1);
break;
case '/':
st.push(val2 / val1);
break;
}
}
}
return st.top();
}

// Driver code
int main()
{
string exp = "231*+9-";

// Function call
cout << "postfix evaluation: " << evaluatePostfix(exp);
return 0;
}

Question3. Write a program to convert an Infix expression to Postfix form.

Examples:

Input: A + B * C + D
Output: ABC*+D+

Input: ((A + B) – C * (D / E)) + F

Output: AB+CDE/*-F+

Solution

Pseudocode:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Function to return precedence of operators

int prec(char c) {
if (c == '^')
return 3;
else if (c == '/' || c == '*')
return 2;
else if (c == '+' || c == '-')
return 1;
else
return -1;
}

// Function to return associativity of operators

char associativity(char c) {
if (c == '^')
return 'R';
return 'L'; // Default to left-associative
}

// The main function to convert infix expression to postfix expression

void infixToPostfix(char s[]) {
char result[1000];
int resultIndex = 0;
int len = strlen(s);
char stack[1000];
int stackIndex = -1;

for (int i = 0; i < len; i++) {

char c = s[i];

// If the scanned character is an operand, add it to the output string.

if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9')) {
result[resultIndex++] = c;
}
// If the scanned character is an ‘(‘, push it to the stack.
else if (c == '(') {
stack[++stackIndex] = c;
}
// If the scanned character is an ‘)’, pop and add to the output string from the stack
// until an ‘(‘ is encountered.
else if (c == ')') {
while (stackIndex >= 0 && stack[stackIndex] != '(') {
result[resultIndex++] = stack[stackIndex--];
}
stackIndex--; // Pop '('
}
// If an operator is scanned
else {
while (stackIndex >= 0 && (prec(s[i]) < prec(stack[stackIndex]) ||
prec(s[i]) == prec(stack[stackIndex]) &&
associativity(s[i]) == 'L')) {
result[resultIndex++] = stack[stackIndex--];
}
stack[++stackIndex] = c;
}
}

// Pop all the remaining elements from the stack

while (stackIndex >= 0) {
result[resultIndex++] = stack[stackIndex--];
}

result[resultIndex] = '\0';
printf("%s\n", result);
}
// Driver code
int main() {
char exp[] = "a+b*(c^d-e)^(f+g*h)-i";

// Function call
infixToPostfix(exp);

return 0;
}