Verifique si la string dada es Palindrome usando Stack

Dada la string str , la tarea es encontrar si la string dada es un palíndromo o no usando una pila .

Ejemplos:  

Entrada: str = «geeksforgeeks» 
Salida: No
Entrada: str = «madam» 
Salida: Sí  

Acercarse:  

• Encuentre la longitud de la string, digamos len . Ahora, encuentre el medio como medio = len / 2 .
• Empuje todos los elementos hasta la mitad de la pila, es decir , str[0…mid-1] .
• Si la longitud de la string es impar, desprecie el carácter del medio.
• Hasta el final de la string, siga extrayendo elementos de la pila y compárelos con el carácter actual, es decir, string[i] .
• Si no coincide, la string no es un palíndromo. Si todos los elementos coinciden, la string es un palíndromo.

A continuación se muestra la implementación del enfoque anterior: 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function that returns true
// if string is a palindrome
bool isPalindrome(string s)
{
    int length = s.size();
 
    // Creating a Stack
    stack<char> st;
 
    // Finding the mid
    int i, mid = length / 2;
 
    for (i = 0; i < mid; i++) {
        st.push(s[i]);
    }
 
    // Checking if the length of the string
    // is odd, if odd then neglect the
    // middle character
    if (length % 2 != 0) {
        i++;
    }
   
    char ele;
    // While not the end of the string
    while (s[i] != '\0')
    {
         ele = st.top();
         st.pop();
 
    // If the characters differ then the
    // given string is not a palindrome
    if (ele != s[i])
        return false;
        i++;
    }
 
return true;
}
 
// Driver code
int main()
{
    string s = "madam";
 
    if (isPalindrome(s)) {
        cout << "Yes";
    }
    else {
        cout << "No";
    }
 
    return 0;
}
 
// This Code is Contributed by Harshit Srivastava

// C implementation of the approach
#include <malloc.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
char* stack;
int top = -1;
 
// push function
void push(char ele)
{
    stack[++top] = ele;
}
 
// pop function
char pop()
{
    return stack[top--];
}
 
// Function that returns 1
// if str is a palindrome
int isPalindrome(char str[])
{
    int length = strlen(str);
 
    // Allocating the memory for the stack
    stack = (char*)malloc(length * sizeof(char));
 
    // Finding the mid
    int i, mid = length / 2;
 
    for (i = 0; i < mid; i++) {
        push(str[i]);
    }
 
    // Checking if the length of the string
    // is odd, if odd then neglect the
    // middle character
    if (length % 2 != 0) {
        i++;
    }
 
    // While not the end of the string
    while (str[i] != '\0') {
        char ele = pop();
 
        // If the characters differ then the
        // given string is not a palindrome
        if (ele != str[i])
            return 0;
        i++;
    }
 
    return 1;
}
 
// Driver code
int main()
{
    char str[] = "madam";
 
    if (isPalindrome(str)) {
        printf("Yes");
    }
    else {
        printf("No");
    }
 
    return 0;
}

// Java implementation of the approach
class GFG
{
static char []stack;
static int top = -1;
 
// push function
static void push(char ele)
{
    stack[++top] = ele;
}
 
// pop function
static char pop()
{
    return stack[top--];
}
 
// Function that returns 1
// if str is a palindrome
static int isPalindrome(char str[])
{
    int length = str.length;
 
    // Allocating the memory for the stack
    stack = new char[length * 4];
 
    // Finding the mid
    int i, mid = length / 2;
 
    for (i = 0; i < mid; i++)
    {
        push(str[i]);
    }
 
    // Checking if the length of the String
    // is odd, if odd then neglect the
    // middle character
    if (length % 2 != 0)
    {
        i++;
    }
 
    // While not the end of the String
    while (i < length)
    {
        char ele = pop();
 
        // If the characters differ then the
        // given String is not a palindrome
        if (ele != str[i])
            return 0;
        i++;
    }
 
    return 1;
}
 
// Driver code
public static void main(String[] args)
{
    char str[] = "madam".toCharArray();
 
    if (isPalindrome(str) == 1)
    {
        System.out.printf("Yes");
    }
    else
    {
        System.out.printf("No");
    }
}
}
 
// This code is contributed by PrinciRaj1992

# Python3 implementation of the approach
stack = []
top = -1
 
# push function
def push(ele: str):
    global top
    top += 1
    stack[top] = ele
 
# pop function
def pop():
    global top
    ele = stack[top]
    top -= 1
    return ele
 
# Function that returns 1
# if str is a palindrome
def isPalindrome(string: str) -> bool:
    global stack
    length = len(string)
 
    # Allocating the memory for the stack
    stack = ['0'] * (length + 1)
 
    # Finding the mid
    mid = length // 2
    i = 0
    while i < mid:
        push(string[i])
        i += 1
 
    # Checking if the length of the string
    # is odd, if odd then neglect the
    # middle character
    if length % 2 != 0:
        i += 1
 
    # While not the end of the string
    while i < length:
        ele = pop()
 
        # If the characters differ then the
        # given string is not a palindrome
        if ele != string[i]:
            return False
        i += 1
    return True
 
# Driver Code
if __name__ == "__main__":
 
    string = "madam"
 
    if isPalindrome(string):
        print("Yes")
    else:
        print("No")
 
# This code is contributed by
# sanjeev2552

// C# implementation of the approach
using System;
 
class GFG
{
 
static char []stack;
static int top = -1;
 
// push function
static void push(char ele)
{
    stack[++top] = ele;
}
 
// pop function
static char pop()
{
    return stack[top--];
}
 
// Function that returns 1
// if str is a palindrome
static int isPalindrome(char []str)
{
    int length = str.Length;
 
    // Allocating the memory for the stack
    stack = new char[length * 4];
 
    // Finding the mid
    int i, mid = length / 2;
 
    for (i = 0; i < mid; i++)
    {
        push(str[i]);
    }
 
    // Checking if the length of the String
    // is odd, if odd then neglect the
    // middle character
    if (length % 2 != 0)
    {
        i++;
    }
 
    // While not the end of the String
    while (i < length)
    {
        char ele = pop();
 
        // If the characters differ then the
        // given String is not a palindrome
        if (ele != str[i])
            return 0;
        i++;
    }
    return 1;
}
 
// Driver code
public static void Main(String[] args)
{
    char []str = "madam".ToCharArray();
 
    if (isPalindrome(str) == 1)
    {
        Console.Write("Yes");
    }
    else
    {
        Console.Write("No");
    }
}
}
 
// This code is contributed by 29AjayKumar

<script>
// Javascript implementation of the approach
 
// Function that returns true
// if string is a palindrome
function isPalindrome(s)
{
    var length = s.length;
 
    // Creating a Stack
    var st = [];
 
    // Finding the mid
    var i, mid = parseInt(length / 2);
 
    for (i = 0; i < mid; i++) {
        st.push(s[i]);
    }
 
    // Checking if the length of the string
    // is odd, if odd then neglect the
    // middle character
    if (length % 2 != 0) {
        i++;
    }
   
    var ele;
    // While not the end of the string
    while (i != s.length)
    {
         ele = st[st.length-1];
         st.pop();
 
    // If the characters differ then the
    // given string is not a palindrome
    if (ele != s[i])
        return false;
        i++;
    }
 
return true;
}
 
// Driver code
var s = "madam";
if (isPalindrome(s)) {
    document.write( "Yes");
}
else {
    document.write( "No");
}
 
</script>

Yes

Complejidad temporal : O(N).
Espacio Auxiliar : O(N).