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

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


2.實現(xiàn)

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

相對來說，順序表的實現(xiàn)上要更為簡單一些，這里我們優(yōu)先用順序表實現(xiàn)棧。

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 概念
隊列：只允許在一端進(jìn)行插入數(shù)據(jù)操作，在另一端進(jìn)行刪除數(shù)據(jù)操作的特殊線性表，隊列具有先進(jìn)先出FIFO(FirstIn First Out) 入隊列：進(jìn)行插入操作的一端稱為隊尾（Tail/Rear） 出隊列：進(jìn)行刪除操作的一端稱為隊頭（Head/Front）

2.實現(xiàn)
隊列也可以數(shù)組和鏈表的結(jié)構(gòu)實現(xiàn)，使用鏈表的結(jié)構(gòu)實現(xiàn)更優(yōu)一些，因為如果使用數(shù)組的結(jié)構(gòu)，出隊列在數(shù)組頭上出數(shù)據(jù)，效率會比較低。

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;
}
}

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

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

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