面接手引き裂きコードまとめ(三)-スタック
2985 ワード
面接手引き裂きコードまとめ(三)-スタック
1.配列によるスタックの実装
2.チェーンテーブル方式でスタックを実現する
3.スタック内の最小要素を求める
4.2つのスタックシミュレーションキュー
5.あるスタックが別のスタックのポップアップ順序であるかどうかを判断する
1.配列によるスタックの実装
public class MyStack{
private Object[] stack;
private int size;
public MyStack(){
stack=new Object[10];
}
//
public boolean isEmpty(){
return size==0;
}
public E peek(){
if(isEmpty()){
return null;
}
return(E) stack[size-1];
}
public E pop(){
E e=peek();
stack[size-1]=null;
size--;
return e;
}
public E push(){
ensureCapacity(size+1);
stack[size+1]=item;
return item;
}
// , ,
private void ensureCapacity(int size){
int len=stack.length;
if(size>len){
int newLen=10;
stack=Arrays.copyOf(stack,newLen);
}
}
}
2.チェーンテーブル方式でスタックを実現する
class Node{
Node next=null;
E data;
public Node(E data){this.data=data;}
}
public class Stack{
Node top=null;
public boolean isEmpty(){
return top==null;
}
public void push(E data){
Node newNode=new Node(data);
newNode.next=top;
top=newNode;
}
public E pop(){
if(this.isEmpty())
return null;
E data=top.data;
top=top.next;
return data;
}
public E peek(){
if(isEmpty){
return null;
}
return top.data;
}
}
3.スタック内の最小要素を求める
public class MyStack{
private Stack stackData;
private Stack stackMin;
public MyStack(){
this.stackData=new Stack();
this.stackMin=new Stack();
}
public void push(int newNum){
if(this.stackMin.isEmpty){
this.stackMin.push(newNum);
}else if(newNum<=this.getMin()){
this.stackMin.push(newNum);
}
this.stackData.push(newNum);
}
public int pop(){
if(this.stackData.isEmpty){
throw new RuntimeException("Your stack is empty");
}
int value=this.stackData.pop();
if(value==this.getMin()){
this.stackMin.pop();
}
return value;
}
public int getMin(){
if(this.stackMin.isEmpty()){
throw new RuntimeException("Your stack is empty");
}
return this.stackMin.peek();
}
}
4.2つのスタックシミュレーションキュー
public class MyQueue{
private Stack s1=new Stack();
private Stack s2=new Stack();
public sychronized void put(E e){
s1.push(e);
}
public sychronized void pop(){
if(s2.isEmpty()){
while(!s1.isEmpty()){
s2.push(s1.pop());
}
}
return s2.pop();
}
public sychronized boolean empty(){
return s1.isEmpty()&&s2.isEmpty();
}
}
5.あるスタックが別のスタックのポップアップ順序であるかどうかを判断する
public boolean IsPopOrder(int[] pushA,int[] popA){
if(pushA==null||popA==null){
return false;
}
Stack stack=new Stack<>();
int index=0;
for(int i=0;i