20.[stack][queue][deque]/[list][set]

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

Python code:

class Solution(object):
def isValid(self, s):
dict = {'}':'{',']':'[',')':'('}
stack = []
for i in s:
if i in dict.values():
stack.append(i)
elif i in dict.keys():
if stack==[] or stack.pop()!=dict[i]:
return False
else:
return False
if len(stack)!=0:
return False
return True

About Python

>>> a = [66.25, 333, 333, 1, 1234.5]
>>> print a.count(333), a.count(66.25), a.count('x')
2 1 0
>>> a.insert(2, -1)
>>> a.append(333)
>>> a
[66.25, 333, -1, 333, 1, 1234.5, 333]
>>> a.index(333)
1
>>> a.remove(333)
>>> a
[66.25, -1, 333, 1, 1234.5, 333]
>>> a.reverse()
>>> a
[333, 1234.5, 1, 333, -1, 66.25]
>>> a.sort()
>>> a
[-1, 1, 66.25, 333, 333, 1234.5]
>>> a.pop()
1234.5
>>> a
[-1, 1, 66.25, 333, 333]

Using list as Stack

>>> stack = [3, 4, 5]
>>> stack.append(6)
>>> stack.append(7)
>>> stack
[3, 4, 5, 6, 7]
>>> stack.pop()
7
>>> stack
[3, 4, 5, 6]
>>> stack.pop()
6
>>> stack.pop()
5
>>> stack
[3, 4]

using list as queues

>>> from collections import deque
>>> queue = deque(["Eric", "John", "Michael"])
>>> queue.append("Terry") # Terry arrives
>>> queue.append("Graham") # Graham arrives
>>> queue.popleft() # The first to arrive now leaves
'Eric'
>>> queue.popleft() # The second to arrive now leaves
'John'
>>> queue # Remaining queue in order of arrival
deque(['Michael', 'Terry', 'Graham'])

Java code using stack:

class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<Character>();
for(char c:s.toCharArray()){
if(c=='{')
stack.push('}');
else if(c=='[')
stack.push(']');
else if(c=='(')
stack.push(')');
else if(stack.isEmpty()||stack.pop()!=c){
return false;
}

}
return stack.isEmpty();

}
}

Java code using deque

class Solution {
public boolean isValid(String s) {
Deque<Character> deque = new LinkedList<Character>();
for(char c:s.toCharArray()){
if(c=='{')
deque.addFirst('}');
else if(c=='[')
deque.addFirst(']');
else if(c=='(')
deque.addFirst(')');
else if(deque.isEmpty()||deque.pollFirst()!=c){
return false;
}

}
return deque.isEmpty();

}
}

About Java Stack

Methods

boolean empty() return true if stack is empty

Object peek() return the top object of stack without deleting it

Object pop() return the top object of stack and delete it from the stack

Object push(Object element) push object into the top of stack

int search(Object element) return the index of object, base on 1

if there are multiple same item, return object closest to the top of stack

— try { showpop(st); } catch (EmptyStackException e) { System.out.println(“empty stack”); } } } instead of returning null

— Stack<> stack = new Stack<>();<> →Integer/Character

example from http://blog.csdn.net/a19881029/article/details/9408649:

public class Test {
public static void main(String[] args) {
Stack<String> s = new Stack<String>();
System.out.println("------isEmpty");
System.out.println(s.isEmpty());
System.out.println("------push");
s.push("1");
s.push("2");
s.push("3");
Test.it(s);
System.out.println("------pop");
String str = s.pop();
System.out.println(str);
Test.it(s);
System.out.println("------peek");
str = s.peek();
System.out.println(str);
Test.it(s);
System.out.println("------search");
int i = s.search("2");
System.out.println(i);
i = s.search("1");
System.out.println(i);
i = s.search("none");
System.out.println(i);
}

public static void it(Stack<String> s){
System.out.print("iterator:");
Iterator<String> it = s.iterator();
while(it.hasNext()){
System.out.print(it.next()+";");
}
System.out.print("\n");
}
}

answer:

------isEmpty
true
------push
iterator:1;2;3;
------pop
3
iterator:1;2;
------peek
2
iterator:1;2;
------search
1 --base on one
2 --distance to the top of stack --> 2-1=1
-1 --there is no such thing in the stack

Stack Traversal(http://lavasoft.blog.51cto.com/62575/181781/):

public class TestStack { 
public static void main(String[] args) {
Stack<Integer> s = new Stack<Integer>();
for (int i = 0; i < 10; i++) {
s.push(i);
}
//集合遍历方式,不会清空
for (Integer x : s) {
System.out.println(x);
}
System.out.println("------1-----");
//栈弹出遍历方式,遍历完清空
// while (s.peek()!=null) { //不健壮的判断方式,容易抛异常,正确写法是下面的
while (!s.empty()) {
System.out.println(s.pop());
}
System.out.println("------2-----");
//错误的遍历方式
// for (Integer x : s) {
// System.out.println(s.pop());
// }
}
}
--------------------------------------------------------------------
/**
* 通过快速访问遍历Stack
*/
public static void iteratorThroughRandomAccess(List list) {
String val = null;
for (int i=0; i<list.size(); i++) {
val = (String)list.get(i);
System.out.print(val+" ");
}
System.out.println();
}
/**
* 通过迭代器遍历Stack
*/
public static void iteratorThroughIterator(List list) {
String val = null;
for(Iterator iter = list.iterator(); iter.hasNext(); ) {
val = (String)iter.next();
System.out.print(val+" ");
}
System.out.println();
}
}

About Java queue

The offer method inserts an element if possible, otherwise returning false. This differs from the Collection.add method, which can fail to add an element only by throwing an unchecked exception. The offer method is designed for use when failure is a normal, rather than exceptional occurrence, for example, in fixed-capacity (or "bounded") queues.

The remove() and poll() methods remove and return the head of the queue. Exactly which element is removed from the queue is a function of the queue's ordering policy, which differs from implementation to implementation. The remove() and poll() methods differ only in their behavior when the queue is empty: the remove() method throws an exception, while the poll() method returns null.

The element() and peek() methods return, but do not remove, the head of the queue.

Queue implementations generally do not allow insertion of null elements, although some implementations, such as LinkedList, do not prohibit insertion of null. Even in the implementations that permit it, null should not be inserted into a Queue, as null is also used as a special return value by the poll method to indicate that the queue contains no elements.

example:

package com.ljq.test;
import java.util.LinkedList;
import java.util.Queue;
public class QueueTest {
public static void main(String[] args) {
//add()和remove()方法在失败的时候会抛出异常(不推荐)
Queue<String> queue = new LinkedList<String>();
//添加元素
queue.offer("a");
queue.offer("b");
queue.offer("c");
queue.offer("d");
queue.offer("e");
for(String q : queue){
System.out.println(q);
}
System.out.println("===");
System.out.println("poll="+queue.poll()); //返回第一个元素,并在队列中删除
for(String q : queue){
System.out.println(q);
}
System.out.println("===");
System.out.println("element="+queue.element()); //返回第一个元素
for(String q : queue){
System.out.println(q);
}
System.out.println("===");
System.out.println("peek="+queue.peek()); //返回第一个元素
for(String q : queue){
System.out.println(q);
}

}
}

Java about deque

— -boolean removeFirstOccurrence(Object o);

delete the first element which satisfies the condition(o==null ? e==null : o.equals(e)). it works then return true,no then false

— -boolean removeLastOccurrence(Object o);

delete the last element which satisfies the condition(o==null ? e==null : o.equals(e)). it works then return true,no then false

— -boolean contains(Object o);

— -public int size();

— -Iterator<E> iterator(); from head to tail

— -Iterator<E> descendingIterator(); from tail to head

Compare to Stack and queue:

example

About Python useful Programming Tools

filter(function, sequence) returns a sequence consisting of those items from the sequence for which function(item) is true.

>>> def f(x): return x % 3 == 0 or x % 5 == 0
...
>>> filter(f, range(2, 25))
[3, 5, 6, 9, 10, 12, 15, 18, 20, 21, 24]

map(function, sequence) calls function(item) for each of the sequence’s items and returns a list of the return values. For example, to compute some cubes:

>>> def cube(x): return x*x*x
...
>>> map(cube, range(1, 11))
[1, 8, 27, 64, 125, 216, 343, 512, 729, 1000]

More than one sequence may be passed

>>> seq = range(8)
>>> def add(x, y): return x+y
...
>>> map(add, seq, seq)
[0, 2, 4, 6, 8, 10, 12, 14]
One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.