判断括号是否匹配：调用java本身
import java.util.Stack;
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.empty())
return false;
char topChar=stack.pop();
if(c==')'&&topChar!='(')
return false;
if(c==']'&&topChar!='[')
return false;
if(c=='}'&&topChar!='{')
return false;
}
}
return stack.empty();
}
public static void main(String[] args){
System.out.println(
(new Solution()).isValid("(){}[]"));
System.out.println(
(new Solution()).isValid("([)]"));
}
}
调用自己写的：
接口：
public interface Stack<E> {
int getSize();
boolean isEmpty();
void push(E e);
E pop();
E peek();
}
实现方法：
public class ArrayStack<E> implements Stack<E> {
Array<E> array;
public ArrayStack(int capacity){
array=new Array<>(capacity);
}
public ArrayStack(){
array=new Array<>();
}
@Override
public int getSize(){
return array.getSize();
}
@Override
public boolean isEmpty(){
return array.isEmpty();
}
public int getCapacity(){
return array.getCapacity();
}
@Override
public void push(E e){
array.addLast(e);
}
@Override
public E pop(){
return array.removeLast();
}
@Override
public E peek(){
return array.getLast();
}
@Override
public String toString(){
StringBuilder res=new StringBuilder();
res.append("Stack:");
res.append("[");
for(int i=0;i<array.getSize();i++){
res.append(array.get(i));
if(i!=array.getSize()-1)//最后一个元素
res.append(",");
}
res.append("] top");
return res.toString();
}
}
队列也是一种线性结构
相比数组，队列对应的操作是数组的子集
只能从一端（队尾）添加元素，只能从另一端（队首）取出元素
public class ArrayQueue<E> implements Queue<E> {
private Array<E> array;
public ArrayQueue(int capacity){
array=new Array<>(capacity);
}
public ArrayQueue(){
array=new Array<>();
}
@Override
public int getSize(){
return array.getSize();
}
@Override
public boolean isEmpty(){
return array.isEmpty();
}
public int getCapacity(){
return array.getCapacity();
}
@Override
public void enqueue(E e){
array.addLast(e);
}
@Override
public E dequeue(){
return array.removeFirst();
}
@Override
public E getFront(){
return array.getFirst();
}
@Override
public String toString(){
StringBuilder res=new StringBuilder();
res.append("Queue:");
res.append("front [");
for(int i=0;i<array.getSize();i++){
res.append(array.get(i));
if(i!=array.getSize()-1)//判断是否是最后一个元素
res.append(", ");
}
res.append("] tail");
return res.toString();
}
public static void main(String[] args){
ArrayQueue<Integer> queue=new ArrayQueue<>();
for (int i=0;i<10;i++){
queue.enqueue(i);
System.out.println(queue);
if(i%3==2){
queue.dequeue();
System.out.println(queue);
}
}
}
}
循环队列：
public class LoopQueue<E> implements Queue<E>{
private E[] data;
private int front,tail;
private int size;
public LoopQueue(int capacity){
data=(E[])new Object[capacity+1];
front=0;
tail=0;
size=0;
}
public LoopQueue(){
this(10);
}
//浪费一个元素
public int getCapacity(){
return data.length-1;
}
@Override
public boolean isEmpty(){
return front==tail;
}
@Override
public int getSize(){
return size;
}
@Override
public void enqueue(E e){
//判断队列是否满
if((tail+1)%data.length==front)
resize(getCapacity()*2);
data[tail]=e;
tail=(tail+1)%data.length;
size++;
}
@Override
public E dequeue(){
if(isEmpty())
throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
E ret=data[front];
data[front]=null;
front=(front+1)%data.length;
size--;
if(size==getCapacity()/4&&getCapacity()/2!=0)
resize(getCapacity()/2);
return ret;
}
@Override
public E getFront(){
if(isEmpty())
throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
return data[front];
}
private void resize(int newCapacity){
E[] newData=(E[])new Object[newCapacity+1];
for(int i=0;i<size;i++){
newData[i]=data[(i+front)%data.length];
}
data=newData;
front=0;
tail=size;
}
@Override
public String toString(){
StringBuilder res=new StringBuilder();
res.append(String.format("Queue:size=%d,capacity=%d\n", size,getCapacity()));
res.append("front [");
for(int i=front;i!=tail;i=(i+1)%data.length){
res.append(data[i]);
if((i+1)%data.length!=tail)//判断是否是最后一个元素
res.append(", ");
}
res.append("] tail");
return res.toString();
}
public static void main(String[] args){
LoopQueue<Integer> queue=new LoopQueue<>();
for (int i=0;i<10;i++){
queue.enqueue(i);
System.out.println(queue);
if(i%3==2){
queue.dequeue();
System.out.println(queue);
}
}
}
}
public class Main {
//测试使用q运行opCount个enqueueu和dequeue操作所需要的时间，单位 秒
private static double testQueue(Queue<Integer> q,int opCout){
long startTime=System.nanoTime();
Random random=new Random();
for( int i=0;i<opCout;i++){
q.enqueue(random.nextInt(Integer.MAX_VALUE));
}
for(int i=0;i<opCout;i++){
q.dequeue();
}
long endTime=System.nanoTime();
return (endTime-startTime)/1000000000.0;
}
public static void main(String[] args){
int opCount=100000;
ArrayQueue<Integer> arrayQueue=new ArrayQueue<>();
double time1=testQueue(arrayQueue, opCount);
System.out.println("ArrayQueue,time: "+time1+" s");
LoopQueue<Integer> loopQueue=new LoopQueue<>();
double time2=testQueue(loopQueue, opCount);
System.out.println("ArrayQueue,time: "+time2+" s");
}
}