栈和队列操作：栈实现、队列实现、双栈实现队列、双队列实现栈、栈实现O(n)求当前栈最大值

1. 栈实现
2. 队列实现
3. 双栈实现队列
4. 双队列实现栈
5. 栈实现O(n)求当前栈最大值

import java.util.Arrays;
import java.util.Comparator;
import java.util.Random;
/*
* shsheng
*/
public class StackAndQueue {
public static final int SIZE=10;
public static final int MAXSIZE=16*SIZE;
public static void main(String[] args) {
testQueue();
testStack();
testTwoQueueWorkStack();
testTwoStackWorkQueue();
testStackAndMax();
}
/*
* 用栈实现当前栈的最大值，时间复杂度O(n)
* 求解方法：双栈
*/
static class StackAndMax{
Stackstack=new Stack();
StackmaxStack=new Stack(); public boolean isEmpty(){ return stack.isEmpty(); } public void push(T data){ if(stack.isEmpty()){ maxStack.push(data); }else{ T max=maxStack.peek(); if((Integer)data>(Integer)max) max=data; maxStack.push(max); } stack.push(data); } public T pop(){ maxStack.pop(); return stack.pop(); } public T getMax(){ return maxStack.peek(); } } public static void testStackAndMax(){ StackAndMax stack=new StackAndMax (); Random random=new Random(); System.out.println("StackAndMax"); for(int i=0;i<10;i++){ int length=random.nextInt(30); for(int j=0;j { Stack enStack=new Stack (); Stack deStack=new Stack (); public boolean isEmpty(){ return enStack.isEmpty()&&deStack.isEmpty(); } public void enQueue(T data){ enStack.push(data); } public T deQueue(){ if(isEmpty()){ try { throw new Exception("Empty TwoStackWorkQueue!"); } catch (Exception e) { e.printStackTrace(); } } if(deStack.isEmpty()){ while(!enStack.isEmpty()){ deStack.push(enStack.pop()); } } return deStack.pop(); } } public static void testTwoStackWorkQueue(){ System.out.println("Test TwoStackWorkQueue"); TwoStackWorkQueue queue=new TwoStackWorkQueue (); for(int i=9;i<12;i++){ System.out.println("TwoStackWorkQueue Length:\t"+i); for(int j=0;j { Queue queue1=new Queue (); Queue queue2=new Queue (); public boolean isEmpty(){ return queue1.isEmpty(); } public void push(T data){ queue1.enQueue(data); } public T pop(){ if(isEmpty()){ try { throw new Exception("Empty TwoQueueWorkStack!"); } catch (Exception e) { e.printStackTrace(); } } T data=queue1.deQueue(); while(!queue1.isEmpty()){ queue2.enQueue(data); data=queue1.deQueue(); } Queue tmp=queue1; queue1=queue2; queue2=tmp; return data; } } public static void testTwoQueueWorkStack(){ System.out.println("Test TwoQueueWorkStack"); TwoQueueWorkStack stack=new TwoQueueWorkStack (); for(int i=9;i<12;i++){ System.out.println("TwoQueueWorkStack Length:\t"+i); for(int j=0;j { Object[] stack; int capacity; int top; public Stack(){ capacity=SIZE; stack=new Object[capacity]; top=0; } public Stack(int size){ if(size>SIZE) capacity=size; else capacity=SIZE; stack=new Object[capacity]; top=0; } public boolean isEmpty(){ return top==0; } public void push(T data){ if(top>=capacity){ if(capacity>MAXSIZE){ try { throw new Exception("Stack is so big!"); } catch (Exception e) { e.printStackTrace(); } } capacity=2*capacity; stack=Arrays.copyOf(stack, capacity); } stack[top++]=data; } public T pop(){ T data=peek(); top--; return data; } public T peek(){ if(isEmpty()){ try { throw new Exception("Empty TwoQueueWorkStack!"); } catch (Exception e) { e.printStackTrace(); } } return (T) stack[top-1]; } } public static void testStack(){ System.out.println("Test Stack"); Stack stack=new Stack (); for(int i=9;i<12;i++){ System.out.println("Stack Length:\t"+i); for(int j=0;j { Object[] queue; int capacity; int front; int rear; public Queue(){ capacity=SIZE; queue=new Object[capacity]; front=0; rear=0; } public Queue(int size){ if(size>SIZE) capacity=size; else capacity=SIZE; queue=new Object[capacity]; front=0; rear=0; } public boolean isEmpty(){ return (front==rear); } public void enQueue(T data){ if((rear+1)%capacity==front){ if(capacity>MAXSIZE){ try { throw new Exception("Queue is so big!"); } catch (Exception e) { e.printStackTrace(); } } Object[] queue1=new Object[2*capacity]; int rear1=0; while(front!=rear){ queue1[rear1++]=queue[front]; front=(front+1)%capacity; } rear=rear1; front=0; capacity=2*capacity; queue=queue1; } queue[rear]=data; rear=(rear+1)%capacity; } public T deQueue(){ if(isEmpty()){ try { throw new Exception("Empty Queue!"); } catch (Exception e) { e.printStackTrace(); } } T data=(T) queue[front]; front=(front+1)%capacity; return data; } } public static void testQueue(){ System.out.println("Test Queue"); Queue queue=new Queue (); for(int i=9;i<12;i++){ System.out.println("Queue Length:\t"+i); for(int j=0;j