Math Editor

Data Structures Report

Tower of Hanoi

The objective of the problem is to move the entire stack of disks from one peg (the source) to another peg (the destination), using the third peg (the auxiliary) as temporary storage.

The rules for the Tower of Hanoi puzzle are as follows:

1. Only 1 disk can be moved at a time.
2. Each move consists of taking the topmost disk from one of the stacks and placing it on top of another stack or an empty peg.
3. A larger disk must never be placed on top of a smaller disk.

Solution using stack:

#include <stdio.h>
#include <stdlib.h>
struct stack
{
  int *arr;
  int top;
  int size;
};
struct stack *createStack(int size)
{
  struct stack *s = (struct stack *)malloc(sizeof(struct stack));
  s->arr = (int *)malloc(sizeof(int) * size);
  s->top = -1;
  s->size = size;
  return s;
}
int isFull(struct stack *s)
{
  return s->top == s->size - 1;
}
int isEmpty(struct stack *s)
{
  return s->top == -1;
}
void push(struct stack *s, int item)
{
  if (isFull(s))
  {
    printf("Stack Overflow!\n");
    return;
  }
  s->arr[++s->top] = item;
}
int pop(struct stack *s)
{
  if (isEmpty(s))
  {
    printf("Stack Underflow!\n");
    return -1;
  }
  return s->arr[s->top--];
}
void printTOH(struct stack *towers[])
{
  int n = towers[0]->size;
  for (int i = n - 1; i >= 0; i--)
  {
    for (int j = 0; j < 3; j++)
    {
      if (towers[j]->top >= i)
      {
        int disk = towers[j]->arr[i];
        printf("%d\t", disk);
      }
      else
      {
        printf("\t");
      }
    }
    printf("\n");
  }
  printf("-----------------\n");
}
void TOH(int n, int src, int dest, struct stack *towers[])
{
  struct stack *srcStack = towers[src - 1];
  struct stack *destStack = towers[dest - 1];

  if (n == 1)
  {
    printf("Move disk %d from tower %d to tower %d\n", n, src, dest);
    push(destStack, pop(srcStack));
    printTOH(towers);
    return;
  }
  else
  {
    int aux = 6 - src - dest;
    TOH(n - 1, src, aux, towers);
    printf("Move disk %d from tower %d to tower %d\n", n, src, dest);
    push(destStack, pop(srcStack));
    printTOH(towers);
    TOH(n - 1, aux, dest, towers);
  }
}
int main()
{
  int n, src, dest;
  printf("Enter the number of disks, source and destination tower number (1-3): ");
  scanf("%d%d%d", &n, &src, &dest);

  struct stack *towers[3] = {createStack(n), createStack(n), createStack(n)};
  for (int i = n; i > 0; i--)
    push(towers[src - 1], i);

  printTOH(towers);
  TOH(n, src, dest, towers);
  return 0;
}

Interleaving queue

Given a queue of integers of even length, rearrange the elements by interleaving the first half of the queue with the second half of the queue.  

Example:

Input : 11 12 13 14 15 16 17 18 19 20
Output : 11 16 12 17 13 18 14 19 15 20

Solution using queue:

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

struct queue
{
  int *arr;
  int front;
  int rear;
  int size;
};

struct queue *createQueue(int size)
{
  struct queue *q = (struct queue *)malloc(sizeof(struct queue));
  q->arr = (int *)malloc(sizeof(int) * size);
  q->front = -1;
  q->rear = -1;
  q->size = size;
  return q;
}
int isFull(struct queue *q)
{
  return q->rear == q->size - 1;
}
int isEmpty(struct queue *q)
{
  return q->front == -1;
}
void enqueue(struct queue *q, int item)
{
  if (isFull(q))
  {
    printf("Queue Overflow!\n");
    return;
  }
  q->arr[++q->rear] = item;
  if (q->front == -1)
    q->front = 0;
}
int dequeue(struct queue *q)
{
  if (isEmpty(q))
  {
    printf("Queue Underflow!\n");
    return -1;
  }
  int item = q->arr[q->front];
  if (q->front == q->rear)
    q->front = q->rear = -1;
  else
    q->front++;
  return item;
}
void printQueue(struct queue *q)
{
  if (isEmpty(q))
  {
    printf("Queue is empty!\n");
    return;
  }
  for (int i = q->front; i <= q->rear; i++)
    printf("%d\t", q->arr[i]);
  printf("\n");
}
void interleave(struct queue *q)
{
  int n = q->rear - q->front + 1;
  int half = n / 2;
  struct queue *q1 = createQueue(half);
  struct queue *q2 = createQueue(half + n % 2);
  for (int i = 0; i < half; i++)
    enqueue(q1, dequeue(q));

  for (int i = 0; i < half + n % 2; i++)
    enqueue(q2, dequeue(q));

  for (int i = 0; i < half; i++)
  {
    enqueue(q, dequeue(q1));
    enqueue(q, dequeue(q2));
  }

  if (!isEmpty(q2))
    enqueue(q, dequeue(q2));
}

int main()
{
  struct queue *q = createQueue(12);
  for (int i = 1; i <= q->size; i++)
    enqueue(q, i);
  printf("Queue before interleaving:\n");
  printQueue(q);
  interleave(q);
  printf("Queue after interleaving:\n");
  printQueue(q);
  return 0;
}