array-queue.java/ArrayQueue.java at master · moocf/array-queue.java · GitHub

History

73 lines (66 loc) · 1.67 KB

Raw

import java.nio.*;

import java.util.concurrent.locks.*;

// Array queue is a bounded lock-based FIFO queue using

// an array. It uses 2 separate locks for head and tail.

class ArrayQueue<T> {

Lock headLock;

Lock tailLock;

T[] data;

int head;

int tail;

// headLock: lock for enq() at head

// tailLock: lock for deq() at tail

// data: array of values in stack

// head: front of queue (0)

// tail: rear of queue (0)

@SuppressWarnings("unchecked")

public ArrayQueue(int capacity) {

headLock = new ReentrantLock();

tailLock = new ReentrantLock();

data = (T[]) new Object[capacity+1];

head = 0;

tail = 0;

}

// 1. Lock tail.

// 2. Try enq.

// 3. Unlock tail.

public void enq(T x) {

try {

tailLock.lock(); // 1

tryEnq(x); // 2

} finally {

tailLock.unlock(); // 3

}

// 1. Lock head.

// 2. Try deq.

// 3. Unlock head.

public T deq() {

try {

headLock.lock(); // 1

return tryDeq(); // 2

} finally {

headLock.unlock(); // 3

}

// 1. Ensure queue is not full

// 2. Save data at tail.

// 3. Increment tail.

protected void tryEnq(T x) {

int tail2 = (tail + 1) % data.length; // 1, 3

if (tail2 == head) // 1

throw new BufferOverflowException(); // 1

data[tail] = x; // 2

tail = tail2; // 3

}

// 1. Ensure queue is not empty.

// 2. Return data at head.

// 3. Increment head.

protected T tryDeq() {

if (head == tail) // 1

throw new BufferUnderflowException(); // 1

T x = data[head]; // 2

head = (head + 1) % data.length; // 3

return x; // 2

}

array-queue.java/ArrayQueue.java at master · moocf/array-queue.java · GitHub

Uh oh!

Expand file tree

Breadcrumbs

ArrayQueue.java

Latest commit

History

Breadcrumbs

ArrayQueue.java

File metadata and controls