單向連結清單實作棧
首先我們要知道"棧"為何物 , 他是一種儲存資料的方法 , 有點類似子彈夾 , 擁有先進後出的特點 . 同時進棧與出棧都隻能在一端進行.
1,建立MyStack接口用來定義方法
public interface MyStack {
boolean isEmpty(); //判斷是否為空
boolean pash(Object x); //入棧
Object pop(); //出棧
Object getTop(); //獲得棧頂元素
}
2,建立連結清單實作就必須的Node節點類
public class Node {
private Object date; //存儲元素
private Node next; //下一個指針對象
public Node(Object x) {
this.date=x;
this.next=null;
}
public Object getDate() {
return date;
}
public void setDate(Object date) {
this.date = date;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
3,建立MyStack接口的實作類MyStackLiked
1,建立兩個屬性一個用來作為記錄有效個數的size , 還有一個用來作為指針的Node對象top
private Node top;
private int size;
2,pash方法
這是一個添加的方法也叫入棧
public boolean pash(Object x) {
Node newNode = new Node(x);
newNode.setNext(top);
top=newNode;
size++;
return true;
}
1,建立一個Node對象newNode用來存儲要插入的元素
2,将top所指向的資料拼接在newNode的後面 , 這樣一來我們就成功的吧新元素newNode給連接配接進來棧了
3,因為我們添加了新元素進來是以棧頂元素變成了newNode , 但是top每一次都是指向棧頂元素是以我們需要将top的元素更換 , 這時我們的top=newNode就可以滿足 , 将top的元素變為了newNode
4,有效個數size++;
話不多說直接上圖
3,pop方法
這是一個出棧方法
public Object pop() {
Object date = top.getDate();
top=top.getNext();
this.size--;
return date;
}
1,因為棧的特性隻允許從棧頂出來 , 而且是先進後出 . 是以我們隻能從棧頂出棧 , 又因為top指向棧頂元素是以我們就直接通過top.getDate方法獲得棧頂元素的值
2,因為top指向的元素要出棧 , 是以我們需要調整top的指針指向 , 直接将top的下以為指派給top讓他達到top重指向的效果
3,有效元素個數size–;
4,isEmpty方法
public boolean isEmpty() {
return size==0;
}
這個方法沒啥好說的直接讓size和0作比較
5,getTop方法
public Object getTop() {
Object object=top.getDate();
return object;
}
這個方法也沒啥好說的跟pop方法一樣但是不用删除元素是以直接傳回值就好了
小結
連結清單實作棧的操作其實并不難我們如果掌握了連結清單的隻是就能很容易的寫出來 , 如果單向連結清單不是很熟練的可以看一下這個部落格還很詳細
好說的跟pop方法一樣但是不用删除元素是以直接傳回值就好了**
小結
連結清單實作棧的操作其實并不難我們如果掌握了連結清單的隻是就能很容易的寫出來 , 如果單向連結清單不是很熟練的可以看一下這個部落格還很詳細
https://blog.csdn.net/qq_46487100/article/details/108941571