java版棧和隊列之數(shù)組和鏈表實現(xiàn)(實現(xiàn)Iterable可迭代版)

本章內(nèi)容主要來自算法(第四版) Robert Sedgewick著 1.3小節(jié)

棧(后進先出)的基本功能

public class Stack<Item> implements Iterable<Item>{
   Stack()
   void push(Item)
   Item pop()
   boolean isEmpty()
   int size()
}

隊列(先進先出):

public class Queue<Item> implements Iterable<Item>{
    Queue()
    void enqueue(Item item)
    Item deque()
    boolean isEmpty()
    int size()
}

關于Iterable和Iterator:

interface　　　　　　method
java.lang.Iterable => iterator()
java.util.Iterator => hasNext()贾费、next()屹徘、remove()

foreach實質(zhì)

  Stack<String> collection = new Stack<String>();
  ...
  for(String s : collection){
      System.out.println(s);
  }
  ...
  等價于如下代碼=======================================
  Iterator<String> i = collection.iterator();
  while(i.hasNext()){
      System.out.println(i.next());
  }

所以實現(xiàn)Iterable需實現(xiàn)Iterator()方法，返回的是實現(xiàn)java.util.Iterator接口的內(nèi)部類對象留美，注意內(nèi)部類可以訪問外部類實例域
數(shù)組沒有實現(xiàn)該接口也能使用foreach涮因，留待后答

數(shù)組版棧實現(xiàn)

import java.util.Iterator;

public class Test {
    public static void main(String[] args) {

    }
}
//未重寫toString()等方法
class Stack<T> implements Iterable<T>{
    private int N =0;
    private T[] t;
    public Stack() {
        t = (T[])new Object[8];   //此處將默認設為8
    }
    public Stack(int length) {
        t = (T[])new Object[length];   //此處將默認設為8
    }
    private void resize(int length) {
        //將棧移動到一個長度為length的新數(shù)組
        T[] temp = (T[])new Object[length];
        for(int i=0;i<N;i++) {
            temp[i] = t[i];
        }
        t = temp;
    }
    public void push(T element) {
        if(N==t.length) {
            resize(2*t.length+2);
        }
        t[N++] = element;
    }
    public T pop() {
        T a = null;
        if(N>0){
            a=t[--N];
            t[N]=null;
            if(N>8&&N<t.length/4){
                resize(t.length/2);
            }
        }
        return a;
            
        
    }
    public boolean isEmpty() {
        return N==0;
    }
    public int size() {
        return N;
    }
    @Override
    public Iterator<T> iterator() {
        return new ReverseArrayIterator();
    }
    //JDK 1.8不用覆蓋remove()方法了
    private class ReverseArrayIterator implements Iterator<T>{
        private int i = N;
        @Override
        public boolean hasNext() {
            return i > 0;
        }
        @Override
        public T next() {
            return t[--i];
        }
    }
}

鏈表版棧實現(xiàn)

class Stack<T> implements Iterable<T>{
    private Node first;
    private int N;
    private class Node{
        T element;
        Node next;
    }
    public boolean isEmpty(){
        return N==0;
    }
    public int size(){
        return N;
    }
    public void push(T element){
        Node oldfirst = first;
        first = new Node();
        first.element = element;
        first.next = oldfirst;
        N++;
    }
    public T pop(){
        //未顯示考慮棧為空的狀態(tài)
        T element = first.element;
        first = first.next;
        N--;
        return element;
    }
    @Override
    public Iterator<T> iterator() {
        return new ListIterator();
    }
    private class ListIterator implements Iterator<T>{
        private Node current = first;
        @Override
        public boolean hasNext() {
            return current != null;
        }

        @Override
        public T next() {
            T element = current.element;
            current = current.next;
            return element;
        }
        
    }
}

數(shù)組版隊列實現(xiàn)

import java.util.Iterator;

public class Test {
    public static void main(String[] args) {

    }
}
//循環(huán)列表
class Queue<T> implements Iterable<T>{
    private int head;
    private int tail;
    private int N;
    T[] t;
    public Queue(){
        N = 0;
        head = 0;
        tail = 0;
        t = (T[])new Object[8];
    }
    public Queue(int length){
        N = 0;
        head = 0;
        tail = 0;
        t = (T[])new Object[length];
    }
    public void enqueue(T element){
        if(N<t.length){
            if(N==0){
                t[head]=element;
            }
            else{
                tail = (++tail) % t.length;
                t[tail] = element;
            }
            N++;
        }
        else{
            //隊列已滿
        }
    }
    public void dequeue(){
        if(N>0){
            //N=1說明首尾指向同一位
            if(N==1){
                t[head]=null;
                N--;
            }
            else{
                //為null防止對象游離
                t[head]=null;
                head = (++head)%t.length;
                N--;
            }
        }
        else{
            //隊列為空
        }
    }
    public int size(){
        return N;
        
    }
    
    @Override
    public Iterator<T> iterator() {
        return new FirstinfirstoutArrayIterator();
    }
    private class FirstinfirstoutArrayIterator implements Iterator<T>{
        private int i = 0;
        @Override
        public boolean hasNext() {
            return i < N;
        }
        @Override
        public T next() {
            T element = t[(i+head)%t.length];    //從頭元素開始獲取元素.
            i++;
            return element;
        }
    }
}

鏈表版隊列實現(xiàn)

import java.util.Iterator;

public class Test {
    public static void main(String[] args) {

    }
}
class Queue<T> implements Iterable<T>{
    private Node first;
    private Node last;
    private int N;
    private class Node{
        T element;
        Node next;
    }
    public boolean isEmpty(){
        return first == null;
    }
    public int size(){
        return N;
    }
    public void enqueue(T element){
        Node oldlast = last;
        last = new Node();
        last.element = element;
        last.next = null;
        if(isEmpty()) first = last;
        else oldlast.next = last;
        N++;
    }
    public T dequeue(){
        if(isEmpty()){
            first = null;
            last = null;
            return null;
        }
        T element = first.element;
        first = first.next;
        N--;
        if(N==0){
            first = null;
            last = null;
        }
        return element;
    }
    @Override
    public Iterator<T> iterator() {
        return new ListIterator();
    }
    private class ListIterator implements Iterator<T>{
        private Node current = first;
        @Override
        public boolean hasNext() {
            return current != null;
        }

        @Override
        public T next() {
            T element = current.element;
            current = current.next;
            return element;
        }
        
    }
}

java中不允許泛型數(shù)組拒迅，需要類型轉換例如 a=(Type[])new Object[N]

最后編輯于 ：
?著作權歸作者所有,轉載或內(nèi)容合作請聯(lián)系作者
  • 人面猴
    序言：七十年代末沥寥，一起剝皮案震驚了整個濱河市，隨后出現(xiàn)的幾起案子既忆，更是在濱河造成了極大的恐慌驱负，老刑警劉巖，帶你破解...
    沈念sama閱讀 218,122評論 6贊 505
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件患雇，死亡現(xiàn)場離奇詭異跃脊，居然都是意外死亡，警方通過查閱死者的電腦和手機苛吱，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 93,070評論 3贊 395
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進店門匾乓，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人又谋，你說我怎么就攤上這事拼缝。” “怎么了彰亥？”我有些...
    開封第一講書人閱讀 164,491評論 0贊 354
  • 道士緝兇錄：失蹤的賣姜人
    文/不壞的土叔 我叫張陵咧七，是天一觀的道長。 經(jīng)常有香客問我任斋，道長继阻，這世上最難降的妖魔是什么？ 我笑而不...
    開封第一講書人閱讀 58,636評論 1贊 293
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任废酷，我火速辦了婚禮瘟檩，結果婚禮上，老公的妹妹穿的比我還像新娘澈蟆。我一直安慰自己墨辛，他們只是感情好，可當我...
    茶點故事閱讀 67,676評論 6贊 392
  • 惡毒庶女頂嫁案：這布局不是一般人想出來的
    文/花漫 我一把揭開白布趴俘。 她就那樣靜靜地躺著睹簇，像睡著了一般。 火紅的嫁衣襯著肌膚如雪寥闪。 梳的紋絲不亂的頭發(fā)上太惠，一...
    開封第一講書人閱讀 51,541評論 1贊 305
  • 城市分裂傳說
    那天，我揣著相機與錄音疲憋，去河邊找鬼凿渊。 笑死，一個胖子當著我的面吹牛缚柳，可吹牛的內(nèi)容都是我干的埃脏。 我是一名探鬼主播，決...
    沈念sama閱讀 40,292評論 3贊 418
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開眼喂击，長吁一口氣：“原來是場噩夢啊……” “哼剂癌！你這毒婦竟也來了？” 一聲冷哼從身側響起翰绊，我...
    開封第一講書人閱讀 39,211評論 0贊 276
  • 萬榮殺人案實錄
    序言：老撾萬榮一對情侶失蹤佩谷，失蹤者是張志新（化名）和其女友劉穎，沒想到半個月后监嗜，有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體谐檀，經(jīng)...
    沈念sama閱讀 45,655評論 1贊 314
  • ?護林員之死
    正文 獨居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 37,846評論 3贊 336
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年裁奇，在試婚紗的時候發(fā)現(xiàn)自己被綠了桐猬。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點故事閱讀 39,965評論 1贊 348
  • 活死人
    序言：一個原本活蹦亂跳的男人離奇死亡刽肠，死狀恐怖溃肪，靈堂內(nèi)的尸體忽然破棺而出免胃，到底是詐尸還是另有隱情，我是刑警寧澤惫撰，帶...
    沈念sama閱讀 35,684評論 5贊 347
  • ?日本核電站爆炸內(nèi)幕
    正文 年R本政府宣布羔沙，位于F島的核電站，受9級特大地震影響厨钻，放射性物質(zhì)發(fā)生泄漏扼雏。R本人自食惡果不足惜，卻給世界環(huán)境...
    茶點故事閱讀 41,295評論 3贊 329
  • 男人毒藥：我在死后第九天來索命
    文/蒙蒙 一夯膀、第九天 我趴在偏房一處隱蔽的房頂上張望诗充。 院中可真熱鬧，春花似錦诱建、人聲如沸蝴蜓。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,894評論 0贊 22
  • 一樁弒父案涂佃，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽励翼。三九已至，卻和暖如春辜荠，著一層夾襖步出監(jiān)牢的瞬間汽抚，已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,012評論 1贊 269
  • 情欲美人皮
    我被黑心中介騙來泰國打工伯病， 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留造烁，地道東北人。 一個月前我還...
    沈念sama閱讀 48,126評論 3贊 370
  • 代替公主和親
    正文 我出身青樓午笛，卻偏偏與公主長得像惭蟋，于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子药磺，可洞房花燭夜當晚...
    茶點故事閱讀 44,914評論 2贊 355