Scribd
Upload
13 views5 pages

Assignment4

The document presents two programming problems: the Tower of Hanoi puzzle solved using recursion and the implementation of a FIFO queue using two stacks. The Tower of Hanoi problem involves moving disks between rods while following specific rules, and a recursive approach is provided along with sample code. The queue implementation details the use of two stacks to perform queue operations such as push, pop, peek, and check if empty, accompanied by sample code and input/output examples.

Uploaded by

musnu001
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
13 views5 pages

Assignment4

The document presents two programming problems: the Tower of Hanoi puzzle solved using recursion and the implementation of a FIFO queue using two stacks. The Tower of Hanoi problem involves moving disks between rods while following specific rules, and a recursive approach is provided along with sample code. The queue implementation details the use of two stacks to perform queue operations such as push, pop, peek, and check if empty, accompanied by sample code and input/output examples.

Uploaded by

musnu001
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Assignment #4 - Recursion, Stack, and Queue

Prepared by: 241004612

Course: Data Structures and Algorithms

Date: January 7, 2025

Problem 1: Tower of Hanoi using Recursion

Problem Statement:

The Tower of Hanoi is a mathematical puzzle consisting of three rods and n disks of different sizes,

which

can slide onto any rod. The puzzle starts with all the disks stacked in ascending order of size on the

first rod. The objective of the puzzle is to move the entire stack to the third rod, obeying the following

rules:

1. Only one disk can be moved at a time.

2. Each move consists of taking the upper disk from one stack and placing it on top of another stack.

3. No larger disk may be placed on top of a smaller disk.

Approach:

This problem can be solved recursively. The steps are:

1. Move the top n-1 disks from the source rod to the auxiliary rod.

2. Move the nth disk from the source rod to the target rod.

3. Move the n-1 disks from the auxiliary rod to the target rod.

Code Implementation:
#include <iostream>

using namespace std;

void towerOfHanoi(int n, char source, char target, char auxiliary) {

if (n == 1) {

cout << "Move disk 1 from " << source << " to " << target << endl;

return;

towerOfHanoi(n - 1, source, auxiliary, target);

cout << "Move disk " << n << " from " << source << " to " << target << endl;

towerOfHanoi(n - 1, auxiliary, target, source);

int main() {

int n = 3; // Number of disks

towerOfHanoi(n, 'A', 'C', 'B');

return 0;

Sample Input:

n=3

Sample Output:

Move disk 1 from A to C

Move disk 2 from A to B

Move disk 1 from C to B

Move disk 3 from A to C


Move disk 1 from B to A

Move disk 2 from B to C

Move disk 1 from A to C

Problem 2: Stack Implementation using Queue

Problem Statement:

Implement a first-in, first-out (FIFO) queue using only two stacks. The implemented queue should

support the following functions:

1. push(x): Push element x to the back of the queue.

2. pop(): Remove the element from the front of the queue and return it.

3. peek(): Return the element at the front of the queue.

4. empty(): Return true if the queue is empty, false otherwise.

Approach:

To implement a queue using stacks, use the following steps:

1. Use two stacks: inputStack and outputStack.

2. For push(x), add the element to inputStack.

3. For pop() and peek(), transfer elements from inputStack to outputStack if outputStack is empty,

then perform the operation on outputStack.

4. For empty(), check if both stacks are empty.

Code Implementation:

#include <stack>

using namespace std;


class MyQueue {

stack<int> inputStack, outputStack;

void transfer() {

while (![Link]()) {

[Link]([Link]());

[Link]();

public:

void push(int x) {

[Link](x);

int pop() {

if ([Link]()) transfer();

int topElement = [Link]();

[Link]();

return topElement;

int peek() {

if ([Link]()) transfer();

return [Link]();

}
bool empty() {

return [Link]() && [Link]();

};

Sample Input:

MyQueue q;

[Link](1);

[Link](2);

[Link](); // returns 1

[Link](); // returns 1

[Link](); // returns false

Sample Output:

false

You might also like