-
Notifications
You must be signed in to change notification settings - Fork 1
/
Queue_CircularArrayImplementation.rtf
126 lines (125 loc) · 4.1 KB
/
Queue_CircularArrayImplementation.rtf
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
{\rtf1\ansi\ansicpg1252\cocoartf1265\cocoasubrtf210
{\fonttbl\f0\fnil\fcharset0 Consolas;}
{\colortbl;\red255\green255\blue255;\red132\green134\blue132;\red255\green255\blue255;\red38\green38\blue38;
\red148\green6\blue75;\red213\green58\blue6;\red101\green71\blue146;\red14\green114\blue164;}
\paperw11900\paperh16840\margl1440\margr1440\vieww10800\viewh8400\viewkind0
\deftab720
\pard\pardeftab720\sl320
\f0\fs24 \cf2 \cb3 //{\field{\*\fldinst{HYPERLINK "https://gist.github.com/mycodeschool/7331785"}}{\fldrslt https://gist.github.com/mycodeschool/7331785}}\
/* Queue - Circular Array implementation in C++*/\cf4 \
#\cf5 include\cf6 <iostream>\cf4 \
\pard\pardeftab720\sl320
\cf5 using\cf4 \cf5 namespace\cf4 \cf7 std\cf5 ;\cf4 \
#\cf5 define\cf4 \cf7 MAX_SIZE\cf4 \cf8 101\cf4 \cf2 //maximum size of the array that will store Queue. \cf4 \
\'a0\
\pard\pardeftab720\sl320
\cf2 // Creating a class named Queue.\cf4 \
\pard\pardeftab720\sl320
\cf5 class\cf4 \cf7 Queue\cf4 \
\{\
\cf5 private:\cf4 \
\cf5 int\cf4 A[MAX_SIZE];\
\cf5 int\cf4 front, rear; \
\cf5 public:\cf4 \
\cf2 // Constructor - set front and rear as -1. \cf4 \
\cf2 // We are assuming that for an empty Queue, both front and rear will be -1.\cf4 \
\cf7 Queue\cf4 ()\
\{\
front = -\cf8 1\cf4 ; \
rear = -\cf8 1\cf4 ;\
\}\
\'a0\
\cf2 // To check wheter Queue is empty or not\cf4 \
\cf5 bool\cf4 \cf7 IsEmpty\cf4 ()\
\{\
\cf5 return\cf4 (front == -\cf8 1\cf4 && rear == -\cf8 1\cf4 ); \
\}\
\'a0\
\cf2 // To check whether Queue is full or not\cf4 \
\cf5 bool\cf4 \cf7 IsFull\cf4 ()\
\{\
\cf5 return\cf4 (rear+\cf8 1\cf4 )%MAX_SIZE == front ? \cf8 true\cf4 : \cf8 false\cf4 ;\
\}\
\'a0\
\cf2 // Inserts an element in queue at rear end\cf4 \
\cf5 void\cf4 \cf7 Enqueue\cf4 (\cf5 int\cf4 x)\
\{\
cout<<\cf6 "Enqueuing "\cf4 <<x<<\cf6 " \\n"\cf4 ;\
\cf5 if\cf4 (\cf8 IsFull\cf4 ())\
\{\
cout<<\cf6 "Error: Queue is Full\\n"\cf4 ;\
\cf5 return\cf4 ;\
\}\
\cf5 if\cf4 (\cf8 IsEmpty\cf4 ())\
\{ \
front = rear = \cf8 0\cf4 ; \
\}\
\cf5 else\cf4 \
\{\
rear = (rear+\cf8 1\cf4 )%MAX_SIZE;\
\}\
A[rear] = x;\
\}\
\'a0\
\cf2 // Removes an element in Queue from front end. \cf4 \
\cf5 void\cf4 \cf7 Dequeue\cf4 ()\
\{\
cout<<\cf6 "Dequeuing \\n"\cf4 ;\
\cf5 if\cf4 (\cf8 IsEmpty\cf4 ())\
\{\
cout<<\cf6 "Error: Queue is Empty\\n"\cf4 ;\
\cf5 return\cf4 ;\
\}\
\cf5 else\cf4 \cf5 if\cf4 (front == rear ) \
\{\
rear = front = -\cf8 1\cf4 ;\
\}\
\cf5 else\cf4 \
\{\
front = (front+\cf8 1\cf4 )%MAX_SIZE;\
\}\
\}\
\cf2 // Returns element at front of queue. \cf4 \
\cf5 int\cf4 \cf7 Front\cf4 ()\
\{\
\cf5 if\cf4 (front == -\cf8 1\cf4 )\
\{\
cout<<\cf6 "Error: cannot return front from empty queue\\n"\cf4 ;\
\cf5 return\cf4 -\cf8 1\cf4 ; \
\}\
\cf5 return\cf4 A[front];\
\}\
\cf2 /* \cf4 \
\pard\pardeftab720\sl320
\cf2 Printing the elements in queue from front to rear. \cf4 \
\cf2 This function is only to test the code. \cf4 \
\cf2 This is not a standard function for Queue implementation. \cf4 \
\cf2 */\cf4 \
\cf5 void\cf4 \cf7 Print\cf4 ()\
\{\
\cf2 // Finding number of elements in queue \cf4 \
\cf5 int\cf4 count = (rear+MAX_SIZE-front)%MAX_SIZE + \cf8 1\cf4 ;\
cout<<\cf6 "Queue : "\cf4 ;\
\cf5 for\cf4 (\cf5 int\cf4 i = \cf8 0\cf4 ; i <count; i++)\
\{\
\cf5 int\cf4 \cf8 index\cf4 = (front+i) % MAX_SIZE; \cf2 // Index of element while travesing circularly from front\cf4 \
cout<<A[\cf8 index\cf4 ]<<\cf6 " "\cf4 ;\
\}\
cout<<\cf6 "\\n\\n"\cf4 ;\
\}\
\};\
\pard\pardeftab720\sl320
\cf5 int\cf4 \cf7 main\cf4 ()\
\{\
\cf2 /*Driver Code to test the implementation\cf4 \
\pard\pardeftab720\sl320
\cf2 Printing the elements in Queue after each Enqueue or Dequeue \cf4 \
\cf2 */\cf4 \
Queue Q; \cf2 // creating an instance of Queue. \cf4 \
Q.\cf8 Enqueue\cf4 (\cf8 2\cf4 ); Q.\cf8 Print\cf4 (); \
Q.\cf8 Enqueue\cf4 (\cf8 4\cf4 ); Q.\cf8 Print\cf4 (); \
Q.\cf8 Enqueue\cf4 (\cf8 6\cf4 ); Q.\cf8 Print\cf4 ();\
Q.\cf8 Dequeue\cf4 (); Q.\cf8 Print\cf4 ();\
Q.\cf8 Enqueue\cf4 (\cf8 8\cf4 ); Q.\cf8 Print\cf4 ();\
\}\
}