Queues
Like stack, queue is a data structure that have ADT restricted compared with one of list. Queue can perform the operation that append an element at the rear of the queue and remove and return the element at the front. There is a data structure containing queue as a special case and it is called deque (double-ended queue). Deque can perform adding an element at the front of the queue and removing at the rear as well as all operations queue can.
Since queue implementation is also a special case of it of deque, I will show the array-based and linked implementation of deque. Array-based implementations of queue and deque is nearly identical and adding operations only deque can do is straightforward. Linked queue needs singly-linked list to implement, while linked deque needs doubly-linked list.
Deque ADT
trait DequeADT[E] {
def clear: Unit
def addFirst(item: E): Unit
def addLast(item: E): Unit
def pollFirst: Option[E]
def pollLast: Option[E]
def peekFirst: Option[E]
def peekLast: Option[E]
def length: Int
}
Array-based deque
Unlike list and stack, queue and deque needs circular list to implement. It is an array pretending the last element is the one preceding the first one.
import scala.reflect.ClassTag
class ADeque[E: ClassTag](size: Int = 10) extends DequeADT[E] {
private val maxSize = size
private var front: Int = 0
private var rear: Int = 0
private var listSize: Int = 0
private val listArray: Array[E] = new Array[E](maxSize)
def clear: Unit = {
front = 0
rear = 0
listSize = 0
}
def addFirst(item: E): Unit = {
listSize match {
case _ if listSize == maxSize =>
case _ =>
listArray(front) = item
front = (front + maxSize - 1) % maxSize
listSize += 1
}
}
def addLast(item: E): Unit = {
listSize match {
case _ if listSize == maxSize =>
case _ =>
rear = (rear + 1) % maxSize
listSize += 1
listArray(rear) = item
}
}
def pollFirst: Option[E] = {
listSize match {
case 0 => None
case _ =>
front = (front + 1) % maxSize
listSize -= 1
Some(listArray(front))
}
}
def pollLast: Option[E] = {
listSize match {
case 0 => None
case _ =>
val optionItem: Option[E] = Some(listArray(rear))
rear = (rear + maxSize - 1) % maxSize
listSize -= 1
optionItem
}
}
def peekFirst: Option[E] = {
listSize match {
case 0 => None
case _ => Some(listArray((front + 1) % maxSize))
}
}
def peekLast: Option[E] = {
listSize match {
case 0 => None
case _ => Some(listArray(rear))
}
}
def length: Int = listSize
}
Linked deque
class DLink[E](item: Option[E], nextVal: Option[DLink[E]], prevVal: Option[DLink[E]]) {
private var linkElement: Option[E] = item
private var nextLink: Option[DLink[E]] = nextVal
private var prevLink: Option[DLink[E]] = prevVal
def next: Option[DLink[E]] = nextLink
def setNext(nextVal: Option[DLink[E]]): Unit = nextLink = nextVal
def prev: Option[DLink[E]] = prevLink
def setPrev(prevVal: Option[DLink[E]]): Unit = prevLink = prevVal
def element: Option[E] = linkElement
def setElement(item: Option[E]): Unit = linkElement = item
}
class LDeque[E] extends DequeADT[E] {
private var front: DLink[E] = new DLink[E](None, None, None)
private var rear: DLink[E] = front
private var dequeSize: Int = 0
def clear: Unit = {
front = new DLink[E](None, None, None)
rear = front
dequeSize = 0
}
def addFirst(item: E): Unit = {
val element = new DLink[E](Some(item), front.next, Some(front))
// when deque is empty
front.next match {
case None => rear = element
case Some(_) =>
}
front.setNext(Some(element))
dequeSize += 1
}
def addLast(item: E): Unit = {
rear.setNext(Some(new DLink[E](Some(item), None, Some(rear))))
rear = rear.next.get
dequeSize += 1
}
def pollFirst: Option[E] = {
front.next match {
case None => None
case Some(link) =>
front.setNext(front.next.get.next)
if (front.next.isEmpty) rear = front
dequeSize -= 1
link.element
}
}
def pollLast: Option[E] = {
rear.element match {
case None => None
case Some(e) =>
val optionItem = rear.element
rear = rear.prev.get
dequeSize -= 1
optionItem
}
}
def peekFirst: Option[E] = {
front.next match {
case None => None
case Some(link) => link.element
}
}
def peekLast: Option[E] = rear.element
def length: Int = dequeSize
}
Deque as queue, deque as stack
Deque can perform all operation in the ADT in constant time. It means we can use it as queue, which is obvious, and as stack by restricting opeartion we use them to perform. However, since we have to use doubly-linked list to implement deque, the operation should be a bit slower when we use deque and it takes more space though the order of the time and space complexities are the same.