算法1.2下壓堆棧（鏈表實(shí)現(xiàn)）

《算法》筆記導(dǎo)航

《算法》中文第四版P94
2020.7.3
@Stream_

public class Stack<Item> implements Iterable<Item>

棧：先入后出，入棧出棧都是對棧頂?shù)墓?jié)點(diǎn)進(jìn)行操作
鏈表：一列元素

一、變量，方法，類及其作用

1.變量

• private Node first
  以鏈表Node實(shí)現(xiàn)的棧頂
• private int N
  保存元素?cái)?shù)量

2.方法

2.1 對棧的操作

• public void push(Item item);
  入棧，通過創(chuàng)建新子節(jié)點(diǎn)，并將新子節(jié)點(diǎn)的next指向原有first子節(jié)點(diǎn)實(shí)現(xiàn)
• public Item pop()
  出棧，通過將first節(jié)點(diǎn)指向first的next實(shí)現(xiàn)，返回值為原first節(jié)點(diǎn)的元素值

2.2 對棧的檢測

• public boolean isEmpty()
  檢測棧是否為空
• public int size()
  檢測棧大小

2.3 可迭代的集合數(shù)據(jù)類型中需要實(shí)現(xiàn)的東西

• public Iterator<Item> iterator()
  返回一個Iterator的泛型，用于迭代

3.類

3.1 鏈表

• private class Node
  鏈表的一個節(jié)點(diǎn)
  Item item
  儲存泛型（任意類型，在實(shí)例化對象時指定）元素。
  Node next
  指向下一個節(jié)點(diǎn)的安全指針（不會出現(xiàn)溢出），通過對next的訪問可以進(jìn)入下一個節(jié)點(diǎn)

3.2 迭代器

• private class LisIterator implements Iterator<Item>
  支持后進(jìn)先出的迭代，方法iterator()返回的就是這個類。
  private Node current=first
  當(dāng)前節(jié)點(diǎn)，用于迭代，可通過訪問current的next指向下一個節(jié)點(diǎn)
  public boolean hasNext()
  是否進(jìn)行下一次的迭代（是否還有下一個元素），通過判斷當(dāng)前節(jié)點(diǎn)current是否為null來實(shí)現(xiàn)。（因?yàn)樵谑褂胣ext()方法后，current已經(jīng)指向了當(dāng)前節(jié)點(diǎn)的next，所以迭代的最后一個，不是它的next節(jié)點(diǎn)是null，而是它本身是null）
  publi Item next()
  訪問下一個元素，通過訪問當(dāng)前節(jié)點(diǎn)current的next指向下一個節(jié)點(diǎn)實(shí)現(xiàn)
  public void remove()
  用于刪除元素，會破壞數(shù)據(jù)結(jié)構(gòu)（棧），需要聲明，但是不予實(shí)現(xiàn)。

二、算法的實(shí)現(xiàn)

import  java.util.Iterator;

public class Stack<Item> implements  Iterable<Item>{
    private Node first;
    private int N;

    private class Node{
        Item item;
        Node next;
    }

    public void push(Item item){
        Node oldfirst=first;
        first = new Node();
        first.item=item;
        first.next=oldfirst;
        N++;
    }
    public Item pop(){
        Item item=first.item;
        first=first.next;
        N--;
        return item;
    }

    public boolean isEmpty(){
        return N==0;
    }
    public int size(){
        return N;
    }

    public Iterator<Item> iterator(){
        return new ListIterator();
    }
    private class ListIterator implements Iterator<Item> {
        private Node current=first;
        public boolean hasNext(){
            return current!=null;
        }
        public Item next(){
            Item item=current.item;
            current=current.next;
            return item;
        }
    }
}

三、算法的使用

1.main函數(shù)

import java.util.Scanner;

public class tets02 {
    public static void main(String[] args) {
        Stack<Character> stack=new Stack<Character>();                 //必須是包裝類，不能是原始類型（byte-Byte,short-Short,int-Interger,long-Long,float-Float,double-Double,char-Character,boolean-Boolean）。

        Scanner sc=new Scanner(System.in);
        String line=sc.nextLine();
        sc.useDelimiter("\n");     //不以空格為分隔符停止輸入

        int length=line.length();
        for(int i=0;i<length;i++){
            if(line.charAt(i)!='-'&&line.charAt(i)!=' '){
                stack.push(line.charAt(i));
            }
            else if(line.charAt(i)=='-'&&!stack.isEmpty()){
                System.out.println(stack.pop());
            }
        }
    }
}

2.輸入的數(shù)據(jù)

abc--d--efg-h--i

3.輸出的數(shù)據(jù)

cbdaghf

渣渣菜雞，難免錯誤，請友善討論
非商用轉(zhuǎn)載需注明作者及文章鏈接來源，私信告知后無需我回復(fù)即可直接轉(zhuǎn)載