定義
先入后出烂瘫，有點(diǎn)類似將書(shū)放在抽屜里，先放進(jìn)去的書(shū)奇适，如果想拿到他坟比，必須將他上面書(shū)拿完才可以，粗俗的形容可以這么比喻：“吃了吐”叫棧滤愕，“吃了拉”叫隊(duì)列温算，話粗理不粗。棧是一種“操作受限”的線性表间影，只允許一段插入和刪除數(shù)據(jù)注竿。
從功能上看，數(shù)組或鏈表確實(shí)可代替棧，但是在特定的情況中巩割，數(shù)組和鏈表暴露的接口太多裙顽，操作上雖然靈活，但是很多條件不可控宣谈，使用上當(dāng)然容易出現(xiàn)問(wèn)題愈犹。
當(dāng)某個(gè)數(shù)據(jù)集合只涉及在一段插入和刪除數(shù)據(jù)，并且滿足先進(jìn)后出的特性闻丑，我們就應(yīng)該首選棧這種數(shù)據(jù)結(jié)構(gòu)漩怎。
實(shí)現(xiàn)
根據(jù)其定義和特點(diǎn)，棧主要包含兩個(gè)操作嗦嗡，入棧和出棧勋锤。數(shù)組和鏈表都可以實(shí)現(xiàn)，用數(shù)組實(shí)現(xiàn)的棧叫做 順序棧侥祭，用鏈表實(shí)現(xiàn)的棧叫做 鏈?zhǔn)綏?/strong>叁执。后面會(huì)貼上具體的實(shí)現(xiàn)代碼和測(cè)試用例。
棧存儲(chǔ)數(shù)據(jù)只需要一個(gè)大小為 n 的數(shù)組就足夠了矮冬，在操作數(shù)據(jù)的過(guò)程中谈宛，只需要一兩個(gè)臨時(shí)變量存儲(chǔ)空間，所以空間復(fù)雜度是 O(1)胎署，至于入棧和出棧的時(shí)間復(fù)雜度也是 O(1)吆录。
練習(xí)
數(shù)組實(shí)現(xiàn)棧(支持動(dòng)態(tài)擴(kuò)容)
需要注意點(diǎn)：
- 當(dāng)數(shù)據(jù)不斷增加，大小達(dá)到閾值硝拧，也就是容器滿了径筏，此時(shí)大小需要擴(kuò)容到原來(lái)的兩倍。
- 當(dāng)數(shù)據(jù)不斷減小障陶，大小達(dá)到整個(gè)大小四分之一時(shí)滋恬，此時(shí)大小需要縮小為原來(lái)的 1/2。
class ArrayStack<T> implements Iterable<T>{
private T[] data;
private int totalCount;
private int count;
ArrayStack(int capacity) {
data = (T[]) new Object[capacity];
totalCount = capacity;
}
private boolean push(T t) {
if (count == totalCount) {
resize(totalCount * 2);
}
data[count] = t;
count++;
System.out.println("push: " + t + " data:\t" + Arrays.toString(data));
return true;
}
private T pop() {
if (count == 0) return null;
T t = data[count - 1];
data[count - 1] = null;
count --;
if (count == totalCount / 4 && totalCount / 2 != 0) {
resize(totalCount / 2);
}
System.out.println("pop: " + t + " data:\t" + Arrays.toString(data));
return t;
}
boolean isEmpty() {
return count == 0;
}
int size() {
return count;
}
T peek() {
if (count == 0) {
return null;
}
T t = data[count - 1];
System.out.println("peek: " + t + " data:\t" + Arrays.toString(data));
return t;
}
private void resize(int newSize) {
T[] newData = (T[]) new Object[newSize];
for (int i = 0; i < count; i++) {
newData[i] = data[i];
}
totalCount = newData.length;
System.out.println("擴(kuò)容前：" + data.length);
data = newData;
System.out.println("重新調(diào)整大小:\t" + data.length + " data:\t" + Arrays.toString(data));
}
public static void main(String[] args) {
ArrayStack<Integer> data = new ArrayStack<Integer>(4);
data.push(1);
data.push(2);
data.push(3);
data.push(4);
data.push(5);
data.push(6);
System.out.println("size:\t" + data.size());
System.out.println("isEmpty:\t" + data.isEmpty());
for (Integer datum : data) {
System.out.print(datum);
}
System.out.println();
data.pop();
data.pop();
data.pop();
data.pop();
data.peek();
data.peek();
data.peek();
}
@Override
public Iterator<T> iterator() {
return new ArrayIterator();
}
class ArrayIterator implements Iterator<T> {
int i = count;
@Override
public boolean hasNext() {
return i > 0;
}
@Override
public T next() {
return data[--i];
}
@Override
public void remove() {
}
}
}
這里如果需要支持加強(qiáng) for 循環(huán)抱究，則需要?jiǎng)?chuàng)建自定義實(shí)現(xiàn) Iterator 類恢氯。
運(yùn)行結(jié)果：
push: 1 data: [1, null, null, null]
push: 2 data: [1, 2, null, null]
push: 3 data: [1, 2, 3, null]
push: 4 data: [1, 2, 3, 4]
擴(kuò)容前：4
重新調(diào)整大小: 8 data: [1, 2, 3, 4, null, null, null, null]
push: 5 data: [1, 2, 3, 4, 5, null, null, null]
push: 6 data: [1, 2, 3, 4, 5, 6, null, null]
size: 6
isEmpty: false
654321
pop: 6 data: [1, 2, 3, 4, 5, null, null, null]
pop: 5 data: [1, 2, 3, 4, null, null, null, null]
pop: 4 data: [1, 2, 3, null, null, null, null, null]
擴(kuò)容前：8
重新調(diào)整大小: 4 data: [1, 2, null, null]
pop: 3 data: [1, 2, null, null]
peek: 2 data: [1, 2, null, null]
peek: 2 data: [1, 2, null, null]
peek: 2 data: [1, 2, null, null]
鏈表實(shí)現(xiàn)棧
需要注意的是臨界值的判斷。
class LinkedStack<T> implements Iterable<T> {
Node<T> head = null;
int count = 0;
void push(T t) {
Node<T> node = createNode(t);
if (head == null) {
head = node;
} else {
node.next = head;
head = node;
}
count++;
System.out.println("push:\t" + t + " data:\t" + head.toString());
}
T pop() {
if (head == null) {
return null;
}
T t = head.value;
head = head.next;
if (head != null) {
System.out.println("pop:\t" + t + " data:\t" + head.toString());
} else {
System.out.println("pop:\t" + t + " data:\tnull");
}
count--;
return t;
}
boolean isEmpty() {
return count == 0;
}
int size() {
return count;
}
T peek() {
if (head == null) {
return null;
}
T t = head.value;
System.out.println("peek:\t" + t + " data:\t" + head.toString());
return t;
}
Node<T> createNode(T t) {
return new Node<T>(t, null);
}
public static void main(String[] args) {
LinkedStack<Integer> stack = new LinkedStack<Integer>();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
System.out.println("size:\t" + stack.size());
System.out.println("isEmpty:\t" + stack.isEmpty());
for (Integer integer : stack) {
System.out.println(integer);
}
stack.peek();
stack.peek();
stack.peek();
stack.pop();
stack.pop();
stack.pop();
stack.pop();
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
for (T t : this) {
sb.append(t).append(" ");
}
sb.append("\n");
return sb.toString();
}
void clear() {
head = null;
count = 0;
}
@Override
public Iterator<T> iterator() {
return new LinkedIterator();
}
class LinkedIterator implements Iterator<T> {
Node<T> first = head;
int n = count;
@Override
public boolean hasNext() {
return n > 0;
}
@Override
public T next() {
T t = first.value;
first = first.next;
n--;
return t;
}
@Override
public void remove() {
}
}
}
運(yùn)行結(jié)果：
push: 1 data: 1
push: 2 data: 2 1
push: 3 data: 3 2 1
push: 4 data: 4 3 2 1
size: 4
isEmpty: false
4321
peek: 4 data: 4 3 2 1
peek: 4 data: 4 3 2 1
peek: 4 data: 4 3 2 1
pop: 4 data: 3 2 1
pop: 3 data: 2 1
pop: 2 data: 1
pop: 1 data: null
棧在括號(hào)匹配中的應(yīng)用
括號(hào)一般都是一一對(duì)應(yīng)的鼓寺，那可以用棧保存未匹配的左括號(hào)勋拟，從左到又進(jìn)行掃描。
class StackTest1 {
public static void main(String[] args) {
LinkedStack<String> stack = new LinkedStack<String>();
stack.push("[");
stack.push("{");
stack.push("『");
stack.push("「");
stack.push("」");
stack.push("』");
stack.push("}");
stack.push("]");
System.out.println(stack.toString());
System.out.println("is correct:\t" + isCorrect(stack));
}
private static boolean isCorrect(LinkedStack<String> stack) {
boolean isCorrect = true;
LinkedStack<String> stack1 = new LinkedStack<String>();
for (String s : stack) {
stack1.push(s);
}
Iterator<String> iterator = stack.iterator();
Iterator<String> iterator1 = stack1.iterator();
while (iterator.hasNext() && iterator1.hasNext()) {
if (!equals(iterator.next(), iterator1.next())) {
return false;
}
}
return isCorrect;
}
private static boolean equals(String one, String two) {
return ("[".equals(one) && "]".equals(two)) || ("[".equals(two) && "]".equals(one)) ||
("{".equals(one) && "}".equals(two)) || ("{".equals(two) && "}".equals(one)) ||
("「".equals(one) && "」".equals(two)) || ("「".equals(two) && "」".equals(one)) ||
("『".equals(one) && "』".equals(two)) || ("『".equals(two) && "』".equals(one));
}
}
瀏覽器在棧的應(yīng)用
一般瀏覽器支持回退和前進(jìn)功能妈候，其實(shí)可以通過(guò)棧來(lái)實(shí)現(xiàn)這個(gè)功能敢靡。
- 使用兩個(gè)棧，一個(gè)存儲(chǔ)后退的數(shù)據(jù)苦银，一個(gè)存儲(chǔ)前進(jìn)的數(shù)據(jù)
- 每次打開(kāi)新的網(wǎng)址啸胧，后退棧壓入赶站，前進(jìn)棧清空
- 每次回退網(wǎng)站，后退棧出棧纺念，前進(jìn)棧壓入
- 在已經(jīng)后退基礎(chǔ)上前進(jìn)贝椿，后退棧壓入，前進(jìn)棧出棧
- 每次前進(jìn)和后退都需要判斷各自棧是否可以進(jìn)行數(shù)據(jù)操作
class StackTest2 {
String currentPage = "";
LinkedStack<String> backStack;
LinkedStack<String> forwardStack;
StackTest2() {
backStack = new LinkedStack<String>();
forwardStack = new LinkedStack<String>();
}
void open(String url) {
if (currentPage != null) {
backStack.push(url);
forwardStack.clear();
}
showPage(url, "open");
}
boolean canGoBack() {
return !backStack.isEmpty();
}
boolean canGoForward() {
return !forwardStack.isEmpty();
}
void goBack() {
if (canGoBack()) {
String back = backStack.pop();
forwardStack.push(currentPage);
showPage(back, "go back");
}
}
void goForward() {
if (canGoForward()) {
String forward = forwardStack.pop();
backStack.push(currentPage);
showPage(forward, "go forward");
}
}
void showCurrentPage() {
System.out.println("current page url:\t" + currentPage);
}
void showPage(String url, String desc) {
this.currentPage = url;
System.out.println("current page url:\t" + this.currentPage + " desc:\t" + desc);
}
public static void main(String[] args) {
StackTest2 stack = new StackTest2();
stack.open("http://www.baidu.com");
stack.open("http://news.baidu.com/");
stack.open("http://news.baidu.com/ent");
stack.goBack();
stack.goBack();
stack.goForward();
stack.open("http://www.qq.com");
stack.goForward();
stack.goBack();
stack.goForward();
stack.goBack();
stack.goBack();
stack.goBack();
stack.goBack();
stack.showCurrentPage();
}
}
參考自極客時(shí)間
