棧的介紹
棧（stack），是一種線性存儲結(jié)構(gòu)胯舷，它有以下幾個特點：
- 棧中數(shù)據(jù)是按照"后進先出（LIFO, Last In First Out）"方式進出棧的。
- 向棧中添加/刪除數(shù)據(jù)時，只能從棧頂進行操作。
棧通常包括的三種操作：push甜攀、peek、pop琐馆。
- push -- 向棧中添加元素规阀。
- peek -- 返回棧頂元素。
- pop -- 返回并刪除棧頂元素的操作瘦麸。
下方這個示例圖就是一個典型的棧型結(jié)構(gòu)谁撼。在棧中有一個指針Top，永遠指向棧頂元素滋饲，如果棧為空厉碟，那么Top就為nil。在棧結(jié)構(gòu)中無論是入棧還是出棧屠缭，都是操作棧頂元素箍鼓。所以入棧順序與出棧順序是相反的。
棧型結(jié)構(gòu)示例圖
棧的示意圖
棧的示意圖
棧中的數(shù)據(jù)依次是 30 --> 20 --> 10
出棧
出棧示意圖
出棧前：棧頂元素是30勿她。此時袄秩，棧中的元素依次是 30 --> 20 --> 10
出棧后：30出棧之后，棧頂元素變成20逢并。此時之剧，棧中的元素依次是 20 --> 10
入棧
入棧示意圖
入棧前：棧頂元素是20。此時砍聊，棧中的元素依次是 20 --> 10
入棧后：40入棧之后背稼，棧頂元素變成40。此時玻蝌，棧中的元素依次是 40 --> 20 --> 10
Stack的實現(xiàn)
棧是一種后進先出的數(shù)據(jù)結(jié)構(gòu)蟹肘，對于Stack 我們希望至少要對外提供以下幾個方法：
| 名稱 | 描述 |
|---|---|
| Stack<T>() | 創(chuàng)建一個空的棧 |
| void Push(T s) | 往棧中添加一個新的元素 |
| T Pop() | 移除并返回最近添加的元素 |
| boolean IsEmpty() | 棧是否為空 |
| int Size() | 棧中元素的個數(shù) |
棧的Java實現(xiàn)
JDK包中也提供了"棧"的實現(xiàn)，它就是集合框架中的Stack類俯树。
數(shù)組實現(xiàn)的棧帘腹，能存儲任意類型的數(shù)據(jù)。
package com.pingkeke.rdf.sample;
import java.lang.reflect.Array;
/**
* 數(shù)組實現(xiàn)的棧许饿，能存儲任意類型的數(shù)據(jù).
*/
public class GeneralArrayStack<T> {
private static final int DEFAULT_SIZE = 12;
private T[] mArray;
private int count;
public GeneralArrayStack(Class<T> type) {
this(type, DEFAULT_SIZE);
}
public GeneralArrayStack(Class<T> type, int size) {
// 不能直接使用mArray = new T[DEFAULT_SIZE];
mArray = (T[]) Array.newInstance(type, size);
count = 0;
}
// 將val添加到棧中
public void push(T val) {
mArray[count++] = val;
}
// 返回“棧頂元素值”
public T peek() {
return mArray[count-1];
}
// 返回“棧頂元素值”阳欲，并刪除“棧頂元素”
public T pop() {
T ret = mArray[count-1];
count--;
return ret;
}
// 返回“棧”的大小
public int size() {
return count;
}
// 返回“椔剩”是否為空
public boolean isEmpty() {
return size()==0;
}
// 打印“椙蚧”
public void PrintArrayStack() {
if (isEmpty()) {
System.out.printf("stack is Empty\n");
}
System.out.printf("stack size()=%d\n", size());
int i=size()-1;
while (i>=0) {
System.out.println(mArray[i]);
i--;
}
}
public static void main(String[] args) {
String tmp;
GeneralArrayStack<String> astack = new GeneralArrayStack<String>(String.class);
// 將10, 20, 30 依次推入棧中
astack.push("10");
astack.push("20");
astack.push("30");
// 將“棧頂元素”賦值給tmp，并刪除“棧頂元素”
tmp = astack.pop();
System.out.println("tmp="+tmp);
// 只將“棧頂”賦值給tmp瓦糟，不刪除該元素.
tmp = astack.peek();
System.out.println("tmp="+tmp);
astack.push("40");
astack.PrintArrayStack(); // 打印棧
}
/**
*
*
*
* 運行結(jié)果：
*
* tmp=30
* tmp=20
* stack size()=3
*
* 40
* 20
* 10
*
* 結(jié)果說明：GeneralArrayStack是通過數(shù)組實現(xiàn)的棧筒愚，而且GeneralArrayStack中使用到了泛型。
*
*/
}
通過鏈表的形式來創(chuàng)建棧
package com.pingkeke.rdf.sample;
/**
* 我們接下來通過鏈表的形式來創(chuàng)建棧菩浙，方便擴充.
*/
public class Stack01 {
class Node {
int data;
Node pre; // 我們需要知道當(dāng)前結(jié)點的前一個結(jié)點
public Node(int data) {
this.data = data;
}
}
public Node head;
public Node current;
/**
* 入棧操作
* @param data
*/
public void push(int data) {
if (head == null) {
head = new Node(data);
current = head;
} else {
Node node = new Node(data);
/**
* 入棧操作時巢掺，下面兩行代碼是關(guān)鍵。
*/
node.pre = current; // current結(jié)點將作為當(dāng)前結(jié)點的前驅(qū)結(jié)點
current = node; // 讓current結(jié)點永遠指向新添加的那個結(jié)點
}
}
/**
* 出棧：返回并刪除棧頂元素的操作劲蜻。
* @return
*/
public Node pop() {
if (current == null) {
return null;
}
Node node = current; // current結(jié)點是我們要出棧的結(jié)點
current = current.pre; // 每出棧一個結(jié)點后陆淀，current后退一位
return node;
}
public static void main(String[] args) {
Stack01 stack = new Stack01();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println(stack.pop().data);
System.out.println(stack.pop().data);
System.out.println(stack.pop().data);
/**
* 運行結(jié)果:
* 3
2
1
*/
}
}
Java的 Collection集合 中自帶的"棧"(stack)的示例。
package com.pingkeke.rdf.sample;
import java.util.Stack;
/**
* Java的 Collection集合 中自帶的"棧"(stack)的示例.
*/
public class StackTest {
public static void main(String[] args) {
int tmp=0;
Stack<Integer> astack = new Stack<Integer>();
// 將10, 20, 30 依次推入棧中
astack.push(10);
astack.push(20);
astack.push(30);
// 將“棧頂元素”賦值給tmp斋竞，并刪除“棧頂元素”
tmp = astack.pop();
System.out.printf("tmp=%d\n", tmp);
// 只將“棧頂”賦值給tmp倔约，不刪除該元素.
tmp = (int)astack.peek();
System.out.printf("tmp=%d\n", tmp);
astack.push(40);
while(!astack.empty()) {
tmp = (int)astack.pop();
System.out.printf("tmp=%d\n", tmp);
}
}
/**
* 運行結(jié)果：
*
* tmp=30
* tmp=20
*
* tmp=40
* tmp=20
* tmp=10
*/
}
使用兩個隊列實現(xiàn)一個棧
我們先往棧內(nèi)壓入一個元素a。由于兩個隊列現(xiàn)在都是空坝初，我們可以選擇把a插入兩個隊列中的任一個浸剩。我們不妨把a插入queue1。接下來繼續(xù)網(wǎng)棧內(nèi)壓入b,c兩個元素鳄袍。我們把它們都插入queue1绢要。這個時候 queue1包含3個元素a,b,c其中a位于隊列的頭部，c位于隊列的尾部拗小。
現(xiàn)在我們考慮從棧內(nèi)彈出一個元素重罪。根據(jù)棧的后入先出的原則，最后被壓入棧的c應(yīng)該最先被彈出。由于c位于queue1的尾部剿配，而我們每次只能從隊列的頭部刪除元素搅幅，因此我們可以從queue1中依次刪除a/b/c并插入到queue2中，再從queue1中刪除c呼胚。這就相當(dāng)于從棧中彈出元素c了茄唐。我們可以用同樣的方法從棧內(nèi)彈出元素b。
接下來我們考慮從棧內(nèi)壓入一個元素d.此時queue1已經(jīng)有了一個元素蝇更，我們就把d插入到queue1的尾部沪编。如果我們再從棧內(nèi)彈出一個元素，此時被彈出的應(yīng)該是最后被壓入的d.由于d位于queue1的尾部年扩，我們只能先從頭部刪除 queue1的元素并插入到queue2蚁廓，直到queue1中遇到d再直接把它刪除。如圖所示：
使用兩個隊列實現(xiàn)一個棧
package com.pingkeke.rdf.sample;
import java.util.LinkedList;
/**
* 兩個隊列實現(xiàn)一個棧.
*/
public class Stack02 {
private LinkedList<String> queue1 = new LinkedList<String>();
private LinkedList<String> queue2 = new LinkedList<String>();
/**
* 入棧操作
* @param obj
*/
public void push(String obj) {
if(queue1.isEmpty()) {
queue2.add(obj);
}
if(queue2.isEmpty()) {
queue1.add(obj);
}
}
/**
* 出棧操作
* @return
*/
public String pop() {
// 兩個棧都為空時,沒有元素可以彈出
if (queue1.isEmpty()&&queue2.isEmpty()) {
try {
throw new Exception("stack is empty");
} catch (Exception e) {
}
}
if(queue1.isEmpty()){
while(queue2.size()>1){
queue1.add(queue2.poll());
}
return queue2.poll();
}
if(queue2.isEmpty()){
while(queue1.size()>1){
queue2.add(queue1.poll());
}
return queue1.poll();
}
return null;
}
public static void main(String[] args) throws Exception {
Stack02 stack = new Stack02();
stack.push("a");
stack.push("b");
stack.push("c");
System.out.println(stack.pop());
System.out.println(stack.pop());
stack.push("d");
System.out.println(stack.pop());
}
/**
* 運行結(jié)果:
* c
b
d
*/
}
