VISVESVARAYA TECHNOLOGICAL UNIVERSITY

“JNANA SANGAMA” BELAGAVI-590018, KARNATAKA

A MINI PROJECT REPORT

ON
“OPERATIONS ON DOUBLE-ENDED
QUEUE USINGOPENGL”

     Computer Graphics & Visualization Laboratory with

MiniProject 18CSL67

Submitted By:

KISHAN S (4VV18CS067)
K YASHAWANTH (4VV18CS061)

UNDER THE GUIDANCE OF

Mr. Pavan Kumar S P Mr. Gururaj H L

Asst. Prof Assoc. Prof
Dept of CSE Dept of CSE
VVCE MYSORE VVCE MYSORE

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING

VIDYAVARDHAKA COLLEGE OF ENGINEERING
MYSORE 570002
 Vidyavardhaka College of Engineering
Department of Computer Science and Engineering

CERTIFICATE

This is to certify that the mini-project report entitled “Operations on Double-Ended Queue
using OpenGL” is a bona fide work carried out by K Yashawanth(4VV18CS061) and
Kishan S(4VV18CS067) students of 6th semester Computer Science and Engineering,
Vidyavardhaka College of Engineering, Mysuru in partial fulfillment for the award of the
degree of Bachelor of Engineering in Computer Science & Engineering of the
Visvesvaraya Technological University, Belagavi, during the academic year 2020-2021. It
is certified that all the suggestions and corrections indicated for the internal assessment have
been incorporated in the report deposited in the department library. The report has been
approved as it satisfies the requirements in respect of mini-project work prescribed for the
said degree.

 Signature of the Guide             Signature of the Guide   Signature of the HOD

  
(Prof. Pavan Kumar S P)             (Prof. Gururaj H L)          (Dr. Ravikumar V)

Name of the Examiners                                                                      Signature with date

1)

2)
 ABSTRACT

Dequeue is sometimes written dequeue, but this use is generally deprecated in technical
literature or technical writing because dequeue is also a verb meaning "to remove from a
queue". Nevertheless, several libraries and some writers, such as Aho, Hopcroft, and
Ullmanin their textbook Data Structures and Algorithms, spell it dequeue. John Mitchell,
author of Concepts in Programming Languages, also uses this terminology.

This differs from the queue abstract data type or first in first out list (FIFO),
where elements can only be added to one end and removed from the other. This general data
class has some possible sub-types: An input-restricted deque is one where deletion can be
made from both ends, but insertion can be made at one end only. An output-restricted deque
is one where insertion can be made at both ends, but deletion can be made from one end only.

Both the basic and most common list types in computing, queues and stacks can be
considered specializations of deques, and can be implemented using deques. The dynamic
array approach uses a variant of a dynamic array that can grow from both ends, sometimes
called array deques. These array deques have all the properties of a dynamic array, such as
constant-time random access, good locality of reference, and inefficient insertion/removal in
the middle, with the addition of amortized constant-time insertion/removal at both ends,
instead of just one end. Three common implementations include:

Allocating deque contents from the center of the underlying array, and resizing the
underlying array when either end is reached. This approach may require more frequent
resizing and waste more space, particularly when elements are only inserted at one end.
  ACKNOWLEDGEMENT

The Mini-project would not have been possible without the guidance,
assistance and suggestions of many individuals. I would like to express our deep sense
of gratitude and indebtedness to each and every one who has helped me to make this
project a success.

We heartily thank our beloved Principal, Dr. B Sadashive Gowda for his
whole hearted support and for his kind permission to undergo the mini-project.

We wish to express our deepest gratitude to Dr. Ravikumar V, Head,

Department of Computer Science and Engineering, VVCE, for his constant
encouragement and inspiration in taking up this mini-project.

We gracefully thank our mini-project guides, Prof. Pavan Kumar S P,

Associate Professor and Prof. Gururaj H L, Assistant Professor, Dept. of Computer
Science and Engineering for their encouragement and advice throughout the course of
the mini-project work.

We also offer our sincere thanks to our family members and friends for their
valuable suggestions and encouragement.

Kishan S (4VV18CS067)                                    K Yashawanth (4VV18CS061)  

 TABLE OF CONTENTS

CHAPTERS Page No.

1. INTRODUCTION 01

1.1 Overview
1.2
Operations On Double-Ended Queue 18CSL67

Chapter 1
INTRODUCTION
1.1 Introduction to Project
In computer science, a double-ended queue (abbreviated to dequeue) is an abstract data type
that generalizes a queue, for which elements can be added to or removed from either the
front (head) or back (tail). It is also often called a head-tail linked list, though properly this
refers to a specific data structure implementation of a de-queue. Our project takes uses input
and the element where ever required by user i.e. backend Or frontend and also lets us delete
from frontend or backend.

1.2 Objective of Project

• Adds an item at the front of Dequeue.
• Adds an item at the rear of Dequeue.
• Deletes an item from front of Dequeue
• Deletes an item from rear of Dequeue.

1.3 Scope of the Project

One example where a dequeue can be used is the A-Steal job scheduling algorithm.
This algorithm implements task scheduling for several processors. A separate dequeue with
threads to be executed is maintained for each processor. To execute the next thread, the
processor gets the first element from the dequeue (using the "remove first element" dequeue
operation). If the current thread forks, it is put back to the front of the dequeue ("insert
element at front") and a new thread is executed. When one of the processors finishes
execution of its own threads (i.e. itsdequeue is empty), it can "steal" a thread from another
processor: it gets the last element from the dequeue of another processor ("remove last
element") and executes it. The steal-job scheduling algorithm is used by Intel's Threading
Building Blocks (TBB) library for parallel programming.
Dept of CSE, VVCE 1
Operations On Double-Ended Queue 18CSL67

Chapter 2
INTODUCTION TO TECHNOLOGY USED
2.1 Visual Studio - 2019

Figure: 2.1- Visual Studio

Microsoft Visual Studio is an integrated development environment from Microsoft. It is used

to develop computer programs, as well as websites, web apps, web services and mobile apps.
Visual Studio uses Microsoft software development platforms such as Windows API,
Windows Forms, Windows Presentation Foundation, Windows Store and Microsoft
Silverlight.
Visual Studio includes a code editor supporting IntelliSense as well as code refactoring. The
integrated debugger works both as a source-level debugger and a machine-level debugger.
Other built-in tools include a code profiler, designer for building GUI applications, web
designer, class designer, and database schema designer. It accepts plug-ins that expand the
functionality at almost every level including adding support for source control systems (like
Subversion and Git) and adding new toolsets like editors and visual designers for domain-
specific languages or toolsets for other aspects of the software development lifecycle (like the
Azure DevOps client: Team Explorer

Dept of CSE, VVCE 2

Operations On Double-Ended Queue 18CSL67

2.2 Back end : GNU Compiler

The GNU Compiler Collection (GCC) is a compiler system produced by the GNU Project
supporting various programming languages. GCC is a key component of the GNU toolchain
and the standard compiler for most Unix-like operating systems. The Free Software
Foundation (FSF) distributes GCC under the GNU General Public License (GNU

GPL). GCC has played an important role in the growth of free software, as both a tool and an
example.

Figure:2.2- Gcc compiler

2.3 OpenGL & Glut

Figure:2.3- OpenGL

Open Graphics Library (OpenGL) is a cross-language, cross-platform application

programming interface (API) for rendering 2D and 3Dvector graphics. The API is typically
used to interact with a graphics processing unit (GPU), to achieve hardware-accelerated
rendering. Silicon Graphics Inc., (SGI) started developing OpenGL in 1991 and released it in
January 1992; applications use it extensively in the fields of computer-aided design (CAD),
virtual reality, scientific visualization,

Dept of CSE, VVCE 3

Operations On Double-Ended Queue 18CSL67

information visualization, flight simulation, and video games. Since 2006 OpenGL has been
managed by the non-profit technology consortium Khronos Group.

The OpenGL Utility Toolkit (GLUT) is a library of utilities for OpenGL programs, which
primarily perform system-level I/O with the host operating system. Functions performed
include window definition, window control, and monitoring of keyboard and mouse input.
Routines for drawing a number of geometric primitives (both in solid and wireframe mode)
are also provided, including cubes, spheres and the Utah teapot. GLUT also has some limited
support for creating pop-up menus.

Dept of CSE, VVCE 4

Operations On Double-Ended Queue 18CSL67

Chapter 3
REQUIREMENT SPECIFICATION
3.1 Software Requirement
• OS : Windows 7 or above
Mac High Sierra or above
Linux
• Front end : Visual Studio - 2019
• Back end : gcc complier
• Coding language : c++

3.2 Hardware Requirement

• Processor : Intel i5 1.5GHz or above.
• Ram : 8GB DDR3 or above.
• Memory : 128GB SSD or above.
• Monitor : LED-backlit glossy widescreen display.

Dept of CSE, VVCE 5

Operations On Double-Ended Queue 18CSL67

Chapter 4
FUNCTIONS USED

4.1 Inbuilt Functions

• main(intargc,char **argv){} - main function of the project.
• glutMainLoop(); - Enters GLUT event processing loop.
• strcpy(); - Copies string from one variable to another.
• glPushMatrix(); - glPushMatrix pushes the current matrix stack down
by one, duplicating the current matrix.
• glVertex2f(); - Draw a line between two points & many more

4.2 User defined Functions

• myinit() - Initialize the values requried.
• square() - Draws a square where we can place element.
• drawOutline() - Draws a outline to a square.
• drawString() - Draws string and other information to the output
screen.
• drawArrow() - Draws arrow where ever requried.
• backEnqueue() - Adds element at the back end of the queue.
• frontEnqueue() - Adds element at front end of the queue & many more
Dept of CSE, VVCE 6
Operations On Double-Ended Queue 18CSL67

Chapter 5
ALGORITHM

5.1 Algorithm for Insertion at rear end

Step -1: [Check for overflow]

if(rear==MAX)
Print("Queue is Overflow”);
return;
Step-2: [Insert element]
else
rear=rear+1;
q[rear]=no;
[Set rear and front pointer]
if rear=0
rear=1;
if front=0
front=1;
Step-3: return

5.2 Implementation of Insertion at rear end

voidadd_item_rear()
{
intnum;
printf("\n Enter Item to insert : ");
scanf("%d",&num);

if(rear==MAX)
{
printf("\n Queue is Overflow");
return;
}

Dept of CSE, VVCE 7

Operations On Double-Ended Queue 18CSL67

Else
{
rear++;
q[rear]=num;
if(rear==0)
rear=1;
if(front==0)
front=1;
}
}

5.3 Algorithm for Insertion at font end

Step-1 : [Check for the front position]

if(front<=1)
Print (“Cannot add item at front end”);
return;
Step-2 : [Insert at front]
else
front=front-1;
q[front]=no;
Step-3 : Return

5.4 Implementation of Insertion at font end

voidadd_item_front()
{
intnum;
printf("\n Enter item to insert:");
scanf("%d",&num);
if(front<=1){

Dept of CSE, VVCE 8

Operations On Double-Ended Queue 18CSL67

printf("\n Cannot add item at front end");

return;
} else {
front—;
q[front]=num;
}
}

5.5 Algorithm for Deletion from front end

Step-1 [ Check for front pointer]

if front=0
print(" Queue is Underflow”);
return;
Step-2 [Perform deletion]
else
no=q[front];
print(“Deleted element is”,no);
[Set front and rear pointer]
if front=rear
front=0;
rear=0;
else
front=front+1;
Step-3 : Return

Dept of CSE,VVCE 9
Operations On Double-Ended Queue 18CSL67

5.6 Implementation of Deletion at font end

Void delete_item_front(){
intnum;
if(front==0)
{
printf("\n Queue is Underflow\n");
return;
}
else{
num=q[front];
printf("\n Deleted item is %d\n",num);
if(front==rear)
{
front=0;
rear=0;
}
else{
front++;
}
}
}

5.7 Algorithm for Deletion from rear end

Step-1 : [Check for the rear pointer]

if rear=0
print(“Cannot delete value at rear end”);
return;
Step-2: [ perform deletion]
else
no=q[rear];

Dept of CSE,VVCE 10
Operations On Double-Ended Queue 18CSL67

if(front = rear)
front=0;
rear=0;
else
rear=rear-1;
print(“Deleted element is”,no);
Step-3 : Return

5.8 Implementation of Deletion from rear end

voiddelete_item_rear()
{
intnum;
if(rear==0)
{
printf("\n Cannot delete item at rear end\n");
return;
}
else{
num=q[rear];
if(front==rear){
front=0;
rear=0;
} else {
rear--;
printf("\n Deleted item is %d\n",num);
}
}
}

Dept of CSE,VVCE 11
Operations On Double-Ended Queue 18CSL67

Chapter 6
SOURCE CODE
6.1 main.cpp
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <GLUT/glut.h>
#include <ctype.h>
#include <time.h>
#include "myheader.h"

//1st function
/ initialize the values requried
voidmyinit() {
/ background

/ glClearColor(BACKGROUND_R, BACKGROUND_G, BACKGROUND_B,

BACKGROUND_A);
/
/ glMatrixMode(GL_MODELVIEW);
/
/ glLoadIdentity();
/
/ glMatrixMode(GL_PROJECTION);
/
/ gluOrtho2D(0.0,SCREEN_X,0.0,SCREEN_Y);
/
/
/

Dept of CSE,VVCE 12
Operations On Double-Ended Queue 18CSL67

/ creates color of cube and outline color

int i;
for(i = 0; i < 15; i++) {
queue[i].r = 0;
queue[i].g = 0.25;
queue[i].b = 0.75;
queue[i].rl = 1;
}

float step = DIST/MAX;

queue[0].x1 = OFFSET_X;
queue[0].x2 = queue[0].x1+step;

for(i = 1; i <= 15; i++) {

queue[i].x1 = queue[i-1].x1+step;
queue[i].x2 = queue[i].x1+step;
}

//2nd function
//function to draw a square
void square(int x1, int y1, int x2, int y2) {
glBegin(GL_POLYGON);
glVertex2f(x1, y1);
glVertex2f(x1, y2);
glVertex2f(x2, y2);
glVertex2f(x2, y1);
glEnd();
}

Dept of CSE,VVCE 13
Operations On Double-Ended Queue 18CSL67

//3rd function
//function to draw the outline the square
voiddrawOutline(int x1, int y1, int x2, int y2) {
int temp;
if(x1 < x2) {
temp = x1;
x1 = x2;
x2 = temp;
}
if(y1 < y2) {
temp = y1;
y1 = y2;
y2 = temp;
}
glBegin(GL_LINES);
glVertex2f(x1, y1);
glVertex2f(x1, y2);
glVertex2f(x2, y2);
glVertex2f(x2, y1);

glEnd();
}
//4th function
//function to draw a string to the output screen
voiddrawString(const char *str, double x=0, double y=0, double size=5.0)
{ glPushMatrix();
glTranslatef(x,y,0);
glScalef(size,size,4.0);
glColor3f(1, 0, 0);

Dept of CSE, VVCE 14

Operations On Double-Ended Queue 18CSL67

intitemCt = 0;
intlen = strlen(str);
}
glPopMatrix();
}
//13th function
//main funtion where all the action takes place
int main(intargc,char **argv) {
char number[1000];
int i, j, len;
char c;
strcpy(enter_str, "Enter Element to Queue: ");
start_of_num = strlen("Enter Element to Queue:
"); jump:
printf("\n\n\n");
printf("------------------------------------\n");
printf("Simulation of dequeueue in OpenGL\n");
printf("------------------------------------\n\n");
printf("Enter the number of elements in the dequeueue\n(Not greater than 15
and not lesser than 3):\n");
scanf("%d", &MAX);

while(MAX > 15 || MAX < 3) {

printf("ERROR: Invalid value! \nEnter again:
"); scanf("%d", &MAX);
}
printf("\n\nVALUE ACCEPTED! Program Running...\n");

glutInit(&argc,argv);

Dept of CSE, VVCE 15

Operations On Double-Ended Queue 18CSL67

glutInitDisplayMode(GLUT_SINGLE|GLUT_RGB);
glutInitWindowSize(SCREEN_X,SCREEN_Y);
glutInitWindowPosition(10,10);
glutKeyboardFunc(mykey);
myinit();
glutMainLoop();
return 0;
}
6.2 myHeader.h
#ifndef QUEUE_SIMULA_H
#define QUEUE_SIMULA_H
#define SCREEN_X 1000
#define BACKGROUND_R 1.0
#define BACKGROUND_G 1.0
#define BACKGROUND_B 1.0
#define BACKGROUND_A 1.0
#define SCREEN_Y 500
#define OFFSET_X 50
#define differenc 180.000000
#define fnot 20
#define ARROW_LENGTH 50
#define ENQUEUE 19
#define DEQUEUEUE1 38
#define DEQUEUEUE2 39
#define NO_OP 45
#define OPERATION_POSITION_X SCREEN_X/4+SCREEN_X/20
#define OPERATION_POSITION_Y SCREEN_Y/5

#define ENTER_POSITION_Y SCREEN_Y-60

#define ENTER_POSITION_X OFFSET_X
#define EMPTY 0
#define FULL 1
staticint MAX; // MAXIMUM NUMBER OF ELEMENTS IN

Dept of CSE, VVCE 16

Operations On Double-Ended Queue 18CSL67

THE QUEUE. TAKEN AS INPUT

int DIST = SCREEN_X - 2*OFFSET_X;
int f = 0; // FRONT OF QUEUE

int b = 0; // REAR OF QUEUE

int YD = SCREEN_Y/10; // just a random height. HEIGHT OF EACH
ELEMENT (BOX) IN THE QUEUE
double FONT_ADJUST = 9; // DENOMINATOR OF FONT_RATIO. LARGER
THE VALUE, LARGER THE FONT
double FONT_RATIO = YD/FONT_ADJUST; // SETS THE SIZE OF THE FONT
intenqORdq = NO_OP; // indicates what the last operation was.
/ end of all Constants
intclr = 0; intisback =
1;
char enter_str[10000]; char
blinking[2] = {'_', 0}; char
displayString[10003]; char
displayString1[10003]; int
start_of_num;
intcnt_of_chars = 0;
int message = EMPTY;
/ Each element of the queue is encapsulated into a structure.
structelem {
float r, g, b; // filling colors

floatrl, gl, bl; // for outlines

float x1, x2; // start and end x positions
charnum[11];
};
structelem queue[16]; // elements of the queue
#endif

Dept of CSE, VVCE 17

Operations On Double-Ended Queue 18CSL67

Chapter 7
SCREENSHOTS

Figure: 7.1- User input screen

Figure: 7.2- Output screen

Dept of CSE, VVCE 18

Operations On Double-Ended Queue 18CSL67

Figure:- 7.3- Queue full condition

Figure: 7.4- dequeueue from front

Dept of CSE, VVCE 19

Operations On Double-Ended Queue 18CSL67

CONCLUSION

The project is well suited for 2d and 3d objects as well as for carrying out basic
graphical functionality. However if implemented on large scale insufficient resources
as the potential to become a standard stand alone. GUI based application for
Macintosh operating system. Out of many features available the project demonstrates
some popular and commonly used features of openGL such as scalene, reshaping,
etc. these graphical function will also work in tandem with various rules involved in
Double-Ended Queue. Since this project works on dynamic values it can be used for
real time computation. OpenGL complexity and the project demonstration the scope
of OpenGL platform as a premiere developing launch pad. Hence it has indeed been
usefull in developing many algorithms. It serves as important stepping stone for
venturing into other fields of computer graphic design and application.

In future version of Operations On Double-Ended Queue project, addition of some

more inbuilt function 2d and 3d models of varioys options to set properties according
to usersrequiremnt is a feasible idea making a user interface of this program simpler
and more user friendly will certainly help beginners in using this program more
easily. The added functionality of giving information about an object on keyboard or
mouse clicks.perhaps the most challenging task will be to implement the
functionality of layers which are used extensively by proffessional’s in graphics
industry.
Dept of CSE, VVCE 20
Operations On Double-Ended Queue 18CSL67

BIBLIOGRAPHY
Text Book :

 Donald Hearn & Pauline Baker: Computer Graphics-OpenGL Version

3rd Edition, Pearson Education ,2011

 Edward Angel :Interactive Computer graphics – A Top Down approach

with OpenGL , 5th edition. Pearson Education, 2011.
Web Links :
www.google.com
https://en.wikipedia.org/wiki/Double-ended_queue/

https://www.geeksforgeeks.org/dequeue-set-1-introduction-applications/

http://scanftree.com/Data_Structure/duble-ended-queue-dequeue/

Dept of CSE, VVCE 21