Question: C Programming: linked list stack implementation using 2 queues. ****NOTE: I need both code AND an explanation with the code provided. MUST be in C
C Programming: linked list stack implementation using 2 queues.
****NOTE: I need both code AND an explanation with the code provided. MUST be in C (NOT C++) in a SINGLE FILE (stack_from_queue.c). If the answer is meets the requirements below, I WILL give awesome reviews!!
INSTRUCTIONS: Use two instances of Queue data structures to implement a Stack. You MUST use only one C file to design the entire interface. The file must be named stack_from_queue.c.
Requirements:
- Program is written in C language;
- Uses the following headers:
#include
#include
#include
- All the stack functions provided in Worksheet 17 (see below) are implemented using the queue functions provided in Worksheet 18 (see below)
- You are able to test stack_from_queue implementation by pushing, checking the top, and popping.
- Finally, the file MUST be able to run using ONLY THIS gcc command
gcc -g -Wall -std=c99 -o stack_from_queue stack_from_queue.c
************************* Worksheet 17: linked list STACK Functions ****************************
struct link {
TYPE value;
struct link *next;
};
struct linkedListStack {
struct link *firstLink;
}
*********Functions start here *********
void linkedListStackInit (struct linkedListStack * s) {
s->firstLink = 0;
}
void linkedListStackFree (struct linkedListStack *s) {
while(! linkedListStackIsEmpty(s))
linkedListStackPop(s);
}
void linkedListStackPush (struct linkedListStack *s, TYPE d) {
struct link * newLink=(struct link *)malloc(sizeof(struct link));
assert (newLink != 0);
newLink->value = d; /* Set data fields in the new link. */
newLink->next = sfirstLink;
s->firstLink = newLink; /*Assign firstLink to pt to newLink */
}
TYPE linkedListStackTop (struct linkedListStack *s) {
assert(! linkedListStackIsEmpty(s));
return s->firstLink->value;
}
void linkedListStackPop (struct linkedListStack *s) {
struct link *temp = s->firstLink; /*1. create a temp link*/
assert (! linkedListStackIsEmpty(s)); /*2. check it */
s->firstLink = tempnext; /*3. Update pointers*/
free(temp); /*4. free memory for popped element*/
}
int linkedListStackIsEmpty (struct linkedListStack *s) {
return s->firstLink == 0;
}
************************ Worksheet 18: linkedList QUEUE Functions **********************************
struct link {
TYPE value;
struct link *next;
};
struct listQueue {
struct link *firstLink;
struct link *lastLink;
};
void listQueueInit (struct listQueue *q) {
struct link *lnk = (struct link *) malloc(sizeof(struct link));
assert(lnk != 0); /* lnk is the sentinel */
lnk->next = 0;
q->firstLink = q->lastLink = lnk;
}
void listQueueAddBack (struct listQueue *q, TYPE e) {
struct link *lnk = (struct link *) malloc(sizeof(struct link));
assert(lnk != 0); /*allocate memory for new link*/
lnk->value = e;
lnk->next = 0;
q->lastLink->next = lnk; /*make tail ptr point to new link*/
q->lastLink = lnk;
}
TYPE listQueueFront (struct listQueue *q) {
assert(! listQueueIsEmpty(q));
return q->firstLink->value; /*get element in front of queue*/
}
void listQueueRemoveFront (struct listQueue *q) {
struct link *lnk = q->firstLink->next;
assert (! listQueueIsEmpty(q));
if (q->firstLink->next->next == 0) /*check if list is empty*/
{ q->lastLink = q->firstLink; /*if Y, set lastLnk=firstLnk*/
}
q->firstLink->next = lnk->next; /*change ptr to next element*/
free(lnk);
}
int listQueueIsEmpty (struct listQueue *q) {
return q->firstLink == q->lastLink;
}
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help