轉(zhuǎn)載請標(biāo)明出處竖哩，謝謝玄组！
http://www.reibang.com/p/8cb602ef4e21
關(guān)聯(lián)文章
冒泡思灰、選擇排序 http://www.reibang.com/p/176b0b892591
棧和隊列 http://www.reibang.com/p/8cb602ef4e21
順序表祷舀、單雙鏈表 http://www.reibang.com/p/3aeb5998e79e
二叉樹 http://www.reibang.com/p/de829eab944c
圖論 http://www.reibang.com/p/cf03e51a3ca2
棧和隊列
棧：只允許在表的末端進行插入和刪除的線性表本涕。基于數(shù)組存儲表示的棧稱為 順序棧收津，基于鏈表的存儲表示的棧稱為鏈棧
棧的存儲特性可以理解成子彈壓入彈夾中饿这。先壓入的子彈總數(shù)在最后才彈出。因此棧也稱為先進后出(LIFO, Last In First Out) 的線性表
下面用代碼表示下：采用鏈?zhǔn)綏５姆绞?/p>
public class Node<T> {
T data;//結(jié)點數(shù)據(jù)
Node next;//指針
private Node(T data) {
this.data = data;
}
public Node() {
}
}
public class Stack {
private Node stackTop; //棧頂
private Node stackBottom; //棧底
public Stack(Node stackTop, Node stackBottom) {
this.stackTop = stackTop;
this.stackBottom = stackBottom;
}
private Stack() {
}
}
入棧：將原本棧頂指向的節(jié)點交由新節(jié)點來指向撞秋，棧頂指向新加入的節(jié)點
/**
* 入棧
*
* @param stack 原本的棧
* @param newNode 新的結(jié)點
*/
public void pushToStack(Stack stack, Node newNode) {
/*新節(jié)點變成棧頂*/
newNode.next = stack.stackTop;
stack.stackTop = newNode;
}
空棧：如果棧頂和棧底指向相同长捧，說明是空棧
/**
* 判斷是否是空棧
*
* @param stack
* @return
*/
public boolean isEmpty(Stack stack) {
return stack.stackTop == stack.stackBottom;
}
遍歷：棧頂指針不斷向下移，直到到達棧底吻贿。為了避免影響原棧串结，使用臨時結(jié)點指向stackTop并且隨之一起移動。
/**
* 棧的遍歷
*
* @param stack
*/
public void traverse(Stack stack) {
Node temp = stack.stackTop;
/*如果空棧不執(zhí)行*/
if (isEmpty(stack)) {
System.out.println("空棧");
return;
}
while (!isEmpty(stack) && temp != null) {
System.out.println(temp.data);
temp = temp.next;
}
}
出棧：將棧頂指針向下移動一位
/**
* 出棧
*
* @param stack
*/
public void popStack(Stack stack) {
if (isEmpty(stack)) {
return;
}
stack.stackTop = stack.stackTop.next;
}
清空棧：實際上就是不斷的出棧廓八，直到到達棧底
/**
* 清空棧
*
* @param stack
*/
public void clearStack(Stack stack) {
if (isEmpty(stack)) {
return;
}
while (!isEmpty(stack)) {
popStack(stack);
}
}
測試：
@Test
public void test() {
Stack stack = new Stack();
for (int i = 0; i < 5; i++) {
pushToStack(stack, new Node("我是結(jié)點" + i));
}
System.out.println("棧的長度 = "+ getLength(stack));
traverse(stack);
popStack(stack);
popStack(stack);
popStack(stack);
System.out.println("------出棧后-------");
traverse(stack);
clearStack(stack);
System.out.println("------清空棧-------");
traverse(stack);
}
隊列
隊列：隊列是限定數(shù)據(jù)存儲位置的一種線性表奉芦，它允許在一端插入，再另一端刪除剧蹂。允許插入的一端叫隊尾声功，允許刪除的一端叫做隊頭。
隊列基于數(shù)組的存儲表示稱為順序隊列宠叼。是利用一個一維數(shù)組 array[maxLength]表示存儲的.并且利用了2個指針front和rear分別表示隊頭和隊尾的位置先巴。
如圖表示：當(dāng)front等于rear時，此隊列不是還剩一個元素冒冬，而是空隊列伸蚯。
當(dāng)有數(shù)據(jù)插入的時候，數(shù)據(jù)插入的位置是當(dāng)前rear的位置简烤，而rear的值就要前進一位剂邮，因為rear永遠指向下一個數(shù)據(jù)的存儲位置。
當(dāng)數(shù)據(jù)刪除的時候 首先要把當(dāng)前front指向位置的數(shù)據(jù)記錄下來横侦，然后front的指向位置就要+1挥萌，最后把記錄的元素返回。因為front指向的位置永遠都是對頭元素
那么問題來了枉侧，rear永遠指向下一個位置元素的存儲位置引瀑，那么如果出現(xiàn)上圖的情況不就是存儲的內(nèi)存溢出了嗎？ 實際上這個溢出是”假溢出“
因為我們可以發(fā)現(xiàn) 再數(shù)據(jù)的前面實際上還有空位置可以利用榨馁。根據(jù)這種情況憨栽，為了充分利用資源空間從而引出了循環(huán)隊列
用2個公式表示
隊頭指針進1 ： front = (front+1)%maxLength ;
隊尾指針進1 ： rear = (rear+1)%maxLength ;
如果循環(huán)隊列讀取元素的速度大于存入的速度，隊頭指針很快就趕上隊尾指針，一旦front == rear 則變成空隊列屑柔，反之屡萤，如果存入元素的速度大于讀取的，隊尾指針趕上隊頭指針锯蛀，如果隊列滿就不能再添加數(shù)據(jù)了灭衷。為了區(qū)分空隊列和滿隊列次慢，用(rear+1)%maxLength == front來表示滿隊列旁涤，用 rear== front表示空隊列。
同樣的用代碼測試一下：用順序隊列表示下
private final static int MAX_LENGTH = 5;
public class Queue {
public String[] array;
public int front;
public int rear;
public Queue() {
front = 0;
rear = 0;
array = new String[MAX_LENGTH];
}
}
判斷是否滿隊列 ：用公式rear = (rear+1)%maxLength ==front;
/**
* 判斷是否滿隊列
*
* @param queue
* @return
*/
public boolean isFull(Queue queue) {
return (queue.rear + 1) % MAX_LENGTH == queue.front;
}
判斷是否是空隊列：用公式 rear== front
/**
* 判斷是否是空隊列
*
* @param queue
* @return
*/
public boolean isEmpty(Queue queue) {
return queue.rear == queue.front;
}
入隊列 ：數(shù)據(jù)插入的位置是當(dāng)前rear的位置迫像，而rear的值就要前進一位劈愚，因為rear永遠指向下一個數(shù)據(jù)的存儲位置。
/**
* 添加數(shù)據(jù)
*
* @param queue
* @param data
*/
public void enQueue(Queue queue, String data) {
if (isFull(queue)) {
System.out.println("滿隊列");
return;
}
queue.array[queue.rear] = data;
queue.rear = (queue.rear + 1) % MAX_LENGTH;
}
刪除數(shù)據(jù) ：front的指向位置就要向前一位
/**
* 刪除數(shù)據(jù)
*
* @param queue
*/
public void delQueue(Queue queue) {
if (isEmpty(queue)) {
System.out.println("空隊列");
return;
}
queue.front = (queue.front + 1) % MAX_LENGTH;
}
清空隊列：
/**
* 清空數(shù)據(jù)
*
* @param queue
*/
public void clear(Queue queue){
if (isEmpty(queue)) {
System.out.println("空隊列");
return;
}
while (!isEmpty(queue)){
System.out.println(queue.array[queue.front]);
queue.front = (queue.front+1) % MAX_LENGTH;
}
}
遍歷隊列：使用臨時變量防止破壞源數(shù)據(jù)
/**
* 遍歷
*
* @param queue
*/
public void traverse(Queue queue) {
if (isEmpty(queue)) {
System.out.println("空隊列");
return;
}
int tempFront = queue.front;
while (tempFront!= queue.rear) {
System.out.println(queue.array[tempFront]);
tempFront = (tempFront + 1) % MAX_LENGTH;
}
}
測試一下：
@Test
public void test() {
Queue queue = new Queue();
enQueue(queue, "1");
enQueue(queue, "2");
enQueue(queue, "3");
traverse(queue);
System.out.println("刪除一個數(shù)據(jù)后");
delQueue(queue);
traverse(queue);
System.out.println("清空數(shù)據(jù)后");
clear(queue);
traverse(queue);
}
最近發(fā)現(xiàn)了一個問題闻妓，即當(dāng)前長度如果是5菌羽，當(dāng)添加第5個數(shù)據(jù)的時候就已經(jīng)提示隊列滿了，因為（rear+1）%5 = (4+1)%5 = 0 而此時front(都不出隊的情況下)=0 這個和判空的條件front=rear實際是沖突的由缆，那么實際情況真是這樣嗎注祖？
其實為了區(qū)分這種情況，循環(huán)隊列判斷滿隊列實際上是犧牲了一個空間來和空隊列做區(qū)分均唉。
如果新元素成功入隊的話是晨，我們的tail也等于2，那么此時就成了 tail == front 舔箭，一開始我們提到過罩缴，當(dāng)隊列為空的tail == front，現(xiàn)在呢层扶，如果隊列為滿時tail也等于front箫章，那么我們就無法區(qū)分，隊列為滿時和隊列為空時收的情況了.
所以镜会，在循環(huán)隊列中檬寂，我們總是浪費一個空間，來區(qū)分隊列為滿時和隊列為空時的情況戳表，也就是當(dāng) ( tail + 1 ) % capacity == front的時候桶至，表示隊列已經(jīng)滿了，當(dāng)front == tail的時候扒袖，表示隊列為空塞茅。
圖片.png
原文：https://www.php.cn/java-article-416578.html
