棧（Stack）是限定僅在表尾進(jìn)行插入或刪除操作的線程表。因此對(duì)棧來(lái)說(shuō)表尾端有其特殊含義清寇，稱為棧頂（top）喘漏，相應(yīng)的表頭端稱為棧底（bottom）。
image
棧是一種后進(jìn)先出（last in first out）的線性表华烟，簡(jiǎn)稱LIFO翩迈。
棧的抽象數(shù)據(jù)類型定義
package com.codestd.study.stack;
/**
* 棧ADT
*/
public interface Stack<E> {
/**
* 查看棧頂元素，僅僅查看元素盔夜，不從棧中取出负饲。
*/
E peek();
/**
* 向棧中添加元素搅方。
*/
void push(E e);
/**
* 取出棧頂元素
*/
E pop();
/**
* 清空棧
*/
void clear();
/**
* 棧中元素的數(shù)量，如果棧為空绽族，則返回0
*/
int size();
/**
* 判斷棧是否為空
*/
boolean isEmpty();
/**
* 判斷棧是否已滿
*/
boolean isFull();
}
棧的表示和實(shí)現(xiàn)
前文講過(guò)，計(jì)算機(jī)存儲(chǔ)數(shù)據(jù)有兩種方式衩藤，一種是順序存儲(chǔ)吧慢，一種是非順序存儲(chǔ)。棧對(duì)應(yīng)兩種存儲(chǔ)方式有兩種實(shí)現(xiàn)方式：一種是數(shù)組赏表，一種是單向鏈表检诗。
棧的數(shù)組實(shí)現(xiàn)
數(shù)組實(shí)現(xiàn)棧不需要記錄棧底，只需要記錄棧頂指針就可以了瓢剿。入棧的時(shí)候棧頂指針后移逢慌，出棧的時(shí)候棧頂指針前移。使用數(shù)組實(shí)現(xiàn)是比較簡(jiǎn)單的间狂，也是比較容易實(shí)現(xiàn)的攻泼。
image
package com.codestd.study.stack;
import java.util.NoSuchElementException;
/**
* 數(shù)組實(shí)現(xiàn)棧
*/
public class ArrayStack<E> implements Stack<E> {
private final int maxSize;
private final E[] elementData;
private int top = -1;
@SuppressWarnings("unchecked")
public ArrayStack(int maxSize) {
this.maxSize = maxSize;
this.elementData = (E[]) new Object[this.maxSize];
}
@Override
public E peek() {
if (this.isEmpty()) {
throw new NoSuchElementException("棧空");
}
return this.elementData[this.top];
}
@Override
public void push(E e) {
if (this.isFull()) {
throw new RuntimeException("棧滿");
}
this.top++;
this.elementData[this.top] = e;
}
@Override
public E pop() {
if (this.isEmpty()) {
throw new NoSuchElementException("椉螅空");
}
E el = this.elementData[this.top];
this.elementData[this.top] = null;
this.top--;
return el;
}
@Override
public void clear() {
for (int i = 0; i < this.top + 1; i++) {
this.elementData[i] = null;
}
this.top = -1;
}
@Override
public int size() {
return this.top + 1;
}
@Override
public boolean isEmpty() {
return this.size() == 0;
}
@Override
public boolean isFull() {
return (this.top + 1) == this.maxSize;
}
}
棧的鏈表實(shí)現(xiàn)
是用鏈表實(shí)現(xiàn)會(huì)相對(duì)復(fù)雜一點(diǎn)忙菠。這里我們使用的是單向鏈表。
與前面講的單向鏈表不同纺弊，這里我們不再是使用next指向下一個(gè)節(jié)點(diǎn)牛欢，而是使用prev指向上一個(gè)節(jié)點(diǎn)。然后指針top始終指向最新的節(jié)點(diǎn)淆游。如果取出棧頂數(shù)據(jù)傍睹，則指針指向棧頂元素的prev。
image
下面我們使用代碼來(lái)實(shí)現(xiàn)犹菱。
package com.codestd.study.stack;
import java.util.NoSuchElementException;
/**
* 鏈表實(shí)現(xiàn)棧
*/
public class LinkedStack<E> implements Stack<E>{
private Node<E> top;
private int size;
private int maxSize = Integer.MAX_VALUE;
public LinkedStack() {
}
public LinkedStack(int maxSize) {
this.maxSize = maxSize;
}
@Override
public E peek() {
if (this.isEmpty()) {
throw new NoSuchElementException("棧中沒(méi)有元素");
}
return this.top.item;
}
@Override
public void push(E e) {
if (this.isFull()) {
throw new RuntimeException("棧滿");
}
if (this.top == null) {
this.top = new Node<>(e);
} else {
Node<E> node = new Node<>(e);
node.prev = this.top;
this.top = node;
}
this.size++;
}
@Override
public E pop() {
if (this.isEmpty()) {
throw new NoSuchElementException("棧中沒(méi)有元素");
}
Node<E> node = this.top;
this.top = node.prev;
node.prev = null;
this.size--;
return node.item;
}
@Override
public void clear() {
Node<E> node = this.top;
while (node != null) {
Node<E> prev = node.prev;
node.prev = null;
node = prev;
}
this.top = null;
this.size = 0;
}
@Override
public int size() {
return this.size;
}
@Override
public boolean isEmpty() {
return this.size == 0;
}
@Override
public boolean isFull() {
return this.size == this.maxSize;
}
private static class Node<E> {
E item;
Node<E> prev;
public Node(E item) {
this.item = item;
}
}
}
