C Programming & Data Structures: Need help fixing code. File MUST be able to run

Question

C Programming & Data Structures: Need help fixing code. File MUST be able to run as a .c file (NOT .cpp)

My program is to implement a stack using two instances of queue data structures. It compiles just fine, but when I try running it, it says "Segmentation fault 11". I think the issue is with the init functions. but I can't figure out how to change them to get it to work.

Code MUST be able to compile using the command: "gcc -g -Wall -std=c99 -o stack_from_queue stack_from_queue.c". Code also must stay in a single file!

Here is the code I have:

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

#ifndef __TYPE
#define __TYPE
#define TYPE int
#endif

/******* structures *********/
/* link structure definition to implement singly linked lists for Queues*/
struct link {
TYPE value;
struct link *next;
};
/* definition of queue structure using a linked list for implementation*/
/* using LL requires keeping track of head & tail of the queue*/
struct listQueue {
struct link *firstLink;
struct link *lastLink;
};
/*definition of struct used to implement a stack using 2 queues */
struct stack {
struct listQueue *q1;
struct listQueue *q2;
};

/******* QUEUE FUNCTION DEFINITIONS **********/
/*function to initialize the queue */
struct listQueue* queue_init(struct listQueue *q) {
struct link *qlnk = (struct link *)malloc(sizeof(struct link));
assert(qlnk != 0);
qlnk->next = 0;
q->firstLink = qlnk;
q->lastLink = qlnk;
return q;
}
/* enqueue function--adds new link to back of the queue */
void queue_addBack(struct listQueue *q, TYPE e){
struct link *newL = (struct link *) malloc(sizeof(struct link));
assert(newL != 0); /*allocate memory for new link*/
newL->value = e;
newL->next = 0; /*set equal to NULL */
q->lastLink->next = newL; /*make tail ptr point to new link*/
q->lastLink = newL;
}
/* function returns value stored in firstLink @ front of the queue*/
TYPE queue_getFront(struct listQueue *q){
assert(q->firstLink != q->lastLink);
return q->firstLink->next->value; /*get element in front of queue*/
}

/*dequeue function--removes queue front value */
void queue_removeFront(struct listQueue *q){
assert(q->firstLink != q->lastLink);
struct link *temp = q->firstLink->next;
  
if(q->firstLink->next == q->lastLink){
q->firstLink = q->lastLink;
q->firstLink->next = NULL;
}
else {
q->firstLink->next = q->firstLink->next->next;
}
  
free(temp);
temp = NULL;
}
/*function to check queue is empty*/
int queue_isEmpty(struct listQueue *q){
if(q->firstLink == q->lastLink){
return 1;
}
else {
return 0;
}
}
/**************** STACK FUNCTION DEFINITIONS ****************/
/*initialize stack*/
struct stack* stack_init(){
struct stack *s = (struct stack *)malloc(sizeof(struct stack));
queue_init(s->q1);
queue_init(s->q2);
return s;
}

/*checks if stack is empty. returns 1 if empty, otherwise returns 0*/
int stack_isEmpty(struct stack *s){
if((queue_isEmpty(s->q1) != 0) && (queue_isEmpty(s->q2) != 0)){
return 1; /*return 1 if empty */
}
else {
return 0;
}
}
/*free memory */
void stack_Free(struct stack *s){
while(stack_isEmpty(s) != 1){
queue_removeFront(s->q1);
queue_removeFront(s->q2);
}
free(s);
}

/*push a new value onto the stack--i.e. add a value to the stack*/
void stack_Push(struct stack *s, TYPE d){
/*push value into empty q2*/
queue_addBack(s->q2, d);
/*push all remaining elements in q1 to q2*/
while(!queue_isEmpty(s->q1)){
queue_addBack(s->q2, queue_getFront(s->q1));
queue_removeFront(s->q1);
}
/*swap names of the 2 queues*/
struct listQueue *temp = s->q1;
s->q1 = s->q2;
s->q2 = temp;
}

/*gets & returns the value stored @ top of stack*/
TYPE stack_getTop(struct stack *s){
/*check if stack is empty*/
assert(!stack_isEmpty(s));
return queue_getFront(s->q1);
}

/*remove the top element from the stack*/
void stack_Pop(struct stack *s){
/*checks if stack is already empty*/
assert(! stack_isEmpty(s));
/*removes top of stack*/
queue_removeFront(s->q1);
}

/********************* int main *************************/
int main()
{
struct stack *s = stack_init();
int n = 6;
int m = 3;
/* Test stack-from-queues implementation by pushing, checking the top, and popping. */
printf(" ============================================= ");
printf("== Testing stack-from-queues implementation ");
printf("============================================= ");

printf("== Pushing some onto stack-from-queues:");
for (int i = 0; i < n; i++) {
int val = 2 * i;
printf(" %4d", val);
stack_Push(s, val);
}
printf(" ");
  
printf("== Popping some from stack-from-queues:");
for (int i = 0; i < m; i++) {
int top = stack_getTop(s);
printf(" %4d", top);
}
printf(" ");
  
printf("== Pushing more onto stack-from-queues:");
for (int i = n; i < n + m; i++) {
int val = 2 * i;
printf(" %4d", val);
stack_Push(s, val);
}
printf(" ");
  
printf("== Dequeueing rest from stack-from-queues:");
while (!stack_isEmpty(s)) {
int top = stack_getTop(s);
stack_Pop(s);
printf(" %4d", top);
}
printf(" ");
  
stack_Free(s);
  
return 0;
}

Explanation / Answer

The following stack_init function is having an issue.

It has to allocate memory to s->q1 and s->q2 and then call the queue_init function.

s->q1 = (struct listQueue *)malloc(sizeof(struct listQueue ));
s->q2 = (struct listQueue *)malloc(sizeof(struct listQueue ));

//The above line should be added to the queue_init function

--------------------Original function---------------------------------
struct stack* stack_init(){
struct stack *s = (struct stack *)malloc(sizeof(struct stack));
queue_init(s->q1);
queue_init(s->q2);
return s;
}

--------------------Modified function---------------------------------

struct stack* stack_init(){
struct stack *s = (struct stack *)malloc(sizeof(struct stack));
s->q1 = (struct listQueue *)malloc(sizeof(struct listQueue ));
s->q2 = (struct listQueue *)malloc(sizeof(struct listQueue ));
queue_init(s->q1);
queue_init(s->q2);
return s;
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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