java.util.Stack#add ( )源码实例Demo

public static void bfs(boolean [][] visited, int x, int y, int [][] id, int idToFind, Set<Integer> neighbourIDs) {
	Stack<Coordinate> stk=new Stack<>();
	stk.push(new Coordinate(x,y));
	
	while (!stk.isEmpty()) {
		Coordinate c=stk.pop();
		visited[c.x][c.y]=true;
		for (int [] neighbour : neighbours) {
			int x1=c.x+neighbour[0];
			int y1=c.y+neighbour[1];
			if (x1>=0 && x1<visited.length && y1>=0 && y1<visited[0].length && !visited[x1][y1]) {
				if (id[x1][y1]!=idToFind) neighbourIDs.add(id[x1][y1]);
				else stk.add(new Coordinate(x1,y1));
			}
		}
	}
}
 

public static Stack<Point2D> convexHull(List<Point2D> points) {
    Stack<Point2D> solution = new Stack<Point2D>();
    Point2D[] pointsArray = new Point2D[points.size()];
    MergeSortByY.mergesort(points.toArray(pointsArray));
    Point2D point0 = pointsArray[0];
    Point2D[] pointsArrayExcept0 = Arrays.copyOfRange(pointsArray, 1, points.size());
    for (int i = 0; i < pointsArrayExcept0.length; i++) {
        pointsArrayExcept0[i].angleTo(point0);
    }
    solution.add(point0);
    MergeSortByPolarAngle.mergesort(pointsArrayExcept0);
    solution.add(pointsArrayExcept0[0]);
    for (int i = 1; i < pointsArrayExcept0.length; i++) {
        Point2D top = solution.pop();
        while (isCounterClockWise(pointsArrayExcept0[i], top, solution.peek()) <= 0) {
            top = solution.pop();
        }
        solution.add(top);
        solution.add(pointsArrayExcept0[i]);
    }
    return solution;
}
 

/**
 * 栈中销毁并移除所有Act对象
 */
public void removeAllActivity() {
    if (null != activityStack && activityStack.size() > 0) {
        //创建临时集合对象
        Stack<Activity> activityTemp = new Stack<>();
        for (Activity activity : activityStack) {
            if (null != activity) {
                //添加到临时集合中
                activityTemp.add(activity);
                //结束Activity
                activity.finish();
            }
        }
        activityStack.removeAll(activityTemp);
    }
    LogUtil.i("AppActivityTaskManager-->>removeAllActivity", "removeAllActivity");
    System.gc();
    System.exit(0);
}
 

/**
 * @param entryType type of interest
 * @return all types that are dependent on the entryType - deletion of which triggers possible retraction of inferences
 */
public static Set<Type> getDependentTypes(Type entryType){
    Set<Type> types = new HashSet<>();
    types.add(entryType);
    Set<Type> visitedTypes = new HashSet<>();
    Stack<Type> typeStack = new Stack<>();
    typeStack.add(entryType);
    while(!typeStack.isEmpty()) {
        Type type = typeStack.pop();
        if (!visitedTypes.contains(type) && type != null){
            type.whenRules()
                    .flatMap(Rule::thenTypes)
                    .peek(types::add)
                    .filter(at -> !visitedTypes.contains(at))
                    .forEach(typeStack::add);
            visitedTypes.add(type);
        }
    }
    return types;
}
 

private double maxdist()
{
    if(isLeaf())
        return 0;
    if(looseBounds)
        return pow(level+1);
    if (this.maxdist >= 0)
        return maxdist;
    //else, maxdist = -1, indicating we need to compute it
    Stack<TreeNode> toGetChildrenFrom = new Stack<>();
    toGetChildrenFrom.add(this);
    
    while(!toGetChildrenFrom.empty())
    {
        TreeNode runner = toGetChildrenFrom.pop();
        
        for(int q_indx = 0; q_indx < runner.numChildren(); q_indx++)
        {
            TreeNode q = runner.getChild(q_indx);
            maxdist = Math.max(maxdist, this.dist(q.vec_indx));//TODO can optimize for first set of childern, we already have that
            toGetChildrenFrom.add(q);
        }
    }
    
    return maxdist;
}
 

void DFS(int v)
{
    boolean visited[] = new boolean[V];

    Stack<Integer> stack = new Stack<Integer>();
    stack.add(v);

    visited[v] = true;

    while (!stack.isEmpty()) {
        int current = stack.pop();
        System.out.print(current + " ");

        Iterator<Integer> i = adj[current].listIterator();
        while (i.hasNext())
        {
            int n = i.next();
            if (!visited[n]) {
                stack.add(n);
                visited[n] = true;
            }
        }
    }
}
 

/**
 * Splits a string using the pattern specified, keeping the delimiters in between.
 *
 * @param text the text to split.
 * @param delimiterPattern the regex pattern to use as the delimiter.
 * @return a list of strings made up of the parts and their delimiters.
 */
private Stack<String> split(String text, String delimiterPattern) {

  if (text == null) {
    throw new IllegalArgumentException("You must supply some text to split");
  }

  if (delimiterPattern == null) {
    throw new IllegalArgumentException("You must supply a pattern to match on");
  }

  Pattern pattern = Pattern.compile(delimiterPattern);

  int lastMatch = 0;
  Stack<String> splitted = new Stack<>();

  Matcher m = pattern.matcher(text);

  // Iterate trough each match
  while (m.find()) {
    // Text since last match
    splitted.add(text.substring(lastMatch, m.start()));

    // The delimiter itself
    splitted.add(m.group());

    lastMatch = m.end();
  }

  // Trailing text
  splitted.add(text.substring(lastMatch));

  Collections.reverse(splitted);

  return splitted;
}
 

public void push(int data) {
    Stack current = getCurrentStack();
    if (current != null && current.size() < this.THRESHOLD) {
        current.add(data);
    } else {
        Stack newStack = new Stack();
        newStack.add(data);
        stacks.add(newStack);
    }
}
 

public static int scoreOfParentheses(String s) {
    int count = 0;
    Stack<Character> parentheses = new Stack<>();

    for (char c : s.toCharArray()) {
        if (c == '(') parentheses.add(c);
        else {
            count++;
            parentheses.pop();
        }
    }
    return count;
}
 

private CourseContactMessageUIModel configureContactUIModelWithOneContactLists() {
    ContactList aContactListMock = ObjectMother.createRecipientsContactList();

    Stack<ContactList> contactLists = new Stack<ContactList>();
    contactLists.add(aContactListMock);

    CourseContactMessageUIModel contactMessageUIModel = mock(CourseContactMessageUIModel.class);
    when(contactMessageUIModel.getContactLists()).thenReturn(contactLists);
    return contactMessageUIModel;
}
 

public static Unit getPostDominatorOfUnit(IInfoflowCFG cfg, Unit dataFlowStatement) {		
	Map<Unit, Set<ControlFlowPath>> controlFlowPathsAtUnit = new HashMap<Unit, Set<ControlFlowPath>>();
	Set<ControlFlowPath> currentPaths = new HashSet<ControlFlowPath>();
	Stack<Unit> worklist = new Stack<Unit>();
	worklist.add(dataFlowStatement);	

	while(!worklist.isEmpty()) {
		Unit currentUnit = worklist.pop();
		
		if(currentUnit.hasTag(InstrumentedCodeTag.name)) {
			List<Unit> successors = cfg.getSuccsOf(currentUnit);
			
			for(Unit nextUnit : successors) {
				if(proceedWithNextUnit(currentUnit, nextUnit, currentPaths, controlFlowPathsAtUnit)) {
					worklist.push(nextUnit);				
				}
			}
			continue;
		}
		
		SootMethod currentMethod = cfg.getMethodOf(currentUnit);
		
		//this is a kind of hack: We excluded exception-edges here and also keep in mind that ALL dominator-algorithms are intra-procedural
		MHGPostDominatorsFinder<Unit> postdominatorFinder = new MHGPostDominatorsFinder<Unit>(new BriefUnitGraph(currentMethod.retrieveActiveBody()));
		Unit immediatePostDominator = postdominatorFinder.getImmediateDominator(currentUnit);
		while(immediatePostDominator.hasTag(InstrumentedCodeTag.name)) {
			immediatePostDominator = postdominatorFinder.getImmediateDominator(immediatePostDominator);
		}
		return immediatePostDominator;
	}	
	return null;
}
 

/**
 * Set prepared access-context on thread.
 * @param accessContext The context of DB access. (NotNull)
 */
public static void setAccessContextOnThread(AccessContext accessContext) {
    if (accessContext == null) {
        String msg = "The argument[accessContext] must not be null.";
        throw new IllegalArgumentException(msg);
    }
    Stack<AccessContext> stack = threadLocal.get();
    if (stack == null) {
        stack = new Stack<AccessContext>();
        threadLocal.set(stack);
    }
    stack.add(accessContext);
}
 

/**
 * Iterative algorithm to solve this problem. The key of this algorithm is to use two pointers to
 * go just through the fifty percent of the list. Using a fast pointer we can create an stack to
 * generate a reversed list and then check if both lists are equals or not. The complexity order
 * of this algorithm is the same than the previous one in time and space terms but the execution
 * time is faster because we are just checking half of the list.
 */
public boolean checkIterative(ListNode list) {
  validateInput(list);

  Stack<ListNode> stack = new Stack<ListNode>();
  ListNode fastPointer = list;
  ListNode slowPointer = list;
  while (fastPointer != null && fastPointer.getNext() != null) {
    stack.add(slowPointer);
    slowPointer = slowPointer.getNext();
    fastPointer = fastPointer.getNext().getNext();
  }

  if (fastPointer != null) {
    slowPointer = slowPointer.getNext();
  }

  boolean isPalindrome = true;
  while (slowPointer != null) {
    if (!stack.pop().equals(slowPointer)) {
      isPalindrome = false;
      break;
    }
    slowPointer = slowPointer.getNext();
  }
  return isPalindrome;
}
 

public List<Integer> postorderTraversal(TreeNode root) {
    LinkedList<Integer> postOrderList = new LinkedList<>();

    if (root == null) return postOrderList;
    Stack<TreeNode> nodeStack = new Stack<>();
    nodeStack.add(root);

    while (!nodeStack.isEmpty()) {
        TreeNode top = nodeStack.pop();
        postOrderList.addFirst(top.val);
        if (top.left != null) nodeStack.push(top.left);
        if (top.right != null) nodeStack.push(top.right);
    }
    return postOrderList;
}
 

/**
 * The solution is simple, every node (except the root) on the left of the tree would have its parent's right child
 * as it's left child and parent as its right child. That's all you have to do to flip the tree upside down.
 *
 * Time Complexity: O(h)
 * Space Complexity: O(h)
 * where,
 * h = height of the tree
 *
 * Runtime: <a href="https://leetcode.com/submissions/detail/248816514/">1 ms</a>.
 *
 * @param root
 * @return
 */
public static TreeNode upsideDownBinaryTreeUsingStack(TreeNode root) {
    if (root == null) return null;

    TreeNode curr = root;
    TreeNode currParent;
    TreeNode newRoot = null;

    // using stack to keep track of the parent node
    Stack<TreeNode> stack = new Stack<>();

    while (curr != null) {
        stack.add(curr);
        curr = curr.left;
    }

    while (!stack.empty()) {
        curr = stack.pop();
        currParent = stack.empty() ? null : stack.peek();

        if (newRoot == null) newRoot = curr;

        if (currParent != null) {
            curr.left = currParent.right;
            curr.right = currParent;
        } else {
            curr.left = null;
            curr.right = null;
        }
    }

    return newRoot;
}
 

private MavlinkDef nextDefinitionLeaf(
        Stack<String> stack,
        List<MavlinkDef> work,
        List<MavlinkDef> sorted,
        MavlinkDef current) {
    if (stack.contains(current.getName())) {
        int lastCall = stack.lastIndexOf(current.getName());
        String cycle = stack.subList(lastCall, stack.size())
                .stream()
                .collect(Collectors.joining(" -> ", "", " -> " + current.getName()));
        throw new IllegalStateException(
                "Cyclic dependencies for " + current.getName() + ", cycle is: \n" + cycle);
    }
    stack.add(current.getName());
    List<String> unmetDependencies = current.getIncludes()
            .stream()
            .filter(s -> sorted.stream()
                    .map(MavlinkDef::getName)
                    .filter(s::equals)
                    .count() == 0)
            .collect(Collectors.toList());
    if (unmetDependencies.size() > 0) {
        String dependencyName = unmetDependencies.get(0);
        MavlinkDef dependency = work.stream()
                .filter(md -> dependencyName.equals(md.getName()))
                .findFirst()
                .orElseThrow(() -> new IllegalStateException(
                        current.getName() + " depends on " + dependencyName + " but such dialect does not exist."));
        return nextDefinitionLeaf(stack, work, sorted, dependency);
    }
    return current;
}
 

public List<Integer> addToArrayForm(int[] A, int K) {
    int len = A.length;
    Stack<Integer> stack = new Stack<>();
    int i = len - 1;
    int curSum;
    int carry = 0;
    while (i >= 0 || K > 0) {
        curSum = carry;
        if (i >= 0) {
            curSum += A[i];
            i--;
        }
        if (K > 0) {
            curSum += K % 10;
            K /= 10;
        }
        if (curSum >= 10) {
            curSum -= 10;
            carry = 1;
        } else {
            carry = 0;
        }
        stack.add(curSum);
    }
    if (carry == 1) {
        stack.add(1);
    }
    List<Integer> res = new ArrayList<>();
    while (!stack.empty()) {
        res.add(stack.pop());
    }
    return res;
}
 

public List<List<Integer>> levelOrderBottom(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) {
        return res;
    }
    Stack<List<Integer>> stack = new Stack<>();
    LinkedList<TreeNode> queue = new LinkedList<>();
    queue.addLast(root);

    while (!queue.isEmpty()){
        int size = queue.size();
        List<Integer> curLevel = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.removeFirst();
            curLevel.add(node.val);
            if(node.left!=null){
                queue.addLast(node.left);
            }
            if(node.right!=null){
                queue.addLast(node.right);
            }
        }
        stack.add(curLevel);
    }

    while (!stack.empty()){
        res.add(stack.pop());
    }
    return res;
}
 

/**
 * 注意这个 dfs 方法的语义
 *
 * @param i      当前访问的课程结点
 * @param graph
 * @param marked 如果 == 1 表示正在访问中，如果 == 2 表示已经访问完了
 * @return true 表示图中存在环，false 表示访问过了，不用再访问了
 */
private boolean dfs(int i,
                    HashSet<Integer>[] graph,
                    int[] marked,
                    Stack<Integer> stack) {
    // 如果访问过了，就不用再访问了
    if (marked[i] == 1) {
        // 从正在访问中，到正在访问中，表示遇到了环
        return true;
    }
    if (marked[i] == 2) {
        // 表示在访问的过程中没有遇到环，这个节点访问过了
        return false;
    }
    // 走到这里，是因为初始化呢，此时 marked[i] == 0
    // 表示正在访问中
    marked[i] = 1;
    // 后继结点的集合
    HashSet<Integer> successorNodes = graph[i];
    for (Integer successor : successorNodes) {
        if (dfs(successor, graph, marked, stack)) {
            // 层层递归返回 true ，表示图中存在环
            return true;
        }
    }
    // i 的所有后继结点都访问完了，都没有存在环，则这个结点就可以被标记为已经访问结束
    // 状态设置为 2
    marked[i] = 2;
    stack.add(i);
    // false 表示图中不存在环
    return false;
}
 

HyperGraph convert(String inputStr) {

    HyperGraph tree = null;

    Stack<String> stack = new Stack<>();
    for (int i = 0; i < inputStr.length(); i++) {
      char curChar = inputStr.charAt(i);

      if (curChar == ')' && inputStr.charAt(i - 1) != ' ') {// end of a rule
        StringBuffer ruleString = new StringBuffer();

        label:
        while (stack.empty() == false) {
          String cur = stack.pop();
          switch (cur) {
          case beginSymbol: // stop
            // setup a node
            // HGNode(int i, int j, int lhs, HashMap<Integer,DPState> dpStates, HyperEdge
            // initHyperedge, double estTotalLogP)
            // public HyperEdge(Rule rule, double bestDerivationLogP, Double transitionLogP,
            // List<HGNode> antNodes, SourcePath srcPath)
            // public Rule(int lhs, int[] sourceRhs, int[] targetRhs, float[]
            // featureScores, int arity, int owner, float latticeCost, int ruleID)

            stack.add(nodeSymbol);// TODO: should be lHS+id

            break label;
          case nodeSymbol:

            break;
          default:
            ruleString.append(cur);
            break;
          }
        }
      } else if (curChar == '(' && inputStr.charAt(i + 1) != ' ') {// begin of a rule
        stack.add(beginSymbol);
      } else {
        stack.add("" + curChar);
      }
    }



    return tree;
  }