Objectives:
• Learn how to implement generic stack and queue.
Description:
The follows are all structs you need for this lab:
typedef struct { typedef struct stackNode {
int id; void * item;
int age; struct stackNode * next;
} Student; } Stack;
typedef struct queueNode { typedef struct {
void * item; QueueNode * front;
struct queueNode * next; QueueNode * rear;
} QueueNode; } Queue;
Implement the following operations of a queue and a stack with O(1) average run time.
• Stack *push(Stack *top, void *item) o Push an item to the top of stack.
o Returns the updated top pointer.
• Stack *pop(Stack *top)
o Removes and frees the stack from the top.
o Returns the updated top pointer.
• Queue *initQueue(void)
o Malloc Queue struct and initializes front and rear pointers with NULL.
o Returns allocated Queue struct.
• void enqueue(Queue *q, void *item)
o Enqueues an item to the rear of queue.
• Queue *dequeue(Queue *q)
o Removes and frees the QueueNode struct from the front of queue.
o Returns the updated Queue pointer.
Implement the main function as following:
• Create an array of 5 Students structs where 1 ≤ age ≤ 65, using rand function, and 0 ≤ Student ID (EID) ≤ 4.
• Create a stack of 5-student items and print out students’ ages at each step.
• Remove all stacks of students one-by-one from your stack, using pop function, and print out students’ ages at each step.
• Create a queue of 5-student items and print out students’ ages at each step.
• Remove all students one-by-one from your queue, using the dequeue function, and print out students’ ages at each step.
1
Section A
Every user-defined function must have a comment describing:
• What function does;
• What parameter values are;
• What value it returns.
Example from the terminal window:
$ ./a.out
Stack is 25
Stack is 19 25
Stack is 59 19 25
Stack is 44 59 19 25
Stack is 52 44 59 19 25
Stack is 44 59 19 25
Stack is 59 19 25
Stack is 19 25
Stack is 25
The stack is empty, nothing to be printed.
Queue is 25
Queue is 25 19
Queue is 25 19 59
Queue is 25 19 59 44
Queue is 25 19 59 44 52
Queue is 19 59 44 52
Queue is 59 44 52
Queue is 44 52
Queue is 52
The queue is empty, nothing to be printed.
Grading Criteria:
•
Main program:
3 points
•
push function:
6 points
•
pop function:
7 points
•
initQueue function:
1 point
•
enqueue function:
6 points
•
dequeue function:
7 points
Note:
• If your code does not compile with –Wall and –Werror, you will receive a zero for this assignment.
• You need to finish at least three peer reviews within three days of this lab. Otherwise, you will get a 20% penalty.
• You will lose points if you don’t have enough comments.
2
