[Data Structure (Java)] Queue

https://crane206265.tistory.com/77

[Data Structure (Java)] Stack

저번에 stack을 다루었으니, 이번에는 queue입니다. stack과 queue의 비교는 저번글에 있으니 참고하시면 될 것 같습니다.

---

Queue API

API of Queue<E> class

methods	explanation
void enqueue(E e)	add an item to the collection (add to end)
E dequeue()	remove and return the item least recently added (remove from beginning)
E first()	return the first element
boolean isEmpty()	return if stack is empty
int size()	return the size of stack

---

Queue implementation -  Linked List

using SLL class,

public class LinkedQueue<E> implements Queue<E> {
    private SinglyLinkedList<E> list = new SinglyLinkedList<>();
    
    public LinkedQueue() {};
    
    public int size() { return list.size(); }
    public boolean isEmpty() { return list.isEmpty(); }
    public void enqueue(E e) { list.addLast(e); }
    public E first() { return list.first(); }
    public E dequeue() { return list.removeFirst(); }
}

 

* enqueue : addLast() / dequeue : removeFirst()

<-- to implement operation as running time O(1)

(removeLast() : O(n))

 

Properties about Linked-List queue
- running time analysis : O(1) for every operation
- memory use : scalable