Java Queue, Stack and Deque
Java Interface:
FIFO: Queue, Deque (not necessary) LIFO: Stack (do not use), Deque
deque和queue的关系，看Java Documentation, deque是queue的subinterface，所以deque实现了queue的功能。
Implementation Class:
Array: ArrayDeque
Linked List: LinkedList
Queue <> = new ArrayDeque
In Java
Queue
Java里的queue不一定是FIFO，例外是priority queue (heap)。所以其实in general， queue是一种数据结构，一头进，另一头出的基本功能。因为我们不希望random access, 所以arraylist就不合适了。
enqueue 入队: offer() at the tail dequeue 出队: poll() at the head peek 看第一个: peek() look at the head without polling it out
queue在空了的时候如果peek()和poll() 会拿出null. 下面表格的左右两组API不可以混用，必须consistent.
在空了时如果调用remove()或者element(), NoSuchElementException; add(e)的异常是满了，比如用ArrayBlockingQueue就有容量限制，会throw IllegalStateException。如果是offer()，在满了时返回false，表示加失败了。
Deque
stack在空了的时候如果peek()和poll() 会拿出null，deque也是一样.
其他
isEmpty()
size()
stack method的Push Pop Peep 尽量不用
其实对应的是2个throw exception那组的addfirst removefirst 和 peekfirst 真是讨厌
Operation Cost O(1)
以上所有的实现，时间复杂度都是O(1) 常用LinkedList和ArrayDeque（Java6以后）实现。在实际使用中，更常用ArrayDeque，因为locality更低、overhead更好、出现null的时候没有歧义。而只有一个情况下需要使用linkedlist：版本是Java6之前的。
此外，ArrayDeque不允许null value，因为不能确定此时是值为null还是空了。这个时候如果用linkedlist实现就没有问题，因为list就可以存null（这里不是在说value是null）。
Implementation
arrayDeque和Linkedlist是用来实现stack queue 和deque这几个data structure的implementation class
Implement a Stack with Linked List
更好的是在头部插入删除，而不是在尾部。因为头部的操作更容易，而尾部即便是维护一个tail，每次在删除的时候就没了，又得再维护一个。
class ListNode{
int value;
ListNode next;
public ListNode(int value){
this.value=value;
}
}
public class Stack{
private ListNode head;
Stack(){
}
public void push(int e){
ListNode newhead = new ListNode(e);
newhead.next=head;
head=newhead;
}
public integer pop(){
if (head==null){
return null; //不要return head 不然类型不一致
}
ListNode prev=head;
head = head.next;
prev.next=null; //这里要防呆
return head.value;
}
public integer peek(){
if (head==null){
return null; //不要return head 不然类型不一致
}
return head.value;
}
}
//push()
//pop()
//peek()Implement a Queue with Linked List
头进尾出：存在和上面一样的问题 尾进头出：和刚才一样
class ListNode{
int value; //如果允许存null value
ListNode next;
public ListNode(int value){
this.value = value;
}
}
public class QueueStack{
private ListNode head;
private ListNode tail;
Queue(){
}
public void offer(int e){
ListNode newtail = new ListNode(e);
if (head == null){
head = newtail;
tail = head;
}else{
tail.next = newtail;
tail = newtail;
}
public nteger poll(){
if (head ==n ull){
return null;
}
ListNode node = head;
head = head.next;
if (head == null){ //重要 只剩一个元素的时候head和tail是一个
tail = null;
}
node.next = null;
return node.value;
}
public nteger peek(){
if (head == null){
return null;
}
return head.value;
}
}
Implement a Deque with Linked List
doubly linked list
Implement a Queue with Circular Array (Ring Buffer)
两种写法：
head = head +1==array.length?0: head+1;head = (head+1)%array.length;
不要用这种写法，要防止overflow：
head++;
array[(head%array.length)]
head有数据，物理意义是next element in queue tail没数据，物理意义是next available position - poll: grab element at head, head++ - offer: put one element, tail++
当head==tail时，它要么是empty，要么满了，怎么知道是满了？解决方法：
维护一个size 当size==0, empty; size==array.length, full
public class BoundedQueue {
int head;
int tail;
int size;
Integer[] array;
public BoundedQueue(int cap) {
array = new Integer[cap];
head = tail = 0;
size = 0
}
public boolean offer(Integer ele) {
//1
if (size == array.length){
return false;
}
//2
array[tail] = ele;
tail = tail + 1 == array.length ? 0 : tail + 1;
size ++;
return true;
}
public Integer peek() {
if (size == 0) {
return null;
}
return array[head];
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public boolean isFull() {
return size == array.length;
}
}如果不支持加一个size，就改变head和tail的物理意义，使得head+1==tail时是空，而head==tail时是满，也就是head指的格子不存数据，tail的格子也不存数据。 - poll: grab element at head+1, head++ - offer：put one element, tail++
class Solution(object):
def __init__(self, k):
"""
Initialize your data structure here. Set the size of the queue to be k.
:type k: int
"""
self.array = [None]*(k+1)
self.head = 0 #index of prev_to_the_next_available
self.tail = 1 #index of the first available spot
def enQueue(self, value):
"""
Insert an element into the circular queue. Return true if the operation is successful.
:type value: int
:rtype: bool
"""
if self.isFull():
return False
else:
self.array[self.tail]=value
self.tail=(self.tail+1)%len(self.array)
return True
def deQueue(self):
"""
Delete an element from the circular queue. Return true if the operation is successful.
:rtype: bool
"""
if self.isEmpty():
return False
else:
self.head=(self.head+1)%len(self.array)
return True
def Front(self):
"""
Get the front item from the queue.
:rtype: int
"""
return -1 if self.isEmpty() else self.array[self.head+1]
def Rear(self):
"""
Get the last item from the queue.
:rtype: int
"""
return -1 if self.isEmpty() else self.array[(self.tail-1+len(self.array))%len(self.array)]
def isEmpty(self):
"""
Checks whether the circular queue is empty or not.
:rtype: bool
"""
return self.tail-self.head==1
def isFull(self):
"""
Checks whether the circular queue is full or not.
:rtype: bool
"""
return self.tail==self.head如果满了，可以1.5X extension的话可以把数据从head拷贝到tail. 这里不是用system.copyof的方法，而是一个一个copy这些格子
Implement a Resizeable Stack with Circular Array
Implement a Resizeable Deque with Circular Array
Last updated