Repository navigation
Expand file tree
/
Copy pathdeque.h
More file actions
137 lines (121 loc) · 3.55 KB
/
Copy pathdeque.h
File metadata and controls
137 lines (121 loc) · 3.55 KB
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
127
128
129
130
131
132
133
134
135
136
137
#ifndef DEQUE_JL
#define DEQUE_JL
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
#define DEQUE_MAX_SIZE 100 // The maximum number of elements that we can store in the deque.
// Define how our (linear and dynamic) double-ended queue is structured. It's a circular array, like the Queue.
typedef struct{
int data[DEQUE_MAX_SIZE]; // The internal array to store our deque elements.
int front; // The index value of the front element.
int size; // The current number of elements in our deque.
} Deque;
/********************/
/* FUNCTIONS */
/********************/
// Set Up the Deque. We start setting size to 0 and front to 0.
void initDeque(Deque *deque){
deque->front = 0;
deque->size = 0;
}
// Check if the Deque is Empty. Returns 1 if it's empty or 0 if it has elements.
int isEmptyDeque(Deque *deque){
if(deque->size == 0){
return 1;
}
else{
return 0;
}
}
// Check if the Deque is Full. Returns 1 if it's full or 0 if it's not full.
int isFullDeque(Deque *deque){
if(deque->size >= DEQUE_MAX_SIZE){
return 1;
}
else{
return 0;
}
}
// Get the Index of the Rear Element. The deque must not be empty.
int rearIndexDeque(Deque *deque){
return (deque->front + deque->size - 1) % DEQUE_MAX_SIZE;
}
// Add an Element to the Front of the Deque. Returns 1 if successful or 0 if the deque is full.
int pushFrontDeque(Deque *deque, int value){
if(isFullDeque(deque)){
return 0;
}
else{
deque->front = (deque->front - 1 + DEQUE_MAX_SIZE) % DEQUE_MAX_SIZE;
deque->data[deque->front] = value;
deque->size++;
return 1;
}
}
// Add an Element to the Rear of the Deque. Returns 1 if successful or 0 if the deque is full.
int pushBackDeque(Deque *deque, int value){
if(isFullDeque(deque)){
return 0;
}
else{
deque->size++;
deque->data[rearIndexDeque(deque)] = value;
return 1;
}
}
// Remove an Element from the Front of the Deque. Returns 1 if successful or 0 if the deque is empty.
int popFrontDeque(Deque *deque, int *value){
if(isEmptyDeque(deque)){
return 0;
}
else{
*value = deque->data[deque->front];
deque->front = (deque->front + 1) % DEQUE_MAX_SIZE;
deque->size--;
return 1;
}
}
// Remove an Element from the Rear of the Deque. Returns 1 if successful or 0 if the deque is empty.
int popBackDeque(Deque *deque, int *value){
if(isEmptyDeque(deque)){
return 0;
}
else{
*value = deque->data[rearIndexDeque(deque)];
deque->size--;
return 1;
}
}
// Peek at the Front Element without Removing It. Returns 1 if successful or 0 if the deque is empty.
int peekFrontDeque(Deque *deque, int *value){
if(isEmptyDeque(deque)){
return 0;
}
else{
*value = deque->data[deque->front];
return 1;
}
}
// Peek at the Rear Element without Removing It. Returns 1 if successful or 0 if the deque is empty.
int peekBackDeque(Deque *deque, int *value){
if(isEmptyDeque(deque)){
return 0;
}
else{
*value = deque->data[rearIndexDeque(deque)];
return 1;
}
}
// Print all Elements of the Deque. Displays elements from front to rear.
void printDeque(Deque *deque){
printf("[");
for(int i = 0; i < deque->size; i++){
printf("%d", deque->data[(deque->front + i) % DEQUE_MAX_SIZE]);
if(i < deque->size-1){
printf(", ");
}
}
printf("]\n");
}
#endif //DEQUE_JL