下面列出了java.util.Stack#peek ( ) 实例代码,或者点击链接到github查看源代码,也可以在右侧发表评论。
/**
* DP
*/
public int longestValidParenthesesB(String s) {
if (s == null || s.length() == 0) return 0;
Stack<Integer> stack = new Stack<>(); // Save indices of '('
int[] dp = new int[s.length()]; // Store the length of the current longest valid sequence.
int max = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') stack.push(i);
else if (stack.isEmpty()) continue;
else if (stack.peek() > 0)
dp[i] = 2 + dp[stack.pop() - 1] + dp[i - 1]; // connect two valid sequences, or increase the length of current valid sequence.
else {
dp[i] = 2 + dp[i - 1]; // leftmost char is a '('
stack.pop();
}
max = Math.max(dp[i], max);
}
return max;
}
public boolean IsPopOrder(int[] pushA, int[] popA) {
//特殊情况序列为零的判断:
if (pushA.length == 0 || popA.length == 0) return false;
Stack <Integer> stack = new Stack <Integer>();
//用于标识弹出序列的位置
int index = 0;
for (int i = 0; i < pushA.length; i++) {
stack.push( pushA[i] );
while (!stack.isEmpty() && stack.peek() == popA[index]) {
//出栈
stack.pop();
//弹出序列向后一位a
index++;
}
}
return stack.isEmpty();
}
public static void traversePreorder(TreeNode<?> rootNode) {
if (rootNode == null) {
return;
}
Stack<TreeNode<?>> stack = new Stack<TreeNode<?>>();
stack.push(rootNode);
while (!stack.empty()) {
TreeNode<?> current = stack.peek();
System.out.println(current);
if (current.hasLeft()) {
stack.push(current.getLeft());
} else {
// Pop until we have a node with a right sub-tree.
while (!stack.empty()) {
current = stack.pop();
if (current.hasRight()) {
stack.push(current.getRight());
break;
}
}
}
}
}
public int[] nextLargerNodes(ListNode head) {
List<Integer> list = new ArrayList<>();
while (head != null) {
list.add(head.val);
head = head.next;
}
int[] res = new int[list.size()];
Stack<Integer> st = new Stack<>();
for (int i = list.size() - 1; i >= 0; i--) {
int num = list.get(i);
while (!st.isEmpty() && st.peek() <= num) st.pop();
if (st.isEmpty()) res[i] = 0;
else res[i] = st.peek();
st.push(num);
}
return res;
}
private void startAnnotation(Nindo.Builder builder, String annotationKey,
String annotationValue) {
Stack<String> annotationStack = startedAnnotations.get(annotationKey);
if (annotationStack == null) {
annotationStack = new Stack<String>();
startedAnnotations.put(annotationKey, annotationStack);
affectedKeys.add(annotationKey);
}
String current = annotationStack.isEmpty() ? null : annotationStack.peek();
// Avoid no-ops
if (ValueUtils.notEqual(annotationValue, current)) {
if (current == null && isDefaultValue(annotationKey, annotationValue)) {
// If the current annotation is the default, and the new annotation
// value is also the default, we don't need to set the annotation value
} else {
builder.startAnnotation(annotationKey, annotationValue);
}
}
annotationStack.push(annotationValue);
}
/**
* Optimized DP
* Build a stack for indices of open parentheses
* Traverse the string, if current is open paren, push to stack
* Otherwise, its close paren.
* If stack is empty, no open paren left, reset len to 0.
* If not, pop the index from stack, matchedLen = current index - index of
* pop open paren + 1
* If stack is empty, means this matchedLen can be added to the whole len
* If not,
*/
public static int longestValidParentheses(String s) {
if (s == null) return 0;
Stack<Integer> stack = new Stack<Integer>();
int maxLen = 0;
int len = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') stack.push(i);
else if (s.isEmpty()) len = 0;
else {
int matchedPos = stack.pop();
int matchedLen = i - matchedPos + 1;
if (s.isEmpty()) { // ()()
len += matchedLen;
matchedLen = len;
} else matchedLen = i - stack.peek(); // ()(()()
maxLen = Math.max(maxLen, matchedLen);
}
}
return maxLen;
}
/**
* Directly using java.util.stack.
* Not recommended since stack has been deprecated.
* Create a stack to deal with collisions.
* For each asteroids, ast:
* | Check if there is a collision, when stack is not empty, and asteroid size < 0, and previous asteroid > 0
* | If yes, compare asteroids' sizes:
* | If ast is larger, pop previous asteroid from stack, continue comparison with the next stack top.
* | If ast is the same size, just pop since both asteroids are destroyed. Then continue to next asteroid.
* | If ast is smaller, it's destroyed. Continue to next asteroid.
* | If no, push the current asteroid to the stack and continue to next asteroid.
* After all asteroids are done, convert the resulting stack to an array.
*/
public int[] asteroidCollision2(int[] asteroids) {
Stack<Integer> stack = new Stack<>();
for (int ast : asteroids) {
while (!stack.isEmpty() && ast < 0 && 0 < stack.peek()) {
if (stack.peek() < -ast) {
stack.pop();
continue;
} else if (stack.peek() == -ast) {
stack.pop();
}
break;
}
stack.push(ast);
}
int[] ans = new int[stack.size()];
for (int t = ans.length - 1; t >= 0; --t) {
ans[t] = stack.pop();
}
return ans;
}
public int[] nextGreaterElements(int[] nums) {
Stack<Integer> stack = new Stack<>();
int len = nums.length, result[] = new int[len];
for (int i = 0; i < len; i++) {
while (!stack.empty() && nums[stack.peek()] < nums[i]) {
result[stack.pop()] = nums[i];
}
stack.add(i);
}
for (int num : nums) {
while (!stack.empty() && nums[stack.peek()] < num) {
result[stack.pop()] = num;
}
}
while (!stack.empty()) result[stack.pop()] = -1;
return result;
}
/**
* Find the start and end position of the phase 2 query, if it exists,
* in the query string. Also performs basic JSON syntax validation.
*
* @return true if the query is valid, false otherwise
*/
protected boolean findQueryPosition() {
Stack<Integer> stack = new Stack<>();
char[] chars = queryString.toCharArray();
for (int i = 0; i < chars.length; i++) {
char c = chars[i];
if (c != '{' && c != '}') {
continue;
}
if (c == '{') {
stack.push(i);
continue;
}
if (!stack.empty()) {
queryStartPos = stack.peek();
queryEndPos = i + 1;
stack.pop();
} else {
return false;
}
}
return queryStartPos != null && queryEndPos != null;
}
private void initialize(String [] tokens) {
final Stack<Integer> stack = new Stack<>();
int nodeIndex = 0;
for (String token : tokens) {
final Matcher matcher = NONTERMINAL_PATTERN.matcher(token);
if (matcher.matches()) {
// new non-terminal node
labels[nodeIndex] = matcher.group(1);
sourceStartIndices[nodeIndex] = Integer.parseInt(matcher.group(2));
sourceEndIndices[nodeIndex] = Integer.parseInt(matcher.group(3));
stack.push(nodeIndex);
nodeIndex++;
} else if (token.equals(")")) {
// finished a subtree
stack.pop();
if (stack.empty()) {
break;
} else {
numChildren[stack.peek()]++;
}
} else {
// otherwise, it's a new leaf node
labels[nodeIndex] = token;
sourceStartIndices[nodeIndex] = -1;
sourceEndIndices[nodeIndex] = -1;
numChildren[stack.peek()]++;
nodeIndex++;
}
}
if (!stack.empty()) {
// Not enough close-parentheses at the end of the tree.
throw new IllegalArgumentException();
}
}
/**
* 问题:给定数组为压栈顺序(无重复),判断另一数组是否可能为出栈顺序
* 思路:建立一个辅助栈,依序遍历压栈序列,若与出栈数不相等,则将该压栈数压入辅助栈,继续遍历压栈数组
* 若相等则继续遍历入栈序列和出栈序列,当出栈序列与入栈序列和辅助栈序列都不一致时,返回 false
* 若辅助栈空,且入栈序列遍历完毕则返回 true
* @param pushOrder
* @param popOrder
* @return
*/
public boolean isPopOrder(int[] pushOrder,int[] popOrder){
// 出栈、入栈序列为空或长度不相等,则返回 false
if (pushOrder == null || popOrder == null||pushOrder.length!=popOrder.length) {
return false;
}
Stack<Integer> stack = new Stack<>();
int pushIndex = 0,
popIndex = 0,
len=pushOrder.length;
while (popIndex < len) {
if (pushIndex<len&&pushOrder[pushIndex] == popOrder[popIndex]) { // 入栈出栈序列一致,继续遍历下一个
popIndex++;
pushIndex++;
}
// 辅助栈顺序与出栈序列一致,辅助栈出栈,继续遍历下一个
else if (stack.size() != 0 && stack.peek() == popOrder[popIndex]) {
popIndex++;
stack.pop();
}
// 入栈序列遍历结束且辅助栈顺序与出栈序列不一致,直接返回 false
else if (pushIndex >= len && stack.peek() != popOrder[popIndex]) {
return false;
}
// 压入辅助装,继续寻找下一相同序列
else {
stack.push(pushOrder[pushIndex]);
pushIndex++;
}
}
return stack.size()==0&&pushIndex==len; // 当序列一致时,辅助栈为空,入栈序列遍历完成
}
/**
* Get parent Node Context
*
* @param contextStack context stack
* @return node context
*/
private NodeContext peekNodeContext(Stack<ElementContext> contextStack)
{
ElementContext element = contextStack.peek();
if (element instanceof NodeContext)
{
return (NodeContext)element;
}
else if (element instanceof NodeItemContext)
{
return ((NodeItemContext)element).getNodeContext();
}
throw new ImporterException("Internal error: Failed to retrieve node context");
}
/**
* Find mime type for a given editor kit implementation class.
*
* @param kitClass The editor kit class to get the mime type for.
* @return The mime type or <code>null</code> if the mime type can't be
* resolved for the given kit class.
*/
public String findMimeType(Class kitClass) {
if (kitClass != null) {
if (WELL_KNOWN_PARENTS.contains(kitClass.getName())) {
// these classes are not directly registered as a kit for any mime type
return null;
}
String contextMimeType = null;
Stack<String> context = contexts.get();
if (context != null && !context.empty()) {
contextMimeType = context.peek();
}
if (contextMimeType == null || contextMimeType.length() == 0) {
List mimeTypes = getMimeTypesForKitClass(kitClass);
if (mimeTypes.size() == 0) {
if (LOG.isLoggable(Level.WARNING) && !DYNAMIC_LANGUAGES.contains(kitClass.getName())) {
logOnce(Level.WARNING, "No mime type uses editor kit implementation class: " + kitClass); //NOI18N
}
return null;
} else if (mimeTypes.size() == 1) {
return (String) mimeTypes.get(0);
} else {
if (LOG.isLoggable(Level.WARNING)) {
// Throwable t = new Throwable("Stacktrace"); //NOI18N
// LOG.log(Level.WARNING, "Ambiguous mime types for editor kit implementation class: " + kitClass + "; mime types: " + mimeTypes, t); //NOI18N
logOnce(Level.WARNING, "Ambiguous mime types for editor kit implementation class: " + kitClass + "; mime types: " + mimeTypes); //NOI18N
}
return null;
}
} else{
return contextMimeType;
}
} else {
return ""; //NOI18N
}
}
/**
* 3.6 Sort Stack using peek, pop, push, isEmpty. O(n^2) time no extra memory.
*/
public static Stack<Integer> sort(Stack<Integer> source) {
Stack<Integer> result = new Stack<Integer>();
while (!source.isEmpty()) {
Integer el = source.pop();
while (!result.isEmpty() && result.peek() < el) {
source.push(result.pop());
}
result.push(el);
}
return result;
}
/**
* Adds the given number as a push data chunk to the given index in the program.
* This is intended to use for negative numbers or values greater than 16, and although
* it will accept numbers in the range 0-16 inclusive, the encoding would be
* considered non-standard.
*
* @see #number(long)
*/
protected ScriptBuilder bigNum(int index, long num) {
final byte[] data;
if (num == 0) {
data = new byte[0];
} else {
Stack<Byte> result = new Stack<>();
final boolean neg = num < 0;
long absvalue = Math.abs(num);
while (absvalue != 0) {
result.push((byte) (absvalue & 0xff));
absvalue >>= 8;
}
if ((result.peek() & 0x80) != 0) {
// The most significant byte is >= 0x80, so push an extra byte that
// contains just the sign of the value.
result.push((byte) (neg ? 0x80 : 0));
} else if (neg) {
// The most significant byte is < 0x80 and the value is negative,
// set the sign bit so it is subtracted and interpreted as a
// negative when converting back to an integral.
result.push((byte) (result.pop() | 0x80));
}
data = new byte[result.size()];
for (int byteIdx = 0; byteIdx < data.length; byteIdx++) {
data[byteIdx] = result.get(byteIdx);
}
}
// At most the encoded value could take up to 8 bytes, so we don't need
// to use OP_PUSHDATA opcodes
return addChunk(index, new ScriptChunk(data.length, data));
}
/**
* Begin the scope of namespace prefix. Forward the event to the
* SAX handler only if the prefix is unknown or it is mapped to a
* different URI.
*/
private boolean startPrefixMapping(String prefix, String uri)
throws SAXException
{
boolean pushed = true;
Stack uriStack = _nsPrefixes.get(prefix);
if (uriStack != null) {
if (uriStack.isEmpty()) {
_sax.startPrefixMapping(prefix, uri);
uriStack.push(uri);
}
else {
final String lastUri = (String) uriStack.peek();
if (!lastUri.equals(uri)) {
_sax.startPrefixMapping(prefix, uri);
uriStack.push(uri);
}
else {
pushed = false;
}
}
}
else {
_sax.startPrefixMapping(prefix, uri);
_nsPrefixes.put(prefix, uriStack = new Stack());
uriStack.push(uri);
}
return pushed;
}
public boolean validateStackSequences(int[] pushed, int[] popped) {
int len1 = pushed.length;
int len2 = popped.length;
if (len1 == 0 && len2 == 0){
return true;
}
if (len2 == 0 || len1 != len2) {
return false;
}
int index = 0;
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < len1; i++) {
stack.push(pushed[i]);
while (!stack.isEmpty() && stack.peek() == popped[index]) {
stack.pop();
index++;
}
// 调试代码
// System.out.println(stack);
}
return stack.isEmpty();
}
/**
* Parses the filterString and constructs a filter using it
* <p>
* @param filterStringAsByteArray filter string given by the user
* @return filter object we constructed
*/
public Filter parseFilterString (byte [] filterStringAsByteArray)
throws CharacterCodingException {
// stack for the operators and parenthesis
Stack <ByteBuffer> operatorStack = new Stack<>();
// stack for the filter objects
Stack <Filter> filterStack = new Stack<>();
Filter filter = null;
for (int i=0; i<filterStringAsByteArray.length; i++) {
if (filterStringAsByteArray[i] == ParseConstants.LPAREN) {
// LPAREN found
operatorStack.push(ParseConstants.LPAREN_BUFFER);
} else if (filterStringAsByteArray[i] == ParseConstants.WHITESPACE ||
filterStringAsByteArray[i] == ParseConstants.TAB) {
// WHITESPACE or TAB found
continue;
} else if (checkForOr(filterStringAsByteArray, i)) {
// OR found
i += ParseConstants.OR_ARRAY.length - 1;
reduce(operatorStack, filterStack, ParseConstants.OR_BUFFER);
operatorStack.push(ParseConstants.OR_BUFFER);
} else if (checkForAnd(filterStringAsByteArray, i)) {
// AND found
i += ParseConstants.AND_ARRAY.length - 1;
reduce(operatorStack, filterStack, ParseConstants.AND_BUFFER);
operatorStack.push(ParseConstants.AND_BUFFER);
} else if (checkForSkip(filterStringAsByteArray, i)) {
// SKIP found
i += ParseConstants.SKIP_ARRAY.length - 1;
reduce(operatorStack, filterStack, ParseConstants.SKIP_BUFFER);
operatorStack.push(ParseConstants.SKIP_BUFFER);
} else if (checkForWhile(filterStringAsByteArray, i)) {
// WHILE found
i += ParseConstants.WHILE_ARRAY.length - 1;
reduce(operatorStack, filterStack, ParseConstants.WHILE_BUFFER);
operatorStack.push(ParseConstants.WHILE_BUFFER);
} else if (filterStringAsByteArray[i] == ParseConstants.RPAREN) {
// RPAREN found
if (operatorStack.empty()) {
throw new IllegalArgumentException("Mismatched parenthesis");
}
ByteBuffer argumentOnTopOfStack = operatorStack.peek();
if (argumentOnTopOfStack.equals(ParseConstants.LPAREN_BUFFER)) {
operatorStack.pop();
continue;
}
while (!(argumentOnTopOfStack.equals(ParseConstants.LPAREN_BUFFER))) {
filterStack.push(popArguments(operatorStack, filterStack));
if (operatorStack.empty()) {
throw new IllegalArgumentException("Mismatched parenthesis");
}
argumentOnTopOfStack = operatorStack.pop();
}
} else {
// SimpleFilterExpression found
byte [] filterSimpleExpression = extractFilterSimpleExpression(filterStringAsByteArray, i);
i+= (filterSimpleExpression.length - 1);
filter = parseSimpleFilterExpression(filterSimpleExpression);
filterStack.push(filter);
}
}
// Finished parsing filterString
while (!operatorStack.empty()) {
filterStack.push(popArguments(operatorStack, filterStack));
}
if (filterStack.empty()) {
throw new IllegalArgumentException("Incorrect Filter String");
}
filter = filterStack.pop();
if (!filterStack.empty()) {
throw new IllegalArgumentException("Incorrect Filter String");
}
return filter;
}
public static String globToRE(String glob) {
if (glob.startsWith("(re)")) {
return glob.substring(4);
}
final Object NEG = new Object();
final Object GROUP = new Object();
Stack<Object> state = new Stack<Object>();
StringBuilder buf = new StringBuilder();
boolean backslash = false;
int length = glob.length();
for (int i = 0; i < length; i++) {
char c = glob.charAt(i);
if (backslash) {
buf.append('\\');
buf.append(c);
backslash = false;
continue;
}
switch (c) {
case '\\':
backslash = true;
break;
case '?':
buf.append('.');
break;
case '.':
case '+':
case '(':
case ')':
buf.append('\\');
buf.append(c);
break;
case '*':
buf.append(".*");
break;
case '|':
if (backslash)
buf.append("\\|");
else
buf.append('|');
break;
case '{':
buf.append('(');
if (i + 1 != length && glob.charAt(i + 1) == '!') {
buf.append('?');
state.push(NEG);
} else
state.push(GROUP);
break;
case ',':
if (!state.isEmpty() && state.peek() == GROUP)
buf.append('|');
else
buf.append(',');
break;
case '}':
if (!state.isEmpty()) {
buf.append(')');
if (state.pop() == NEG)
buf.append(".*");
} else
buf.append('}');
break;
default:
buf.append(c);
}
}
return buf.toString();
}
/**
* Prunes redundant edges from the workflow.
*
* @param workflow
* @param root the root from which to start to assign the levels
* @return the workflow with non essential edges removed
*/
public void assignLevels(Graph workflow, GraphNode root) {
// start a DFS for the graph at root.
reset(workflow);
// mCurrentDepth = 0;
root.setDepth(0);
root.setColor(GraphNode.GRAY_COLOR);
// System.out.println( "Traversing node " + root.getID() );
// start an iterative DFS on the root
Stack<GraphNode> stack = new Stack();
stack.push(root);
while (!stack.isEmpty()) {
GraphNode top = stack.peek();
int newDepth = top.getDepth() + 1;
for (GraphNode child : top.getChildren()) {
// we always update the depth to max of current and new depth
child.setDepth(Math.max(child.getDepth(), newDepth));
if (child.isColor(GraphNode.WHITE_COLOR)) {
child.setColor(GraphNode.GRAY_COLOR);
// System.out.println( "Traversing node " + child.getID() + " with depth " +
// child.getDepth());
stack.push(child);
}
}
// set the color of the node to be black
top.setColor(GraphNode.BLACK_COLOR);
stack.pop();
}
// reset colors again to white
// sanity intialization of all nodes depth
for (Iterator it = workflow.nodeIterator(); it.hasNext(); ) {
GraphNode node = (GraphNode) it.next();
node.setColor(GraphNode.WHITE_COLOR);
}
}