Week 4
Double-ended Queue (Dequeue) Implementation using Array
#include <stdio.h>
#include <string.h>
#define MAX_SIZE 5
typedef struct {
int arr[MAX_SIZE];
int front;
int rear;
int count;
} Dequeue;
void initialize(Dequeue *dq) {
dq->front = -1;
dq->rear = -1;
dq->count = 0;
}
int isfull(Dequeue *dq) {
return dq->count == MAX_SIZE;
}
int isempty(Dequeue *dq) {
return dq->count == 0;
}
void insertfront(Dequeue *dq, int value) {
if (isfull(dq)) {
printf("Dequeue is full\n");
return;
}
if (isempty(dq)) {
dq->front = 0;
dq->rear = 0;
} else {
dq->front = (dq->front - 1 + MAX_SIZE) % MAX_SIZE;
}
dq->arr[dq->front] = value;
dq->count++;
printf("Inserted at front: %d\n", value);
}
void insertend(Dequeue *dq, int value) {
if (isfull(dq)) {
printf("Dequeue is full\n");
return;
}
if (isempty(dq)) {
dq->front = 0;
dq->rear = 0;
} else {
dq->rear = (dq->rear + 1) % MAX_SIZE;
}
dq->arr[dq->rear] = value;
dq->count++;
printf("Inserted at end: %d\n", value);
}
void deletefront(Dequeue *dq) {
if (isempty(dq)) {
printf("Dequeue is empty\n");
return;
}
printf("Deleted from front: %d\n", dq->arr[dq->front]);
if (dq->front == dq->rear) {
dq->front = -1;
dq->rear = -1;
} else {
dq->front = (dq->front + 1) % MAX_SIZE;
}
dq->count--;
}
void deleteend(Dequeue *dq) {
if (isempty(dq)) {
printf("Dequeue is empty\n");
return;
}
printf("Deleted from end: %d\n", dq->arr[dq->rear]);
if (dq->front == dq->rear) {
dq->front = -1;
dq->rear = -1;
} else {
dq->rear = (dq->rear - 1 + MAX_SIZE) % MAX_SIZE;
}
dq->count--;
}
void displayfromfront(Dequeue *dq) {
if (isempty(dq)) {
printf("Dequeue is empty\n");
return;
}
int i, index;
for (i = 0; i < dq->count; i++) {
index = (dq->front + i) % MAX_SIZE;
printf("%d", dq->arr[index]);
if (i < dq->count - 1) printf(" ");
}
printf("\n");
}
void frontelement(Dequeue *dq) {
if (isempty(dq)) {
printf("Dequeue is empty\n");
return;
}
printf("%d\n", dq->arr[dq->front]);
}
void endelement(Dequeue *dq) {
if (isempty(dq)) {
printf("Dequeue is empty\n");
return;
}
printf("%d\n", dq->arr[dq->rear]);
}
void elementcount(Dequeue *dq) {
printf("%d\n", dq->count);
}
int main() {
Dequeue dq;
initialize(&dq);
char operation[20];
int n, value;
scanf("%d", &n);
while (n--) {
scanf("%s", operation);
if (strcmp(operation, "insertfront") == 0) {
scanf("%d", &value);
insertfront(&dq, value);
} else if (strcmp(operation, "insertend") == 0) {
scanf("%d", &value);
insertend(&dq, value);
} else if (strcmp(operation, "deletefront") == 0) {
deletefront(&dq);
} else if (strcmp(operation, "deleteend") == 0) {
deleteend(&dq);
} else if (strcmp(operation, "displayfromfront") == 0) {
displayfromfront(&dq);
} else if (strcmp(operation, "isempty") == 0) {
printf("%s\n", isempty(&dq) ? "true" : "false");
} else if (strcmp(operation, "isfull") == 0) {
printf("%s\n", isfull(&dq) ? "true" : "false");
} else if (strcmp(operation, "frontelement") == 0) {
frontelement(&dq);
} else if (strcmp(operation, "endelement") == 0) {
endelement(&dq);
} else if (strcmp(operation, "elementcount") == 0) {
elementcount(&dq);
}
}
return 0;
}
Palindrome Check Using Deque
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define MAX_SIZE 1001
// Structure for deque node
typedef struct Node {
char data;
struct Node* prev;
struct Node* next;
} Node;
// Structure for deque
typedef struct {
Node* front;
Node* rear;
} Deque;
// Initialize deque
void initDeque(Deque* dq) {
dq->front = dq->rear = NULL;
}
// Create new node
Node* createNode(char data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->prev = newNode->next = NULL;
return newNode;
}
// Insert at rear
void insertRear(Deque* dq, char data) {
Node* newNode = createNode(data);
if (dq->rear == NULL) {
dq->front = dq->rear = newNode;
return;
}
dq->rear->next = newNode;
newNode->prev = dq->rear;
dq->rear = newNode;
}
// Get and remove front element
char removeFront(Deque* dq) {
if (dq->front == NULL) return '\0';
Node* temp = dq->front;
char data = temp->data;
dq->front = dq->front->next;
if (dq->front == NULL) {
dq->rear = NULL;
} else {
dq->front->prev = NULL;
}
free(temp);
return data;
}
// Get and remove rear element
char removeRear(Deque* dq) {
if (dq->rear == NULL) return '\0';
Node* temp = dq->rear;
char data = temp->data;
dq->rear = dq->rear->prev;
if (dq->rear == NULL) {
dq->front = NULL;
} else {
dq->rear->next = NULL;
}
free(temp);
return data;
}
// Free deque memory
void freeDeque(Deque* dq) {
while (dq->front != NULL) {
Node* temp = dq->front;
dq->front = dq->front->next;
free(temp);
}
dq->rear = NULL;
}
// Check if character is valid for palindrome
int isValidChar(char c) {
return isalnum(c);
}
// Check if string is palindrome using deque
int isPalindrome(char* str) {
Deque dq;
initDeque(&dq);
// Insert valid characters into deque
for (int i = 0; str[i]; i++) {
if (isValidChar(str[i])) {
insertRear(&dq, tolower(str[i]));
}
}
// Compare characters from both ends
while ([Link] != NULL && [Link] != [Link]) {
char front = removeFront(&dq);
char rear = removeRear(&dq);
if (front != rear) {
freeDeque(&dq);
return 0;
}
}
freeDeque(&dq);
return 1;
}
int main() {
char str[MAX_SIZE];
fgets(str, MAX_SIZE, stdin);
// Remove trailing newline if present
int len = strlen(str);
if (len > 0 && str[len-1] == '\n') {
str[len-1] = '\0';
}
if (isPalindrome(str)) {
printf("PALINDROME\n");
} else {
printf("NOT PALINDROME\n");
}
return 0;
}
Deque as a Sliding Window
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
void slidingWindowMax(int* arr, int n, int k) {
int deque[n], front = 0, rear = -1;
for (int i = 0; i < n; i++) {
if (front <= rear && deque[front] < i - k + 1) {
front++;
}
while (front <= rear && arr[deque[rear]] <= arr[i]) {
rear--;
}
deque[++rear] = i;
if (i >= k - 1) {
printf("%d ", arr[deque[front]]);
}
}
printf("\n");
}
int main() {
int n, k;
scanf("%d %d", &n, &k);
int arr[n];
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
slidingWindowMax(arr, n, k);
return 0;
}
