public class Array<E> {
int size;
E[] data;
public Array(int capacity) {
data=(E[])new Object[capacity];
size=0;
}
public Array() {
data=(E[])new Object[10];
size=0;
}
public int getSize() {
return size;
}
public int getCapacity() {
return data.length;
}
public boolean isEmpty() {
return size==0;
}
public void add(int index,E e) {
if (size==getCapacity())
resize(2*data.length);
if (index<0||index>size)
throw new IllegalArgumentException("index ");
for (int i = data.length-1; i >=index; i--) {
data[i+1]=data[i];
}
data[size]=e;
size++;
}
public void addLast(E e) {
add(size, e);
}
public void addFirst(E e) {
add(0, e);
}
public E get(int index) {
if (index<0||index>size)
throw new IllegalArgumentException("index ");
return data[index];
}
public E getLast() {
return get(data.length);
}
public void set(int index,E e) {
if (index<0||index>size)
throw new IllegalArgumentException("index ");
data[index]=e;
}
public boolean contains(E e) {
for (int i = 0; i < size; i++) {
if (data[i]==e) {
return true;
}
}
return false;
}
public int find(E e) {
for (int i = 0; i < size; i++) {
if (data[i]==e) {
return i;
}
}
return -1;
}
public E remove(int index) {
if (index<0||index>=size)
throw new IllegalArgumentException("index ");
E res=data[index];
for (int i = index+1; i < data.length; i++) {
data[i-1]=data[i];
}
size--;
data[size]=null;
if (size==data.length/4) {
resize(data.length/2);
}
return res;
}
public E removeLast() {
return remove(data.length);
}
public boolean removeElement(E e) {
int res = find(e);
if (res!=-1) {
remove(res);
return true;
}
return false;
}
private void resize(int newCapacity) {
E[] newdata=(E[])new Object[newCapacity];
for (int i = 0; i < data.length; i++) {
newdata[i]=data[i];
}
data=newdata;
}
}
public class Stack<E> {
Array<E> array;
public Stack(int capacity) {
array=new Array<E>(capacity);
}
void push(E e) {
array.addLast(e);
}
E pop() {
return array.removeLast();
}
E peek() {
return array.getLast();
}
boolean isEmpty() {
return array.isEmpty();
}
}
小判例:有効な括弧:「(',')」、'''、''''、'''、'''』という文字列を与えて、文字列が有効かどうかを判断する.有効な文字列を満たす必要があります.左括弧は同じ種類の右括弧で閉じなければなりません.左括弧は正しい順番で閉じなければなりません.注意空の文字列は有効な文字列と考えられます.
public class Solution {
public boolean isValid(String s) {
Stack<Character> stack=new Stack();
for (int i = 0; i < s.length(); i++) {
char c=s.charAt(i);
if (c=='('||c=='['||c=='{') {
stack.push(c);
}else {
if (stack.isEmpty()==true) {
return false;
}
char topchar = stack.pop();
if (c==')'&&topchar!='(') {
return false;
}
if (c==']'&&topchar!='[') {
return false;
}
if (c=='}'&&topchar!='{') {
return false;
}
}
}
return stack.isEmpty();
}
}