Reversing a string in C using stack in linked list

Question

I am trying to reverse a given string using stacks. I am using linked lists as it takes up less memory compared to arrays. Here is my code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define M 100

struct Stack{
    char ele;
    struct Stack *next;
};

struct Stack* next_node(char element){
    struct Stack *node=(struct Stack *)malloc(sizeof(struct Stack));
    node->ele=element;
    node->next=NULL;
    return node;
}

int isEmpty(struct Stack *node){
    return node==NULL;
}

void push(struct Stack **node, char element){
    struct Stack *temp=next_node(element);
    temp->next=*node;
    *node=temp;
}

char pop(struct Stack **node){
    if(isEmpty(*node)){
        return 'a';
    }
    struct Stack *temp=*node;
    *node=(*node)->next;
    free(temp);
}

void rev(char str[]){
    int i;
    int n=strlen(str);
    struct Stack *s=(struct Stack *)malloc(sizeof(struct Stack));
    for(i=0;i<n;i++)
        push(&s, str[i]);
    for(i=0;i<n;i++)
        str[i]=pop(&s);
    printf("The reversed string is: %s\n", str);
}

int main()
{
    char string[M], op[1];
    do{
        printf("Enter the string to be reversed: ");
        scanf("%s", string);
        rev(string);
        printf("Do you want to go again?(Y/N): ");
        scanf("%s", op);
    }while(op[0]=='Y');
}

However, I do not get any output, it simply says, "The reversed string is: "

I tried a slightly different code by replacing

node->ele=element;

with

strcpy(node->ele, element);

But this gives me a warning, which says:

warning: passing argument 1 of 'strcpy' makes pointer from integer without a cast

I can't wrap my head around why such things is happening. Any help is appreciated! :-)

Why don't you just swap the characters around? Regarding the warning, `strcpy` expects pointers to `char`s not `char`s themselves. The `char` is implicitly converted to `char*` and that certainly isn't what you want, and will result in errors not just a warning. — Emanuel P, Apr 12 '21 at 08:28
@EmanuelP so you are suggesting I should make another swap() method for these two characters? — Jayajit, Apr 12 '21 at 08:34
I'm asking you why you use a stack/linked list structure. You can reverse a string simply by swapping the last character with the first and doing so until you reached the center. See the answer posted in meantime. — Emanuel P, Apr 12 '21 at 08:41

score 2 · Answer 1 · answered Apr 12 '21 at 08:40

You could skip the stack entirely and do something simpler and faster like this:

void rev(char str[])
{
    int i;
    int n = strlen(str);
    
    for(i=0; i<n/2; i++) {
        char tempChar = str[i];
        str[i] = str[n-i-1];
        str[n-i-1] = tempChar;
    }
    printf("The reversed string is: %s\n", str);
}

Basically, just step halfway through the string (not including the middle character if the length is odd), and swap characters from the left half and the right half of the string.

thanks for the answer, but I am familiar with this solution. I'm looking for a stack implementation. This is to explore how the stack data structure can be applied. — Jayajit, Apr 12 '21 at 08:43

score 0 · Answer 2 · answered Apr 12 '21 at 08:55

First of all, don't cast the result of malloc() and always check that it doesn't return NULL. Following what is written here, it's also better to write struct Stack *s = malloc(sizeof(*s)); (the parentheses around *s are optional because it's a variable instead of a type).

As for your reasoning, I'm not sure that a linked list actually uses less memory than arrays. Given n the number of elements and size the size of a single one in bytes, an array always uses n * size bytes of contiguously allocated memory, so it's also very efficient and fast to access all of its elements; a linked list has to keep for each node the pointer to the next one, so it needs n * size + n * 8 bytes and the nodes can be stored all over your memory, so they're also less efficient and slower to access in a very big list.

Since you're just reversing a string you don't need a data structure that can grow dinamically at runtime, or at the very least you can just allocate a new array of the right size at each iteration of your main loop. If you want to try out some cool excercises with linked lists you can try different versions with head insert (a stack), tail insert (a queue), or sorted insert; then when you have the basic data structures done you can use them to solve other problems like writing a postfix calculator or checking if the parentheses in a string are balanced.

score 0 · Accepted Answer · answered Apr 12 '21 at 09:33

There are some bugs in your code:

the very first element you allocate in rev is never initialized, and therefore it contains garbage. Just don't allocate this but let push do all the work.
the pop function doesn't return anything, it needs to return the char you pop from the stack.

char pop(struct Stack** node) {
  if (isEmpty(*node)) {
    return 0;                // return 0, not 'a'. Anyway this should never happen
  }
  struct Stack* temp = *node;
  *node = (*node)->next;
  char retval = temp->ele;   // retrieve char to return
  free(temp);
  return retval;             // return the char
}

void rev(char str[]) {
  int i;
  int n = strlen(str);
  struct Stack* s = NULL;   // don't allocate anything here, just set it to NULL,
                            // but this is not even necessary here.
  for (i = 0; i < n; i++)
    push(&s, str[i]);
  for (i = 0; i < n; i++)
    str[i] = pop(&s);

  printf("The reversed string is: %s\n", str);
}

Reversing a string in C using stack in linked list

3 Answers3