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

In [1]:

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
}

Out[1]:

defined trait DequeADT

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.

In [2]:

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
}

Out[2]:

import scala.reflect.ClassTag


defined class ADeque

Linked deque

In [3]:

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
}

Out[3]:

defined class DLink
defined class LDeque

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.

Yuta Nishino

Queues and Deques

Queues

Deque ADT

Array-based deque

Linked deque

Deque as queue, deque as stack