implemented it based on juver++ & zhang. I think both stacks need to
provide get_min functionality...
class MyQueue{
private ItemStack pushstack;
private ItemStack popstack;
class Item{
int val;
int min;
public Item(int val,int min){
this.val = val;
this.min = min;
}
}
class ItemStack extends Stack{
public void push(int val){
if(this.isEmpty()){
super.push(new Item(val,val));
}else{
Item oneItem = this.peek();
if(val>oneItem.min){
super.push(new Item(val,oneItem.min));
}else{
super.push(new Item(val,val));
}
}
}
@Override
public Item peek(){
return (Item)super.peek();
}
@Override
public Item pop(){
return (Item)super.pop();
}
}
public MyQueue(){
pushstack = new ItemStack();
popstack = new ItemStack();
}
public void push_rear(int value){
pushstack.push(value);
}
public int pop_front(){
if(popstack.isEmpty()){
while(!pushstack.isEmpty()){
int value = pushstack.pop().val;
popstack.push(value);
}
}
return popstack.pop().val;
}
public int get_min(){
if(!pushstack.isEmpty() && !popstack.isEmpty()){
return Math.min(popstack.peek().min,
pushstack.peek().min);
}else if(pushstack.isEmpty() && popstack.isEmpty()){
throw new EmptyStackException();
}else if(!pushstack.isEmpty()){
return pushstack.peek().min;
}else{
return popstack.peek().min;
}
}
}
On Jan 2, 12:23 am, sourav <[email protected]> wrote:
> Implement a queue in which push_rear(), pop_front() and get_min() are
> all constant time operations.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
