0

I'm implementing a stack using two queues. I'm quite familiar with the algorithm, and have prepared the following code where the push operation is costly:

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

struct queue_struct{
    int ele;
    struct queue_struct *next;
};

struct Queue{
    struct queue_struct *front, *rear;
};

struct Stack{
    struct Queue *q1, *q2;
};

void enqueue(struct Queue *q, int x){
    struct queue_struct *temp=malloc(sizeof(*temp));
    temp->ele=x;
    temp->next=NULL;
    if(q->rear!=NULL){
        q->rear->next=temp;
    }
    q->rear=temp;
    if(q->front==NULL)
        q->front=temp;
    //printf("The item %d has been enqueued into the queue\n", x);
}

void dequeue(struct Queue *q){
    struct queue_struct *temp=q->front;
    if(temp==NULL){
        //printf("The queue is already empty. No more elements can be removed!\n");
        return;
    }
    printf("The item %d has been popped from the stack\n", temp->ele);
    q->front=temp->next;
    if(q->rear==temp)
        q->rear=NULL;
    free(temp);
}

void push(struct Stack *s, int x){
    enqueue(s->q2, x);
    while(!(s->q1->front==NULL)){
        enqueue(s->q2, s->q1->front->ele);
        dequeue(s->q1);
    }
    struct Queue *q=s->q1;
    s->q1=s->q2;
    s->q2=q;
    printf("The item %d has been pushed into the stack\n", x);
}

void pop(struct Stack *s){
    if(s->q1->front==NULL){
        printf("The stack is already empty. No more elements can be removed!\n");
        return;
    }
    dequeue(s->q1);
}

void display(struct Stack *s){
    struct queue_struct *temp=s->q1->front;
    printf("The contents of the queue are:\n");
    if(temp==NULL){
        printf("Nothing to be shown, the queue is empty.\n");
        return;
    }
    for(int i=0;temp!=NULL;temp=temp->next){
        if(i){
            printf(" ------ \n");
        }
        printf("|  %d  |\n", temp->ele);
        i=1;
    }
}

int main()
{
    int choice, element;
    struct Stack *s=malloc(sizeof(*s));
    s->q1->front=s->q1->rear=NULL;
    s->q2->front=s->q2->rear=NULL;
    printf("LET'S START WITH AN EMPTY STACK\n\n");
    while(1){
        printf("MENU\n");
        printf("----\n");
        printf("\t1. Push an element\n");
        printf("\t2. Pop an element\n");
        printf("\t3. Display stack\n");
        printf("\t4. Exit\n");
        printf("Enter your choice: ");
        scanf("%d", &choice);
        switch(choice){
            case 1: printf("Enter the element to be pushed: ");
                    scanf("%d", &element);
                    push(s, element);
                    break;
            case 2: pop(s);
                    break;
            case 3: display(s);
                    break;
            case 4: printf("Program terminated successfully!");
                    return 0;
            default: printf("Invalid input");
        }
    }
}

However, I'm getting a Segmentation fault for the line(s): s->q1->front=s->q1->rear=NULL;. I'm not really sure why it is happening and how to fix it. Any help is appreciated.

6
  • 1
    Looks like q1 and q2 members of Stack are uninitialized at that point. Commented May 4, 2021 at 13:48
  • You have only allocated s, but s->q1, yet you are trying to dereference it Commented May 4, 2021 at 13:49
  • @FredLarson but I have mentioned in struct Stack that they are part of s. Won't that be enough? Commented May 4, 2021 at 13:50
  • 1
    s->q1 is a pointer. Where would it point to? Commented May 4, 2021 at 13:50
  • 1
    @FredLarson Oh, now I get it, I have to allocate memory for q1 and q2 too! Thanks Commented May 4, 2021 at 13:51

1 Answer 1

4

You invoked undefined behavior by using values in buffer allocated via malloc() and not initialized.

You have to initialize s->q1 and s->q2 before dereferencing them.

struct Stack *s=malloc(sizeof(*s));
if (s == NULL) return 1; /* check if allocation succeeded */
s->q1 = malloc(sizeof(*s->q1)); /* allocate for s->q1 */
s->q2 = malloc(sizeof(*s->q2)); /* allocate for s->q2 */
if (s->q1 == NULL || s->q2 == NULL) return 1; /* check if allocations succeeded */
s->q1->front=s->q1->rear=NULL;
s->q2->front=s->q2->rear=NULL;
Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.