package com.arithmetic;import com.Util.StdIn;
import com.Util.StdOut;import java.util.Iterator;
import java.util.NoSuchElementException;/*** 栈* 链表实现*/
public class Stack<Item> implements Iteratable<Item> {private Node<Item> first;// 结点数量private int n;// 结点表示private static class Node<Item> {private Item item;private Node<Item> next;}Stack() {first = null;n = 0;}void push(Item item) {Node node = new Node();node.item = item;node.next = first;first = node;n++;}Item pop() {if (isEmpty()) {if (isEmpty()) throw new NoSuchElementException("Stack underflow");}Item item = first.item;first = first.next;n--;return item;}int size() {return n;}// 返回栈顶元素但不移除它Item peek() {return first.item;}boolean isEmpty() {return first == null;}// 接受一个链表和一个字符串key为参数,如果链表中的某个节点的item域的值为key,返回true,否则返回folseboolean find(Stack<Item> stack, String key) {if (stack == null) {return false;} Iterator<Item> iterator = stack.iterator();while (iterator.hasNext()) {Item value = iterator.next();if (value.equals(key)) {return true;}}return false;}// 实现迭代@Overridepublic Iterator<Item> iterator() {return new ListIterator<Item>(first);}private class ListIterator<Item> implements Iterator<Item> {private Node<Item> current;public ListIterator(Node<Item> first) {current = first;}@Overridepublic boolean hasNext() {return current != null;}@Overridepublic Item next() {if (!hasNext()) throw new NoSuchElementException();Item item = current.item;current = current.next;return item;}@Overridepublic void remove() {throw new UnsupportedOperationException();}}public static void main(String[] args) {Stack<String> stack = new Stack<String>();stack.push("1");stack.push("2");stack.push("3");Iterator<String> iterator = stack.iterator();while (iterator.hasNext()) {String value = iterator.next();System.out.println(value);}System.out.println(stack.find(stack, "5"));System.out.println(stack.find(stack, "3"));}
}