一、何為棧？
棧（stack）又名堆棧，它是一種運(yùn)算受限的線(xiàn)性表。限定僅在表尾進(jìn)行插入和刪除操作的線(xiàn)性表。這一端被稱(chēng)為棧頂，相對(duì)地，把另一端稱(chēng)為棧底。向一個(gè)棧插入新元素又稱(chēng)作進(jìn)棧、入棧或壓棧，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素；從一個(gè)棧刪除元素又稱(chēng)作出?；蛲藯?，它是把棧頂元素刪除掉，使其相鄰的元素成為新的棧頂元素。
棧可以類(lèi)比成現(xiàn)實(shí)生活中的彈夾或者羽毛球桶
二、用數(shù)組實(shí)現(xiàn)棧
用數(shù)組模擬棧的思路分析如圖：
1.定義一個(gè)top變量（指針）表示棧頂初始化為-1.
2.定義一個(gè)變量來(lái)記錄棧的大小。
3.入棧操作有數(shù)據(jù)加入到棧中：top++; arr[top]=value;
4.出棧操作： int value=arr[top]; top–; return value;
下面看完整代碼示例：
class Stack{
public int maxsize;//棧的大小
public int top=-1;//棧頂
public int[] arr;
public Stack(int maxsize) {
this.maxsize = maxsize;
arr=new int[maxsize];
}
//判斷棧是否為空
public boolean isEmpty(){
return top==-1;
}
//判斷棧是否滿(mǎn)
public boolean isFull(){
return top==maxsize-1;
}
//添加一個(gè)元素
public void push(int value){
if(isFull()){
throw new RuntimeException("棧滿(mǎn)");
}
top++;
arr[top]=value;
}
//彈出一個(gè)元素
public int pop(){
if(isEmpty())
throw new RuntimeException("?？?);
int value=arr[top];
top--;
return value;
}
//遍歷棧中的元素
public void traverse(){
if (isEmpty()){
return;
}
//需要從棧頂開(kāi)始顯示數(shù)據(jù)
for(int i = top; i >= 0 ; i--) {
System.out.printf("stack[%d]=%d
", i, arr[i]);
}
}
}
入棧操作 top++;arr[top]=value;其實(shí)可以直接改寫(xiě)為arr[++top]=value;
出棧操作可以將 int value=arr[top]; top–;return value;改為return arr[top–];
三、鏈表實(shí)現(xiàn)棧
思路分析：
入棧操作：用一個(gè)臨時(shí)節(jié)點(diǎn)保存當(dāng)前棧頂節(jié)點(diǎn)，將入棧的新節(jié)點(diǎn)作為棧頂元素，并將next域指向原來(lái)的舊節(jié)點(diǎn)。 Node temp=top; top.setNext(temp);
出棧操作：先判斷棧是否為空，不為空則將top節(jié)點(diǎn)的數(shù)據(jù)返回，并將top指向top的下一個(gè)next域：top=top.getNext();
public class LinkedListStack<V> {
static class Node<V>{
private V data;
private Node<V> next;
public V getData() {
return data;
}
public void setData(V data) {
this.data = data;
}
public Node<V> getNext() {
return next;
}
public void setNext(Node<V> next) {
this.next = next;
}
}
public int stackSize;//棧內(nèi)元素的個(gè)數(shù)
public Node<V> top;//棧頂元素
public LinkedListStack() {
stackSize = 0;
top = null;
}
//入棧
public void push(V element){
Node<V> temp=top;
top=new Node<>();
top.setData(element);
top.setNext(temp);
stackSize++;
}
//出棧
public V pop(){
if (isEmpty())
throw new RuntimeException("empty stack");
V value=top.getData();
//棧頂指向下一個(gè)元素
top=top.getNext();
stackSize--;
return value;
}
//查看棧頂元素
public V peek(){
return top.getData();
}
//判斷是否為空
public boolean isEmpty(){
return stackSize==0;
}
//查看棧內(nèi)元素個(gè)數(shù)
public int getStackSize(){
return stackSize;
}
}
四、測(cè)試
public class Test {
public static void main(String[] args) {
LinkedListStack<String> stack = new LinkedListStack<>();
stack.push("a");
stack.push("b");
stack.push("c");
System.out.println(stack.pop());
System.out.println(stack.peek());
System.out.println(stack.getStackSize());
}
}
測(cè)試結(jié)果:
c
b
2本篇關(guān)于使用Java數(shù)據(jù)和鏈表的形式分別模擬棧的實(shí)現(xiàn)的文章就介紹到這結(jié)束了，想要了解更多關(guān)于Java實(shí)現(xiàn)其他數(shù)據(jù)結(jié)構(gòu)的內(nèi)容，請(qǐng)多多關(guān)注W3Cschool相關(guān)內(nèi)容的文章，也希望大家可以多多支持我們！
