哎涣达，面試被問住了吐葵，就記得當(dāng)時學(xué)過的先進(jìn)后出了污筷，在此記錄下工闺。
(轉(zhuǎn)載了一個大神回答，地址在這:https://segmentfault.com/a/1190000002516799
Stack
棧（Stack）是限制僅在表的一端進(jìn)行插入和刪除運(yùn)算的線性表瓣蛀。
java 沒有棧這樣的數(shù)據(jù)結(jié)構(gòu)陆蟆，如果想利用先進(jìn)后出（FILO）這樣的數(shù)據(jù)結(jié)構(gòu)，就必須自己實(shí)現(xiàn)惋增。
要實(shí)現(xiàn)Stack叠殷，至少應(yīng)該包括：
- pop() 出棧操作，彈出棧頂元素器腋。
- push(E e) 入棧操作
- peek() 查看棧頂元素
- isEmpty() 棧為空
另外溪猿，實(shí)現(xiàn)一個棧，還應(yīng)該考慮到幾個問題：
- 棧的初始大小以及棧滿以后如何新增椚宜空間
- 對棧進(jìn)行更新時需要進(jìn)行同步
有三種實(shí)現(xiàn)的方式诊县，數(shù)組，容器措左，以及鏈表的方法依痊。
數(shù)組：
import java.util.*;
public class StackArray{
private int[] array;//用數(shù)組實(shí)現(xiàn)
private int top; //棧頂指針
private final static int size = 100;
public StackArray(){
array = new int[size];
top = -1; //棧空的時候
}
//壓棧
public void push(int element){
if(top == size-1){
throw new StackOverflowError();
}
else
array[++top] = element;
}
//彈棧
public int pop(){
if(top == -1){
throw new EmptyStackException();
}
return array[top--];
}
//判斷是否為空
public boolean isEmpty(){
return top == -1;
}
//返回棧頂元素
public Integer peek(){
if(top == -1){
throw new EmptyStackException();
}
return array[top];
}
}
容器
public interface Stack<T> {
public T pop();
public void push(T element);
public boolean isEmpty();
public T peek();
}
package gsm;
import java.util.*;
public class StackList<T> implements Stack<T> {
private List<T> list ; //用容器實(shí)現(xiàn)
StackList(){
list = new ArrayList<T>();
}
//彈棧
public T pop(){
if(this.isEmpty() == true){
throw new EmptyStackException();
}
return list.remove(list.size()-1);
}
//壓棧
public void push(T element){
list.add(element);
}
//判斷是否為空
public boolean isEmpty(){
return list.size() == 0;
}
//返回棧頂元素
public T peek(){
if(this.isEmpty() == true){
throw new EmptyStackException();
}
return list.get(list.size()-1);
}
}
鏈表
import java.util.EmptyStackException;
public class LinkedStack<T> implements Stack<T>{
//不用容器或者數(shù)組等數(shù)據(jù)結(jié)構(gòu)存儲節(jié)點(diǎn)
//Node定義一個節(jié)點(diǎn)類
private static class Node<U>{
private U item; //存儲的data
private Node<U> next; //類似指針
Node(){
this.item = null;
this.next = null;
}
Node(U item, Node<U> next){
this.item = item;
this.next = next;
}
boolean end(){
return item == null && next == null;
}
}
private Node<T> top ; //棧頂指針
LinkedStack(){
top = new Node<T>();
}
//彈棧
public T pop(){
if(this.isEmpty() == true){
throw new EmptyStackException();
}
T result = top.item;
if(!top.end())
{
top = top.next;
}
return result;
}
//壓棧
public void push(T element){
top = new Node<T>(element, top);
}
//判斷是否為空
public boolean isEmpty(){
return top.end();
}
//返回棧頂元素
public T peek(){
if(this.isEmpty() == true){
throw new EmptyStackException();
}
T result = top.item;
return result;
}
}
可以發(fā)現(xiàn)容器果然是java的一個利器，方便高效胸嘁。
