下面列出了java.util.Stack#empty ( ) 实例代码,或者点击链接到github查看源代码,也可以在右侧发表评论。
/**
* Get the dependencies (transitively) of the given parent element.
*
* @param scope the scope to use for the parent.
* @param parent the parent dependency.
* @return a collection of all dependencies of the given parent.
*/
private static Set<DependencyDescriptor> getDependenciesTransitively(String scope, ResolvedDependency parent) {
Stack<ResolvedDependency> stack = new Stack<>();
stack.push(parent);
Set<DependencyDescriptor> dependencies = new HashSet<>();
while (!stack.empty()) {
ResolvedDependency rd = stack.pop();
// Skip the parent's artifacts.
if (rd != parent) {
rd.getModuleArtifacts().forEach(a -> dependencies.add(asDescriptor(scope, a)));
}
rd.getChildren().forEach(d -> {
if (!stack.contains(d)) {
stack.add(d);
}
});
}
return dependencies;
}
/** Preorder traversal from a subtree without using recursion */
protected void preorder(TreeNode<E> root) {
if (root == null) return;
Stack<TreeNode<E>> stack = new Stack<>();
stack.push(root);
while (!stack.empty()) {
TreeNode<E> node = stack.pop();
System.out.print(node.element + " ");
// Push the right child onto the stack
// first so the left isgit processed first
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
}
/**
* Including super class fields.
*/
List<VariableElement> getAllFields(TypeElement subclazz) {
List<VariableElement> fields = new ArrayList<VariableElement>();
TypeElement cd = null;
Stack<TypeElement> s = new Stack<TypeElement>();
cd = subclazz;
while (true) {
s.push(cd);
TypeElement c = (TypeElement) (types.asElement(cd.getSuperclass()));
if (c == null)
break;
cd = c;
}
while (!s.empty()) {
cd = s.pop();
fields.addAll(ElementFilter.fieldsIn(cd.getEnclosedElements()));
}
return fields;
}
private void checkValidity(Editable s) {
String s1 = s.toString();
Stack stackCheck = new Stack();
char[] valid = s1.toCharArray();
for (char c : valid) {
if (c == '{' || c == '(') {
stackCheck.push((c));
}
if (c == '}' || c == ')') {
if (stackCheck.empty()) {
Toast.makeText(getContext(), "Your Code Has Invalid Parenthesis", Toast.LENGTH_LONG).show();
return;
} else {
if (!matchPair((char) stackCheck.peek(), c)) {
Toast.makeText(getContext(), "Your Code Has Invalid Parenthesis", Toast.LENGTH_LONG).show();
return;
}
stackCheck.pop();
}
}
}
if(stackCheck.size() ==1 ){
Toast.makeText(getContext(), "Unmatched Parenthesis", Toast.LENGTH_LONG).show();
}
}
public int[] exclusiveTime(int n, List<String> logs) {
Stack<int[]> stack = new Stack<>();
Stack<Integer> interval = new Stack<>();
int result[] = new int[n];
for (String log : logs) {
String[] tmp = log.split(":");
if (tmp[1].equals("start")) {
stack.add(new int[]{Integer.valueOf(tmp[0]), Integer.valueOf(tmp[2])});
interval.add(0);
} else {
int[] last = stack.pop();
result[last[0]] += Integer.valueOf(tmp[2]) - last[1] - interval.pop() + 1;
if (!interval.empty()) {
interval.add(interval.pop() + Integer.valueOf(tmp[2]) - last[1] + 1);
}
}
}
return result;
}
/**
* 中序遍历
* @param root
*/
public void inOrder(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
if (root == null) {
return;
}
TreeNode currentNode = root;
while (currentNode != null || !stack.empty()) {
while (currentNode != null) {
stack.push(currentNode);
currentNode = currentNode.left;
}
if (!stack.empty()) {
currentNode = stack.pop();
System.out.print(currentNode.val + " ");
currentNode = currentNode.right;
}
}
}
/**
* @param item
* @return
*/
public List<ListItem> convert2list()
{
List<ListItem> list = new ArrayList<ListItem>();
Stack<ListItem> processStack = new Stack<ListItem>();
processStack.push(this);
while(! processStack.empty())
{
ListItem parent = processStack.pop();
list.add(parent);
List<ListItem> children = parent.getMembers();
if(children != null)
{
for(int i = children.size() - 1; i >= 0; i--)
{
ListItem child = children.get(i);
processStack.push(child);
}
}
}
return list;
}
private static int pop() {
Stack<Integer> lastStack = stackList.get(stackList.size() - 1);
if (lastStack == null || (stackList.size() == 1 && lastStack.empty())) {
throw new EmptyStackException();
} else if (lastStack.empty()) {
stackList.remove(stackList.size() - 1);
return pop();
} else {
return lastStack.pop();
}
}
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;
}
/**
* Associates the specified value with the specified key in this map
* (optional operation).
*
* @param key key with which the specified value is to be associated.
* @param value value to be associated with the specified key.
* @return previous value associated with specified key, or
* <tt>null</tt> if there was no mapping for key. A <tt>null</tt>
* return can also indicate that the map previously associated
* <tt>null</tt> with the specified key, if the implementation
* supports <tt>null</tt> values.
*/
public V put(final K key, final V value) {
Stack<ScopedMapItem<V>> stack = map.get(key);
ScopedMapItem<V> previousItem;
if (stack == null) {
stack = new Stack<ScopedMapItem<V>>();
map.put(key, stack);
previousItem = null;
} else {
if (stack.empty()) {
previousItem = null;
} else {
previousItem = stack.peek();
}
}
final ScopedMapItem<V> item = new ScopedMapItem<V>(scope, value);
stack.push(item);
if (previousItem == null) {
return null;
}
return previousItem.getValue();
}
/**
* 处理操作符.
*/
public void processOper(Token token, Stack<Token> tokenStack,
List<Token> output) {
if ("(".equals(token.getValue())) {
tokenStack.push(token);
return;
}
if (")".equals(token.getValue())) {
popTokenStack(tokenStack, output, true);
return;
}
if (tokenStack.empty()) {
tokenStack.push(token);
return;
}
Token innerToken = tokenStack.peek();
// 越靠前,索引越小,优先级越高
if (opers.indexOf(innerToken.getValue()) <= opers.indexOf(token
.getValue())) {
// 如果当前token的优先级低于栈顶的操作符优先级,就弹出栈顶的操作符
output.add(tokenStack.pop());
}
tokenStack.push(token);
}
public static void main(String[] argv) {
Stack<String> bar = new Stack<String>();
String foo;
// Compiles, but causes verify error
foo=(bar.empty()?"":bar.peek()).intern();
// The following two work fine
foo = (bar.empty()?"":bar.peek().intern());
foo = (bar.empty()?"":(String)bar.peek()).intern();
}
/**
* 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;
}
protected final ArrayList<T> infixToRPN(ArrayList<T> inputTokens)
throws SyntaxException {
ArrayList<T> out = new ArrayList<T>();
Stack<T> stack = new Stack<T>();
// For each tokens
if (inputTokens != null) {
Iterator<T> it = inputTokens.iterator();
while (it.hasNext()) {
T token = it.next();
// If token is an operator
if (isOperator(token)) {
// While stack not empty AND stack top element
// is an operator
while (!stack.empty() && isOperator(stack.peek())) {
if ((isAssociative(token,
OperandConfiguration.Associativity.LEFT)
&& cmpPrecedence(
token, stack.peek()) <= 0)
|| (isAssociative(
token,
OperandConfiguration.Associativity.RIGHT)
&& cmpPrecedence(
token, stack.peek()) < 0)) {
out.add(stack.pop());
continue;
}
break;
}
// Push the new operator on the stack
stack.push(token);
}
// If token is a left bracket '('
else if (isLeftParenthesis(token)) {
stack.push(token); //
}
// If token is a right bracket ')'
else if (isRightParenthesis(token)) {
while (!stack.empty()
&& !isLeftParenthesis(stack.peek())) {
out.add(stack.pop());
}
try {
stack.pop();
} catch (EmptyStackException e) {
throw new SyntaxException(SyntaxErrors.MISSING_LEFT_PARENTHESIS, token, e);
}
}
// If token is a number
else {
out.add(token);
}
}
}
while (!stack.empty()) {
out.add(stack.pop());
}
return out;
}
public static Instantiator get() {
Stack<Instantiator> stack = getStack();
return stack.empty() ? null : stack.peek();
}
public static int evaluate(String expression) {
char[] tokens = expression.toCharArray();
// Stack for numbers: 'values'
Stack<Integer> values = new Stack<Integer>();
// Stack for Operators: 'ops'
Stack<Character> ops = new Stack<Character>();
for (int i = 0; i < tokens.length; i++) {
// Current token is a whitespace, skip it
if (tokens[i] == ' ')
continue;
// Current token is a number, push it to stack for numbers
if (tokens[i] >= '0' && tokens[i] <= '9') {
StringBuffer sbuf = new StringBuffer();
// There may be more than one digits in number
while (i < tokens.length && tokens[i] >= '0' && tokens[i] <= '9')
sbuf.append(tokens[i++]);
values.push(Integer.parseInt(sbuf.toString()));
}
// Current token is an opening brace, push it to 'ops'
else if (tokens[i] == '(')
ops.push(tokens[i]);
// Closing brace encountered, solve entire brace
else if (tokens[i] == ')') {
while (ops.peek() != '(')
values.push(applyOp(ops.pop(), values.pop(), values.pop()));
ops.pop();
}
// Current token is an operator.
else if (tokens[i] == '+' || tokens[i] == '-' ||
tokens[i] == '*' || tokens[i] == '/') {
// While top of 'ops' has same or greater precedence to current
// token, which is an operator. Apply operator on top of 'ops'
// to top two elements in values stack
while (!ops.empty() && hasPrecedence(tokens[i], ops.peek()))
values.push(applyOp(ops.pop(), values.pop(), values.pop()));
// Push current token to 'ops'.
ops.push(tokens[i]);
}
}
// Entire expression has been parsed at this point, apply remaining
// ops to remaining values
while (!ops.empty())
values.push(applyOp(ops.pop(), values.pop(), values.pop()));
// Top of 'values' contains result, return it
return values.pop();
}
/**
* A deep version of listSimple. Which recursively walks down the tree from a given starting point, returning
* the node refs of files or folders found along the way.
* <p>
* The folder filter is called for each sub-folder to determine whether to search in that sub-folder, should a subfolder be excluded
* then all its chidren are excluded as well.
*
* @param contextNodeRef the starting point.
* @param files return nodes of type files.
* @param folders return nodes of type folders.
* @param folderFilter filter controls which folders to search. If null then all subfolders are searched.
* @return list of node references
*/
/* <p>
* MER: I've added this rather than changing listSimple to minimise the risk of breaking
* the existing code. This is a quick performance improvement between using
* XPath which is awful or adding new methods to the NodeService/DB This is also a dangerous method in that it can return a
* lot of data and take a long time.
*/
private List<NodeRef> listSimpleDeep(NodeRef contextNodeRef, boolean files, boolean folders, SubFolderFilter folderFilter)
{
if(logger.isDebugEnabled())
{
logger.debug("searchSimpleDeep contextNodeRef:" + contextNodeRef);
}
// To hold the results.
List<NodeRef> result = new ArrayList<NodeRef>();
// Build a list of folder types
Set<QName> folderTypeQNames = buildFolderTypes();
Set<QName> fileTypeQNames = (files ? buildFileTypes() : new HashSet<QName>(0));
if(!folders && !files)
{
return Collections.emptyList();
}
// Shortcut
if (folderTypeQNames.size() == 0)
{
return Collections.emptyList();
}
Stack<NodeRef> toSearch = new Stack<NodeRef>();
toSearch.push(contextNodeRef);
// Now we need to walk down the folders.
while(!toSearch.empty())
{
NodeRef currentDir = toSearch.pop();
List<ChildAssociationRef> folderAssocRefs = nodeService.getChildAssocs(currentDir, folderTypeQNames);
for (ChildAssociationRef folderRef : folderAssocRefs)
{
// We have some child folders
boolean include = true;
if(folderFilter != null)
{
include = folderFilter.isEnterSubfolder(folderRef);
if(include)
{
// yes search in these subfolders
toSearch.push(folderRef.getChildRef());
}
}
else
{
// No filter - Add the folders in the currentDir
toSearch.push(folderRef.getChildRef());
}
if(folders && include)
{
result.add(folderRef.getChildRef());
}
}
if(files)
{
// Add the files in the current dir
List<ChildAssociationRef> fileAssocRefs = nodeService.getChildAssocs(currentDir, fileTypeQNames);
for (ChildAssociationRef fileRef : fileAssocRefs)
{
result.add(fileRef.getChildRef());
}
}
}
if(logger.isDebugEnabled())
{
logger.debug("searchSimpleDeep finished size:" + result.size());
}
// Done
return result;
}
protected void updateDigestWithXmlChunk(StringBuilder parseBuf, MessageDigest messageDigest, Stack<XmlTag> stackStartTag,
Stack<XmlTag> stackChunkStartTag, Stack<XmlTag> stackChunkEndTag, Canonicalizer canonicalizer, DocumentBuilder docBuilderNSTrue,
String digestPrefixStr, String digestSuffixStr) throws Exception {
//stackChunkStartTag has start tags whose end tags are not in chunk
//stackChunkEndTag has end tags whose start tags are not in chunk
int startPrefixTagCount = 0, pos;
int startTagToAddCount = stackStartTag.size() - stackChunkStartTag.size();
String startPrefixTags = "", endSuffixTags = "", prefix, suffix;
XmlTag tag;
byte[] tmpbuf;
//add end tags, newest to oldest to match xml structure, to xml chunk for transformation
while (!stackChunkStartTag.empty()) {
//stackChunkStartTag - 0=<MessageSpec>, 1=<TAG>....add suffix </TAG></MessageSpec>
tag = stackChunkStartTag.pop();
//corresponding start tag exists in chunk
endSuffixTags = endSuffixTags + tag.getEndTag();
}
//add start tags, newest to oldest to match xml structure, to xml chunk for transformation
while (!stackChunkEndTag.empty()) {
//stackChunkEndTag - 0=<Address>, 1=<AddressFix>....meaning parseBuf has </AddressFix></Address>
//add prefix <Address><AddressFix>
startPrefixTagCount++;
tag = stackChunkEndTag.pop();
startPrefixTags = startPrefixTags + tag.getStartTag();
//corresponding end tag exists in chunk
}
//add tags, prefix and suffix, present in stackStartTag as they may have NS (namespace) defined
//even if a tag in stackStartTag has no NS defined, we need them because of correct transformation, mainly for 'Exclusive' transformation
//stackStartTag - 0=<OUTERTAG>, 1=<MessageSpec> add prefix=<OUTERTAG><MessageSpec> and suffix=</MessageSpec></OUTERTAG>
prefix = suffix = "";
for (int i = 0; i < startTagToAddCount; i++) {
tag = stackStartTag.get(i);
//do not restrict to tags with ns only - Exclusive transformation would fail
startPrefixTagCount++;
prefix = prefix + tag.getStartTag();
suffix = tag.getEndTag() + suffix;
}
startPrefixTags = prefix + startPrefixTags;
endSuffixTags = endSuffixTags + suffix;
startPrefixTags = digestPrefixStr + startPrefixTags;
//for prefix with digestPrefixStr
//<Object> and <SignatureProperty> has 1 prefix tag while <SignatureProperties><SignatureProperty> has 2
pos = 0;
while ((pos = digestPrefixStr.indexOf(">", pos + 1)) > 0)
startPrefixTagCount++;
endSuffixTags += digestSuffixStr;
String modifiedval = startPrefixTags + parseBuf.toString() + endSuffixTags;
logger.trace("to transform str=" + modifiedval);
Document doc = docBuilderNSTrue.parse(new InputSource(new StringReader(modifiedval)));
String digestval = new String(canonicalizer.canonicalizeSubtree(doc));
logger.trace("transformed str=" + digestval);
//simply drop endSuffixTags - they don't gets altered by canonicalization
if (endSuffixTags.length() > 0)
digestval = digestval.substring(0, digestval.length() - endSuffixTags.length());
//drop canonicalized startPrefixTags - remember they may be altered by transformation and so use prefix count to drop them
pos = 0;
for (int i = 0; i < startPrefixTagCount; i++)
pos = digestval.indexOf(">", pos + 1);
if (pos > 0)
digestval = digestval.substring(pos + 1);
logger.trace("digestval=" + digestval);
tmpbuf = digestval.getBytes();
messageDigest.update(tmpbuf);
if (digestBuf != null)
digestBuf = UtilShared.append(digestBuf, tmpbuf);
parseBuf.setLength(0);
stackChunkStartTag.clear();
stackChunkEndTag.clear();
}
/**
* Get Bidi level of Expression String.
*
* @param message
* @return
*/
public static int[] getExpressionBidiLevel( String message )
{
java.text.Bidi bidi = new Bidi( message,
// Bidi.DIRECTION_DEFAULT_LEFT_TO_RIGHT );
Bidi.DIRECTION_LEFT_TO_RIGHT ); // bidi_hcg
int[] level = new int[message.length( )];
boolean bidiStart = false;
Stack<Character> bracket = new Stack<Character>( );
for ( int i = 0; i < message.length( ); i++ )
{
char c = message.charAt( i );
if ( isNeutral( c ) )
{
// Neutral char enclosed with ' or " should bidi with surround
// bidichar.
// otherwise should not bidi.
if ( c == '\'' || c == '\"' )
{
if ( bracket.empty( ) )
{
bracket.add( Character.valueOf( c ) );
}
else
{
if ( bracket.peek( ).charValue( ) == c )
{
bracket.pop( );
bidiStart = false;
}
else
{
bracket.add( Character.valueOf( c ) );
}
}
}
level[i] = bidiStart && !bracket.empty( ) ? 1 : 0;
}
else
{
level[i] = bidi.getLevelAt( i );
if ( level[i] % 2 != 0 )
{
bidiStart = true;
}
}
}
return level;
}
public int run(String [] argv) throws Exception {
Job job = Job.getInstance(getConf());
job.setJarByClass(GenericMRLoadGenerator.class);
job.setMapperClass(SampleMapper.class);
job.setReducerClass(SampleReducer.class);
if (!parseArgs(argv, job)) {
return -1;
}
Configuration conf = job.getConfiguration();
if (null == FileOutputFormat.getOutputPath(job)) {
// No output dir? No writes
job.setOutputFormatClass(NullOutputFormat.class);
}
if (0 == FileInputFormat.getInputPaths(job).length) {
// No input dir? Generate random data
System.err.println("No input path; ignoring InputFormat");
confRandom(job);
} else if (null != conf.getClass(INDIRECT_INPUT_FORMAT, null)) {
// specified IndirectInputFormat? Build src list
JobClient jClient = new JobClient(conf);
Path tmpDir = new Path("/tmp");
Random r = new Random();
Path indirInputFile = new Path(tmpDir,
Integer.toString(r.nextInt(Integer.MAX_VALUE), 36) + "_files");
conf.set(INDIRECT_INPUT_FILE, indirInputFile.toString());
SequenceFile.Writer writer = SequenceFile.createWriter(
tmpDir.getFileSystem(conf), conf, indirInputFile,
LongWritable.class, Text.class,
SequenceFile.CompressionType.NONE);
try {
for (Path p : FileInputFormat.getInputPaths(job)) {
FileSystem fs = p.getFileSystem(conf);
Stack<Path> pathstack = new Stack<Path>();
pathstack.push(p);
while (!pathstack.empty()) {
for (FileStatus stat : fs.listStatus(pathstack.pop())) {
if (stat.isDirectory()) {
if (!stat.getPath().getName().startsWith("_")) {
pathstack.push(stat.getPath());
}
} else {
writer.sync();
writer.append(new LongWritable(stat.getLen()),
new Text(stat.getPath().toUri().toString()));
}
}
}
}
} finally {
writer.close();
}
}
Date startTime = new Date();
System.out.println("Job started: " + startTime);
int ret = job.waitForCompletion(true) ? 0 : 1;
Date endTime = new Date();
System.out.println("Job ended: " + endTime);
System.out.println("The job took " +
(endTime.getTime() - startTime.getTime()) /1000 +
" seconds.");
return ret;
}