-
Notifications
You must be signed in to change notification settings - Fork 1
/
CircularQueue_LinkedList.cs
95 lines (80 loc) · 2.1 KB
/
CircularQueue_LinkedList.cs
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
namespace CSharp.DS.Queue
{
/// <summary>
/// Circular Queue implementation using a Linked List
/// </summary>
/// <typeparam name="T"></typeparam>
public class CircularQueue_LinkedList<T>
{
public class ListNode
{
public T Value;
public ListNode Previous, Next;
public ListNode(T val)
{
this.Value = val;
}
}
private readonly int _capacity;
private readonly ListNode _head;
private readonly ListNode _tail;
private int _size;
public CircularQueue_LinkedList(int capacity)
{
_capacity = capacity;
_size = 0;
_head = new ListNode(default); // dummy nodes
_tail = new ListNode(default);
_head.Next = _tail;
_tail.Previous = _head;
}
public bool Enqueue(T value)
{
if (IsFull())
{
return false;
}
var newNode = new ListNode(value);
newNode.Next = _tail;
newNode.Previous = _tail.Previous;
_tail.Previous.Next = newNode;
_tail.Previous = newNode;
_size++;
return true;
}
public bool Dequeue()
{
if (IsEmpty())
{
return false;
}
var deletedNode = _head.Next;
_head.Next = deletedNode.Next;
deletedNode.Next.Previous = _head;
deletedNode.Next = null;
deletedNode.Previous = null;
_size--;
return true;
}
public T Front()
{
if (IsEmpty())
return default;
return _head.Next.Value;
}
public T Rear()
{
if (IsEmpty())
return default;
return _tail.Previous.Value;
}
public bool IsEmpty()
{
return _size == 0;
}
public bool IsFull()
{
return _size == _capacity;
}
}
}