aboutsummaryrefslogtreecommitdiff
path: root/design_circular_queue.c
blob: ad1e353aa1242c7f5e3b1edd416766db198d2180 (plain)
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
// 641. Design Circular Deque
#include "leetcode.h"

/*
 * design your implementation of the circular double ended queue (deque).
 * implement the 'MyCircularDeque' class
 */

struct node {
  struct node *next;
  struct node *prev;
  int val;
};

typedef struct {
  struct node *head;
  struct node *tail;
  int size;
  int max_size;
} MyCircularDeque;

MyCircularDeque *myCircularDequeCreate(int k) {
  MyCircularDeque *dq = (MyCircularDeque *)malloc(sizeof(MyCircularDeque));
  dq->head = (struct node *)malloc(sizeof(struct node));
  dq->tail = (struct node *)malloc(sizeof(struct node));
  dq->head->next = dq->tail;
  dq->head->prev = NULL;
  dq->tail->prev = dq->head;
  dq->tail->next = NULL;
  dq->size = 0;
  dq->max_size = k;
  return dq;
}

bool myCircularDequeInsertFront(MyCircularDeque *obj, int value) {
  if (obj->size == obj->max_size)
    return false;
  struct node *n = (struct node *)malloc(sizeof(struct node));
  n->val = value;
  n->prev = obj->head;
  n->next = obj->head->next;
  obj->head->next->prev = n;
  obj->head->next = n;
  obj->size++;
  return true;
}

bool myCircularDequeInsertLast(MyCircularDeque *obj, int value) {
  if (obj->size == obj->max_size)
    return false;
  struct node *n = (struct node *)malloc(sizeof(struct node));
  n->val = value;
  n->prev = obj->tail->prev;
  n->next = obj->tail;
  obj->tail->prev->next = n;
  obj->tail->prev = n;
  obj->size++;
  return true;
}

bool myCircularDequeDeleteFront(MyCircularDeque *obj) {
  if (!obj->size)
    return false;
  struct node *back = obj->head->next;
  obj->head->next->next->prev = obj->head;
  obj->head->next = obj->head->next->next;
  obj->size--;
  free(back);
  return true;
}

bool myCircularDequeDeleteLast(MyCircularDeque *obj) {
  if (!obj->size)
    return false;
  struct node *back = obj->tail->prev;
  obj->tail->prev->prev->next = obj->tail;
  obj->tail->prev = obj->tail->prev->prev;
  obj->size--;
  free(back);
  return true;
}

int myCircularDequeGetFront(MyCircularDeque *obj) {
  return !obj->size ? -1 : obj->head->next->val;
}

int myCircularDequeGetRear(MyCircularDeque *obj) {
  return !obj->size ? -1 : obj->tail->prev->val;
}

bool myCircularDequeIsEmpty(MyCircularDeque *obj) { return !obj->size; }

bool myCircularDequeIsFull(MyCircularDeque *obj) {
  return obj->size == obj->max_size;
}

void myCircularDequeFree(MyCircularDeque *obj) {
  struct node *curr = obj->head;
  while (curr) {
    struct node *back = curr;
    curr = curr->next;
    free(back);
  }
}

int main() {
  MyCircularDeque *obj = myCircularDequeCreate(3);
  printf("%d\n", myCircularDequeInsertLast(obj, 1));  // expect: 1
  printf("%d\n", myCircularDequeInsertLast(obj, 2));  // expect: 1
  printf("%d\n", myCircularDequeInsertFront(obj, 3)); // expect: 1
  printf("%d\n", myCircularDequeInsertFront(obj, 4)); // expect: 0
  printf("%d\n", myCircularDequeGetRear(obj));        // expect: 2
  printf("%d\n", myCircularDequeIsFull(obj));         // expect: 1
  printf("%d\n", myCircularDequeDeleteLast(obj));     // expect: 1
  printf("%d\n", myCircularDequeInsertFront(obj, 4)); // expect: 1
  printf("%d\n", myCircularDequeGetFront(obj));       // expect: 4
  myCircularDequeFree(obj);
}