Background A palindrome is a string of characters that reads the same when read

Question

Background A palindrome is a string of characters that reads the same when read from left-to-right as when read from right-to-left. For example, afjassajfa and djkfjasajfkjd are palindromes, but akdfjaslfk is not.

Description of an algorithm Your algorithm should read in a string (from one line of standard input) and print out a message saying that the string is, or is not, a palindrome. Your algorithm may use constants, counters, and temporary variables (for storing single characters of the string), but it may not store the string in any structure other than the stack in part 1. and queue in part 2. For instance, you can not read it into an array or use an array in your algorithm.

Implementation In the implementation, you can assume that the input text consists only low-case letters from a to z. The input text will be terminated by [enter]. In your program, you may specify the maximum stack and/or queue sizes by using name constants. The attributes of a stack are the “top” and its “depth” while the attributes of a queue are the “head”, “tail”, and its “length”. Each instance of the stack and queue will have their own set of attributes. What to hand in Please submit a list of your programs (one for the stack and one for the queue), and the output (generated text) of your program on canvas. You should run your program on a command line on hillls by using the above three sample inputs

#include <iostream>

void create_stack(unsigned &t,unsigned &d,char s[]);
unsigned depth(const unsigned t,const unsigned d,char s[]);
void push(unsigned &t,unsigned &d,char s[],char std_element);
char pop(unsigned &t,unsigned &d,char s[]);
void terminate_stack(unsigned &t,unsigned &d,char s[]);
void create_queue(unsigned &h,unsigned &t,unsigned &l,char q[]);
unsigned length(const unsigned h,const unsigned t,const unsigned
l,char q[]);
void enqueue(unsigned &h,unsigned &t,unsigned &l,char q[],char
std_element);
char serve(unsigned &h,unsigned &t,unsigned &l,char q[]);
void terminate_queue(unsigned &h,unsigned &t,unsigned &l,char

int main() {
void create_stack(unsigned &t,unsigned &d,char s[]);
//results: the linear data structure, stack, is initialized

unsigned depth(const unsigned t,const unsigned d,char s[]);
//requires: create_stack() is already executed
//results: the current number of elements in the stack

void push(unsigned &t,unsigned &d,char s[],char std_element);
//requires: create_stack() is already executed and depth < ssize
//results: std_element is the most recently arrived element of the stack

char pop(unsigned &t,unsigned &d,char s[]);
//requires: create_stack() is already executed and 0 < depth
//results: the most recent element pushed onto the stack is retrieved and it is no longer on the stack s[]

void terminate_stack(unsigned &t,unsigned &d,char s[]);
//results: terminate the stack by resetting the top

void create_queue(unsigned &h,unsigned &t,unsigned &l,char q[]);
//results: the linear data structure, queue, is initialized (or created)

unsigned length(const unsigned h,const unsigned t,const unsigned
l,char q[]);
//requires: create_queue() is already executed
//results: the current number of elements in the queue

void enqueue(unsigned &h,unsigned &t,unsigned &l,char q[],char
std_element);
//requires: create_queue() is already executed and l < qsize
//results: std_element is the most recently arrived element of the queue

char serve(unsigned &h,unsigned &t,unsigned &l,char q[]);
//requires: create_queue() is already executed and 0 < l
//results: the longest waiting element enqueued onto the queue is served and it is no longer on the queue q[]

void terminate_queue(unsigned &h,unsigned &t,unsigned &l,char
q[]);
//results: terminate the queue by resetting both the h and the t

}

Part 2. Specification of the queue A queue is a linear data structure in which elements are ordered according to when(First In First Out) they are put on the queue. Elements on the queue are specified by user and we will use atomic data type, char, for this assignment. However, you should keep in mind that the elements shall be easily modified or re-defined in the future assignments void create_queue (unsigned &h;,unsigned &t;,unsigned &1,char qll)

Explanation / Answer

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 50
int top = -1,
front = 0;
int stack[MAX];
void push(char);
void pop();
void main()
{
int i, choice;
char s[MAX], b;
while (1)
{ printf("Menu: 1-enter string 2-exit "); printf("enter your choice ");
scanf("%d", &choice);
switch (choice) {
case 1: printf("Enter the String "); scanf("%s", s);
for (i = 0;s[i] != '';i++)
{ b = s[i]; push(b); }
for (i = 0;i < (strlen(s) / 2);i++)
{
if (stack[top] == stack[front])
{ pop(); front++; }
else
{ printf("%s is not a palindrome ", s); break; }
} if ((strlen(s) / 2) = = front)
printf("%s is palindrome ", s);
front = 0;
top = -1;
break;
case 2: exit(0);
default: printf("enter correct choice "); }
}
}
/* to push a character into stack */
void push(char a)
{ top++; stack[top] = a;}
/* to delete an element in stack */
void pop()
{ top--;}

Program Explanation-

1. Take a string as input and store it in the array s[].
2. Load each character of the array s[] into the array stack[].
3. Use variables front and top to represent the last and top element of the array stack[].
4. Using for loop compare the top and last element of the array stack[]. If they are equal, then delete the top element, increment the variable front by 1 and compare again.
5. If they are not equal, then print the output as “It is not a palindrome”.
6. Compare the elements in the steps 4-5 upto the middle element of the array stack[].
7. If every characters of the array is equal, then it is a paliandrome.

Runtime Test Cases-
Menu
1-enter string
2-exit
enter your choice
1 Enter the String
madam
madam is palindrome
Menu
1-enter string
2-exit l
enter your choice 1
Enter the String abccba
abccba is palindrome
Menu
1-enter string
2-exit
Enter your choice 2

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.