thecoderenroute

Checking for Palindrome with douvle sided queue

Oct 6th, 2020
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.54 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include <iostream>
  3. #include <string>
  4.  
  5. using std::cin;
  6. using std::cout;
  7.  
  8. void print(struct node *p, struct node *pb);
  9. void enqueue(struct node **p, struct node **pb, char dataToAdd);
  10. void deque(struct node **p, struct node **pb);
  11. void peek(struct node *p);
  12. void enqueue2(struct node **p, struct node **pb, char dataToAdd);
  13. void deque2(struct node **p, struct node **pb);
  14. void peek2(struct node *pb);
  15. bool isPalindrome(struct node *p, struct node *q);
  16.  
  17. struct node
  18. {
  19.     char data;
  20.     struct node *link;
  21. };
  22.  
  23. int main()
  24. {
  25.     struct node *front = (struct node *)malloc(sizeof(struct node));
  26.     front = NULL;
  27.  
  28.     struct node *rear = (struct node *)malloc(sizeof(struct node));
  29.     rear = front;
  30.  
  31.     while (true)
  32.     {
  33.         cout << "\nEnter your choice: \n1. Enque\n2. Deque\n3. Peek\n4. View all\n5. Check if palindrome\n6. Exit\n";
  34.         int ch;
  35.         cin >> ch;
  36.  
  37.         if (ch == 6)
  38.         {
  39.             break;
  40.         }
  41.  
  42.         int db;
  43.         switch (ch)
  44.         {
  45.         case 1:
  46.             cout << "Enter element: ";
  47.             char data;
  48.             cin >> data;
  49.             cout << "1. Rear\n2. Front\n";
  50.             cin >> db;
  51.             if (db == 1)
  52.             {
  53.                 enqueue(&front, &rear, data);
  54.             }
  55.             else if (db == 2)
  56.             {
  57.                 enqueue2(&front, &rear, data);
  58.             }
  59.             break;
  60.         case 2:
  61.             cout << "1. Rear\n2. Front\n";
  62.             cin >> db;
  63.             if (db == 1)
  64.             {
  65.                 deque2(&front, &rear);
  66.             }
  67.             else if (db == 2)
  68.             {
  69.                 deque(&front, &rear);
  70.             }
  71.  
  72.             break;
  73.         case 3:
  74.             peek(rear);
  75.             break;
  76.         case 4:
  77.             cout << "\n";
  78.             print(front, rear);
  79.             break;
  80.         case 5:
  81.             if (isPalindrome(front, rear))
  82.             {
  83.                 cout << "\nThe end is the beginning and the beginning is the end!";
  84.             }
  85.             else
  86.             {
  87.                 cout << "\nNot a Palindrome!";
  88.             }
  89.             break;
  90.         default:
  91.             cout << "Invalid choice\n";
  92.         }
  93.     }
  94. }
  95.  
  96. void print(struct node *p, struct node *pb)
  97. {
  98.     struct node *t = p;
  99.     cout << "\n";
  100.     if (t == NULL)
  101.     {
  102.         cout << "Empty Queue\n";
  103.     }
  104.     else
  105.     {
  106.         while (true)
  107.         {
  108.             cout << t->data << " -> ";
  109.             t = t->link;
  110.             if (t == NULL)
  111.             {
  112.                 break;
  113.             }
  114.         }
  115.         cout << " NULL";
  116.     }
  117. }
  118.  
  119. void enqueue(struct node **p, struct node **pb, char dataToAdd)
  120. {
  121.     if (*pb == NULL)
  122.     {
  123.         struct node *temp = (struct node *)malloc(sizeof(struct node));
  124.  
  125.         temp->data = dataToAdd;
  126.         temp->link = NULL;
  127.         (*pb) = temp;
  128.         (*p) = temp;
  129.     }
  130.     else
  131.     {
  132.         struct node *temp = (struct node *)malloc(sizeof(struct node));
  133.         struct node *t = (*pb);
  134.         temp->data = dataToAdd;
  135.         temp->link = NULL;
  136.         t->link = temp;
  137.         t = t->link;
  138.         (*pb) = t;
  139.     }
  140. }
  141.  
  142. void deque(struct node **p, struct node **pb)
  143. {
  144.     struct node *t = (*p);
  145.     if (t == NULL)
  146.     {
  147.         cout << "Empty queue";
  148.     }
  149.     else if (t == (*pb))
  150.     {
  151.         (*pb) = NULL;
  152.         (*p) = NULL;
  153.     }
  154.     else
  155.     {
  156.         (*p) = (*p)->link;
  157.         free(t);
  158.     }
  159. }
  160.  
  161. void enqueue2(struct node **p, struct node **pb, char dataToAdd)
  162. {
  163.     if (*p == NULL)
  164.     {
  165.         struct node *temp = (struct node *)malloc(sizeof(struct node));
  166.  
  167.         temp->data = dataToAdd;
  168.         temp->link = NULL;
  169.         (*pb) = temp;
  170.         (*p) = temp;
  171.     }
  172.     else
  173.     {
  174.         struct node *temp = (struct node *)malloc(sizeof(struct node));
  175.         struct node *t = (*p);
  176.         temp->data = dataToAdd;
  177.         temp->link = t;
  178.         // t->link = temp;
  179.         // t = t->link;
  180.         t = temp;
  181.         (*p) = t;
  182.     }
  183. }
  184.  
  185. void deque2(struct node **p, struct node **pb)
  186. {
  187.     struct node *t = (*pb);
  188.     struct node *t1 = (*p);
  189.     if (t == NULL)
  190.     {
  191.         cout << "Empty queue";
  192.     }
  193.     else if (t == (*p))
  194.     {
  195.         (*pb) = NULL;
  196.         (*p) = NULL;
  197.     }
  198.     else
  199.     {
  200.  
  201.         while (1)
  202.         {
  203.             if (t1->link == (*pb))
  204.             {
  205.                 break;
  206.             }
  207.             t1 = t1->link;
  208.         }
  209.         (*pb) = t1;
  210.         (*pb)->link = NULL;
  211.         t1 = t1->link;
  212.         free(t1);
  213.     }
  214. }
  215.  
  216. void peek(struct node *p)
  217. {
  218.     if (p == NULL)
  219.     {
  220.         cout << "Empty queue";
  221.         return;
  222.     }
  223.     cout << p->data;
  224. }
  225.  
  226. void peek2(struct node *pb)
  227. {
  228.     if (pb == NULL)
  229.     {
  230.         cout << "Empty queue";
  231.         return;
  232.     }
  233.     cout << pb->data;
  234. }
  235.  
  236. bool isPalindrome(struct node *p, struct node *q)
  237. {
  238.     struct node *f = (struct node *)malloc(sizeof(struct node));
  239.     f = NULL;
  240.  
  241.     struct node *r = (struct node *)malloc(sizeof(struct node));
  242.     r = f;
  243.  
  244.     struct node *t = p;
  245.  
  246.     while (t != NULL)
  247.     {
  248.         enqueue(&f, &r, t->data);
  249.         t = t->link;
  250.     }
  251.  
  252.     // print(f, r);
  253.  
  254.     struct node *t1 = f, *t2 = r;
  255.     struct node *t3 = f;
  256.  
  257.     while (true)
  258.     {
  259.         if (t1 == t2 || t2 == t3)
  260.             break;
  261.  
  262.         if (t1->data != t2->data)
  263.         {
  264.             // cout << "False";
  265.             return false;
  266.         }
  267.  
  268.         t1 = t1->link;
  269.         deque2(&t1, &t2);
  270.     }
  271.     // cout << "True";
  272.     return true;
  273. }
Advertisement
Add Comment
Please, Sign In to add comment