Java中棧和隊列的概念和使用

一：棧(Stack)
1 概念
棧：一種特殊的線性表，其只允許在固定的一端進行插入和刪除元素操作。進行數據插入和刪除操作的一端稱為棧頂，另一端稱為棧底。棧中的數據元素遵守后進先出LIFO（Last In First Out）的原則。
壓棧：棧的插入操作叫做進棧/壓棧/入棧，入數據在棧頂。
出棧：棧的刪除操作叫做出棧。出數據在棧頂。


2.實現

1. 利用順序表實現，即使用尾插 + 尾刪的方式實現
2. 利用鏈表實現，則頭尾皆可

相對來說，順序表的實現上要更為簡單一些，這里我們優先用順序表實現棧。

public class MyStack
{ //不考慮擴容問題
private int[] array = new int[100]; 
private int size = 0;
public void push(int v)
{ 
array[size++] = v; 
}
public int pop()
{ 
return array[--size]; 
}
public int peek() 
{
return array[size - 1]; 
}
public boolean isEmpty() 
{ 
return size == 0; 
}
public int size() 
{ 
return size;
}
}`

二：隊列(Queue)
1 概念
隊列：只允許在一端進行插入數據操作，在另一端進行刪除數據操作的特殊線性表，隊列具有先進先出FIFO(FirstIn First Out) 入隊列：進行插入操作的一端稱為隊尾（Tail/Rear） 出隊列：進行刪除操作的一端稱為隊頭（Head/Front）

2.實現
隊列也可以數組和鏈表的結構實現，使用鏈表的結構實現更優一些，因為如果使用數組的結構，出隊列在數組頭上出數據，效率會比較低。

class Node
{
int val;
Node next;
Node(int val, Node next)
{ 
this.val = val; 
this.next = next; 
}
Node(int val) 
{ 
this(val, null); 
}
}
public class MyQueue
{
private Node head = null;
private Node tail = null;
private int size = 0; 
public void offer(int v) 
{ 
Node node = new Node(v, head);
if (tail == null)
{
tail = head;
}
size++; 
}
public int poll() 
{ 
if (size == 0)
{
throw new RuntimeException("隊列為空"); 
}
Node oldHead = head;
head = head.next; 
if (head == null)
{ tail = null; 
}
size--; 
return oldHead.val;
}
public int peek()
{
if (size == 0)
{
throw new RuntimeException("隊列為空");
}
return head.val;
}
public boolean isEmpty() 
{
return size == 0;
}
public int size()
{ 
return size;
}
}

實際中我們還可能遇到循壞隊列：
數組下標循壞的小技巧：
1.1. 下標最后再往后(offset 小于 array.length): index = (index + offset) % array.length

1. 下標最前再往前(offset 小于 array.length): index = (index + array.length - offset) % array.length
   

雙端隊列 (Deque)
概念
雙端隊列（deque）是指允許兩端都可以進行入隊和出隊操作的隊列，deque 是 “double ended queue” 的簡稱。
那就說明元素可以從隊頭出隊和入隊，也可以從隊尾出隊和入隊。