算法1.2下压堆栈（链表实现）

算法1.2下压堆栈（链表实现）

《算法》笔记导航

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

public class Stack<Item> implements Iterable<Item>

栈：先入后出，入栈出栈都是对栈顶的节点进行操作
链表：一列元素

一、变量，方法，类及其作用

1.变量

• private Node first
  以链表Node实现的栈顶
• private int N
  保存元素数量

2.方法

2.1 对栈的操作

• public void push(Item item);
  入栈，通过创建新子节点，并将新子节点的next指向原有first子节点实现
• public Item pop()
  出栈，通过将first节点指向first的next实现，返回值为原first节点的元素值

2.2 对栈的检测

• public boolean isEmpty()
  检测栈是否为空
• public int size()
  检测栈大小

2.3 可迭代的集合数据类型中需要实现的东西

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

3.类

3.1 链表

• private class Node
  链表的一个节点
  Item item
  储存泛型（任意类型，在实例化对象时指定）元素。
  Node next
  指向下一个节点的安全指针（不会出现溢出），通过对next的访问可以进入下一个节点

3.2 迭代器

• private class LisIterator implements Iterator<Item>
  支持后进先出的迭代，方法iterator()返回的就是这个类。
  private Node current=first
  当前节点，用于迭代，可通过访问current的next指向下一个节点
  public boolean hasNext()
  是否进行下一次的迭代（是否还有下一个元素），通过判断当前节点current是否为null来实现。（因为在使用next()方法后，current已经指向了当前节点的next，所以迭代的最后一个，不是它的next节点是null，而是它本身是null）
  publi Item next()
  访问下一个元素，通过访问当前节点current的next指向下一个节点实现
  public void remove()
  用于删除元素，会破坏数据结构（栈），需要声明，但是不予实现。

二、算法的实现

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函数

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.输入的数据

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

3.输出的数据

cbdaghf

渣渣菜鸡，难免错误，请友善讨论
非商用转载需注明作者及文章链接来源，私信告知后无需我回复即可直接转载