Description: In this assignment you are to implement a simple queue data type. Y
ID: 3900435 • Letter: D
Question
Description:
In this assignment you are to implement a simple queue data type. You have
been given a starting programming template. You task is to dene a queue
data type, and implement the enqueue(), dequeue() and displayQueue()
functions.
For this assignment I ask that you do NOT use the C++ Standard Tem-
plate Library (STL) to implement your queue logic. You should write a small
queue implementation by hand. As a suggestion, you can use a linked list, or
simply use a regular C array of integers (for example create a circular buer
implementation). I will never test your implementation of the queue with
more than 50 items, so if you need to declare a static array to implement
your queue, you can hard code it to hold 50 items maximum.
The input le will simply be a list of operations to perform on a queue.
For example:
----- testfile.tst --------
enqueue 5
enqueue 7
dequeue
enqueue 3
enqueue 8
enqueue 9
dequeue
dequeue
dequeue
dequeue
dequeue
---------------------------
Example correct output for this set of enqueue/dequeue operations will
look like the following:
Processing queue test file: testfile.tst
Enqueuing item: 5
Head: 5 :Tail
Enqueuing item: 7
Head: 5 7 :Tail
Dequeued item: 5
Head: 7 :Tail
Enqueuing item: 3
Head: 7 3 :Tail
Enqueuing item: 8
Head: 7 3 8 :Tail
Enqueuing item: 9
Head: 7 3 8 9 :Tail
Dequeued item: 7
Head: 3 8 9 :Tail
Dequeued item: 3
Head: 8 9 :Tail
Dequeued item: 8
Head: 9 :Tail
Dequeued item: 9
Head: :Tail
Error: dequeue from empty queue
Assignment Submission and Requirements
All source les you create for you solution (.c or .cpp/.c++ and .h header
les) should be uploaded to the eCollege dropbox created for this assignment
by the deadline. You should not attach any les besides the source les
containing your C/C++ code. But you should make sure you attach all
needed les you create to your submission, so that I can compile and run
your solution.
You are required to write the program in standard C/C++ programming
language. You should use a relatively recent version of the C/C++ compiler
(C90 C++98 is ne, or the more recent C99 C++11 will also be acceptable),
and/or recent IDE that has an up to date compiler. You should only use
standard C/C++ libraries, do not use Microsoft specic or other third-party
developed external libraries. This page http://en.cppreference.com/w/
provides a good up to date reference of the libraries in the standard C++ and
C languages. You may use the C++ standard template library containers
(like the list and queue items) to implement the ready queue you need. We
will go over a simple implementation of a queue using pointers and/or arrays
in class, if you would like an example implementation in plain C that might
be simpler to use than learning the STL.
Explanation / Answer
Hello!
Here goes the following code :
#include <stdio.h>
#include <stdlib.h>
struct node {
int info;
struct node *ptr;
}*front,*rear,*temp,*front1;
void create() {
front = rear = NULL;
}
void displayQueue() {
printf("Head: ");
front1 = front;
while (front1 != rear) {
printf("%d ", front1->info);
front1 = front1->ptr;
}
if (front1 == rear && rear != NULL)
printf("%d", front1->info);
printf(" :Tail ");
}
void enqueue(int data) {
printf("Enqueuing item: %d ", data);
if (rear == NULL) {
rear = (struct node *)malloc(1*sizeof(struct node));
rear->ptr = NULL;
rear->info = data;
front = rear;
} else {
temp=(struct node *)malloc(1*sizeof(struct node));
rear->ptr = temp;
temp->info = data;
temp->ptr = NULL;
rear = temp;
}
displayQueue();
}
void dequeue() {
front1 = front;
if (front1 == NULL) {
printf("Error: dequeue from empty queue ");
return;
}
else if (front1->ptr != NULL) {
front1 = front1->ptr;
printf("Dequeued item: %d ", front->info);
free(front);
front = front1;
} else {
printf("Dequeued item: %d ", front->info);
free(front);
front = NULL;
rear = NULL;
}
displayQueue();
}
int frontelement() {
if ((front != NULL) && (rear != NULL))
return(front->info);
else
return 0;
}
void empty() {
if ((front == NULL) && (rear == NULL))
printf("Queue empty");
else
printf("Queue not empty");
}
int main() {
create();
enqueue(5);
enqueue(7);
dequeue();
enqueue(3);
enqueue(8);
enqueue(9);
dequeue();
dequeue();
dequeue();
dequeue();
dequeue();
}
Test case :
Enqueuing item: 5
Head: 5 :Tail
Enqueuing item: 7
Head: 5 7 :Tail
Dequeued item: 5
Head: 7 :Tail
Enqueuing item: 3
Head: 7 3 :Tail
Enqueuing item: 8
Head: 7 3 8 :Tail
Enqueuing item: 9
Head: 7 3 8 9 :Tail
Dequeued item: 7
Head: 3 8 9 :Tail
Dequeued item: 3
Head: 8 9 :Tail
Dequeued item: 8
Head: 9 :Tail
Dequeued item: 9
Head: :Tail
Error: dequeue from empty queue
Program ended with exit code: 0