Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- getMinimum()
- Real stack Min stack
- 5 --> TOP 1
- 1 1
- 4 2
- 6 2
- 2 2
- Real stack Min stack
- 4 2
- 6 2
- 2 2
- Real stack Min stack
- 1 --> TOP 1
- 5 1
- 1 2
- 4
- 6
- 2
- Real stack Min stack
- 5 --> TOP 1
- 1 2
- 4
- 6
- 2
- Real stack Min stack
- 1 1
- 4 2
- 6
- 2
- Real stack Min stack
- 4 2
- 6
- 2
- using System.Collections.Generic;
- public class FastMinStack<T>
- {
- private readonly Stack<T> stack = new Stack<T>();
- // Could pass this in to the constructor
- private readonly IComparer<T> comparer = Comparer<T>.Default;
- private T currentMin;
- public T Minimum
- {
- get { return currentMin; }
- }
- public void Push(T element)
- {
- if (stack.Count == 0 ||
- comparer.Compare(element, currentMin) <= 0)
- {
- stack.Push(currentMin);
- stack.Push(element);
- currentMin = element;
- }
- else
- {
- stack.Push(element);
- }
- }
- public T Pop()
- {
- T ret = stack.Pop();
- if (comparer.Compare(ret, currentMin) == 0)
- {
- currentMin = stack.Pop();
- }
- return ret;
- }
- }
- public sealed class MinStack {
- private int MinimumValue;
- private readonly Stack<int> Stack = new Stack<int>();
- public int GetMinimum() {
- if (IsEmpty) {
- throw new InvalidOperationException("Stack is empty");
- }
- return MinimumValue;
- }
- public int Pop() {
- var value = Stack.Pop();
- if (value == MinimumValue) {
- MinimumValue = Stack.Min();
- }
- return value;
- }
- public void Push(int value) {
- if (IsEmpty || value < MinimumValue) {
- MinimumValue = value;
- }
- Stack.Push(value);
- }
- private bool IsEmpty { get { return Stack.Count() == 0; } }
- }
- public class StackWithMin {
- int min;
- int size;
- int[] data = new int[1024];
- public void push ( int val ) {
- if ( size == 0 ) {
- data[size] = val;
- min = val;
- } else if ( val < min) {
- data[size] = 2 * val - min;
- min = val;
- assert (data[size] < min);
- } else {
- data[size] = val;
- }
- ++size;
- // check size and grow array
- }
- public int getMin () {
- return min;
- }
- public int pop () {
- --size;
- int val = data[size];
- if ( ( size > 0 ) && ( val < min ) ) {
- int prevMin = min;
- min += min - val;
- return prevMin;
- } else {
- return val;
- }
- }
- public boolean isEmpty () {
- return size == 0;
- }
- public static void main (String...args) {
- StackWithMin stack = new StackWithMin();
- for ( String arg: args )
- stack.push( Integer.parseInt( arg ) );
- while ( ! stack.isEmpty() ) {
- int min = stack.getMin();
- int val = stack.pop();
- System.out.println( val + " " + min );
- }
- System.out.println();
- }
- }
- public class LinkedStackWithMin {
- private static class Link {
- final int value;
- final Link next;
- Link ( int value, Link next ) {
- this.value = value;
- this.next = next;
- }
- int pop ( LinkedStackWithMin stack ) {
- stack.top = next;
- return value;
- }
- }
- private static class MinLink extends Link {
- MinLink ( int value, Link next ) {
- super( value, next );
- }
- int pop ( LinkedStackWithMin stack ) {
- stack.top = next;
- int prevMin = stack.min;
- stack.min = value;
- return prevMin;
- }
- }
- Link top;
- int min;
- public LinkedStackWithMin () {
- }
- public void push ( int val ) {
- if ( ( top == null ) || ( val < min ) ) {
- top = new MinLink(min, top);
- min = val;
- } else {
- top = new Link(val, top);
- }
- }
- public int pop () {
- return top.pop(this);
- }
- public int getMin () {
- return min;
- }
- public boolean isEmpty () {
- return top == null;
- }
- typedef struct _stack_link stack_with_min;
- typedef struct _stack_link stack_link;
- struct _stack_link {
- size_t next;
- int value;
- };
- stack_link* get_next ( stack_link* link )
- {
- return ( stack_link * )( link -> next & ~ ( size_t ) 1 );
- }
- bool is_min ( stack_link* link )
- {
- return ( link -> next & 1 ) ! = 0;
- }
- void push ( stack_with_min* stack, int value )
- {
- stack_link *link = malloc ( sizeof( stack_link ) );
- link -> next = ( size_t ) stack -> next;
- if ( (stack -> next == 0) || ( value == stack -> value ) ) {
- link -> value = stack -> value;
- link -> next |= 1; // mark as min
- } else {
- link -> value = value;
- }
- stack -> next = link;
- }
- etc.;
- public class MinStack {
- long min;
- Stack<Long> stack;
- public MinStack(){
- stack = new Stack<>();
- }
- public void push(int x) {
- if (stack.isEmpty()) {
- stack.push(0L);
- min = x;
- } else {
- stack.push(x - min); //Could be negative if min value needs to change
- if (x < min) min = x;
- }
- }
- public int pop() {
- if (stack.isEmpty()) return;
- long pop = stack.pop();
- if (pop < 0) {
- long ret = min
- min = min - pop; //If negative, increase the min value
- return (int)ret;
- }
- return (int)(pop + min);
- }
- public int top() {
- long top = stack.peek();
- if (top < 0) {
- return (int)min;
- } else {
- return (int)(top + min);
- }
- }
- public int getMin() {
- return (int)min;
- }
- }
- class StackDemo
- {
- int[] stk = new int[100];
- int top;
- public StackDemo()
- {
- top = -1;
- }
- public void Push(int value)
- {
- if (top == 100)
- Console.WriteLine("Stack Overflow");
- else
- stk[++top] = value;
- }
- public bool IsEmpty()
- {
- if (top == -1)
- return true;
- else
- return false;
- }
- public int Pop()
- {
- if (IsEmpty())
- {
- Console.WriteLine("Stack Underflow");
- return 0;
- }
- else
- return stk[top--];
- }
- public void Display()
- {
- for (int i = top; i >= 0; i--)
- Console.WriteLine(stk[i]);
- }
- }
- class MinStack : StackDemo
- {
- int top;
- int[] stack = new int[100];
- StackDemo s1; int min;
- public MinStack()
- {
- top = -1;
- s1 = new StackDemo();
- }
- public void PushElement(int value)
- {
- s1.Push(value);
- if (top == 100)
- Console.WriteLine("Stack Overflow");
- if (top == -1)
- {
- stack[++top] = value;
- stack[++top] = value;
- }
- else
- {
- // stack[++top]=value;
- int ele = PopElement();
- stack[++top] = ele;
- int a = MininmumElement(min, value);
- stack[++top] = min;
- stack[++top] = value;
- stack[++top] = a;
- }
- }
- public int PopElement()
- {
- if (top == -1)
- return 1000;
- else
- {
- min = stack[top--];
- return stack[top--];
- }
- }
- public int PopfromStack()
- {
- if (top == -1)
- return 1000;
- else
- {
- s1.Pop();
- return PopElement();
- }
- }
- public int MininmumElement(int a,int b)
- {
- if (a > b)
- return b;
- else
- return a;
- }
- public int StackTop()
- {
- return stack[top];
- }
- public void DisplayMinStack()
- {
- for (int i = top; i >= 0; i--)
- Console.WriteLine(stack[i]);
- }
- }
- class Program
- {
- static void Main(string[] args)
- {
- MinStack ms = new MinStack();
- ms.PushElement(15);
- ms.PushElement(2);
- ms.PushElement(1);
- ms.PushElement(13);
- ms.PushElement(5);
- ms.PushElement(21);
- Console.WriteLine("Min Stack");
- ms.DisplayMinStack();
- Console.WriteLine("Minimum Element:"+ms.StackTop());
- ms.PopfromStack();
- ms.PopfromStack();
- ms.PopfromStack();
- ms.PopfromStack();
- Console.WriteLine("Min Stack");
- ms.DisplayMinStack();
- Console.WriteLine("Minimum Element:" + ms.StackTop());
- Thread.Sleep(1000000);
- }
- }
- //
- // main.cpp
- // Eighth
- //
- // Created by chaitanya on 4/11/13.
- // Copyright (c) 2013 cbilgika. All rights reserved.
- //
- #include <iostream>
- #include <limits>
- using namespace std;
- struct stack
- {
- int num;
- int minnum;
- }a[100];
- void push(int n,int m,int &top)
- {
- top++;
- if (top>=100) {
- cout<<"Stack Full";
- cout<<endl;
- }
- else{
- a[top].num = n;
- a[top].minnum = m;
- }
- }
- void pop(int &top)
- {
- if (top<0) {
- cout<<"Stack Empty";
- cout<<endl;
- }
- else{
- top--;
- }
- }
- void print(int &top)
- {
- cout<<"Stack: "<<endl;
- for (int j = 0; j<=top ; j++) {
- cout<<"("<<a[j].num<<","<<a[j].minnum<<")"<<endl;
- }
- }
- void get_min(int &top)
- {
- if (top < 0)
- {
- cout<<"Empty Stack";
- }
- else{
- cout<<"Minimum element is: "<<a[top].minnum;
- }
- cout<<endl;
- }
- int main()
- {
- int top = -1,min = numeric_limits<int>::min(),num;
- cout<<"Enter the list to push (-1 to stop): ";
- cin>>num;
- while (num!=-1) {
- if (top == -1) {
- min = num;
- push(num, min, top);
- }
- else{
- if (num < min) {
- min = num;
- }
- push(num, min, top);
- }
- cin>>num;
- }
- print(top);
- get_min(top);
- return 0;
- }
- Enter the list to push (-1 to stop): 5
- 1
- 4
- 6
- 2
- -1
- Stack:
- (5,5)
- (1,1)
- (4,1)
- (6,1)
- (2,1)
- Minimum element is: 1
- package com.java.util.collection.advance.datastructure;
- /**
- *
- * @author vsinha
- *
- */
- public abstract interface Stack<E> {
- /**
- * Placing a data item on the top of the stack is called pushing it
- * @param element
- *
- */
- public abstract void push(E element);
- /**
- * Removing it from the top of the stack is called popping it
- * @return the top element
- */
- public abstract E pop();
- /**
- * Get it top element from the stack and it
- * but the item is not removed from the stack, which remains unchanged
- * @return the top element
- */
- public abstract E peek();
- /**
- * Get the current size of the stack.
- * @return
- */
- public abstract int size();
- /**
- * Check whether stack is empty of not.
- * @return true if stack is empty, false if stack is not empty
- */
- public abstract boolean empty();
- }
- package com.java.util.collection.advance.datastructure;
- @SuppressWarnings("hiding")
- public abstract interface MinMaxStack<Integer> extends Stack<Integer> {
- public abstract int min();
- public abstract int max();
- }
- package com.java.util.collection.advance.datastructure;
- import java.util.Arrays;
- /**
- *
- * @author vsinha
- *
- * @param <E>
- */
- public class MyStack<E> implements Stack<E> {
- private E[] elements =null;
- private int size = 0;
- private int top = -1;
- private final static int DEFAULT_INTIAL_CAPACITY = 10;
- public MyStack(){
- // If you don't specify the size of stack. By default, Stack size will be 10
- this(DEFAULT_INTIAL_CAPACITY);
- }
- @SuppressWarnings("unchecked")
- public MyStack(int intialCapacity){
- if(intialCapacity <=0){
- throw new IllegalArgumentException("initial capacity can't be negative or zero");
- }
- // Can't create generic type array
- elements =(E[]) new Object[intialCapacity];
- }
- @Override
- public void push(E element) {
- ensureCapacity();
- elements[++top] = element;
- ++size;
- }
- @Override
- public E pop() {
- E element = null;
- if(!empty()) {
- element=elements[top];
- // Nullify the reference
- elements[top] =null;
- --top;
- --size;
- }
- return element;
- }
- @Override
- public E peek() {
- E element = null;
- if(!empty()) {
- element=elements[top];
- }
- return element;
- }
- @Override
- public int size() {
- return size;
- }
- @Override
- public boolean empty() {
- return size == 0;
- }
- /**
- * Increases the capacity of this <tt>Stack by double of its current length</tt> instance,
- * if stack is full
- */
- private void ensureCapacity() {
- if(size != elements.length) {
- // Don't do anything. Stack has space.
- } else{
- elements = Arrays.copyOf(elements, size *2);
- }
- }
- @Override
- public String toString() {
- return "MyStack [elements=" + Arrays.toString(elements) + ", size="
- + size + ", top=" + top + "]";
- }
- }
- package com.java.util.collection.advance.datastructure;
- /**
- * Time complexity will be O(1) to find min and max in a given stack.
- * @author vsinha
- *
- */
- public class MinMaxStackFinder extends MyStack<Integer> implements MinMaxStack<Integer> {
- private MyStack<Integer> minStack;
- private MyStack<Integer> maxStack;
- public MinMaxStackFinder (int intialCapacity){
- super(intialCapacity);
- minStack =new MyStack<Integer>();
- maxStack =new MyStack<Integer>();
- }
- public void push(Integer element) {
- // Current element is lesser or equal than min() value, Push the current element in min stack also.
- if(!minStack.empty()) {
- if(min() >= element) {
- minStack.push(element);
- }
- } else{
- minStack.push(element);
- }
- // Current element is greater or equal than max() value, Push the current element in max stack also.
- if(!maxStack.empty()) {
- if(max() <= element) {
- maxStack.push(element);
- }
- } else{
- maxStack.push(element);
- }
- super.push(element);
- }
- public Integer pop(){
- Integer curr = super.pop();
- if(curr !=null) {
- if(min() == curr) {
- minStack.pop();
- }
- if(max() == curr){
- maxStack.pop();
- }
- }
- return curr;
- }
- @Override
- public int min() {
- return minStack.peek();
- }
- @Override
- public int max() {
- return maxStack.peek();
- }
- @Override
- public String toString() {
- return super.toString()+"nMinMaxStackFinder [minStack=" + minStack + "n maxStack="
- + maxStack + "]" ;
- }
- }
- // You can use the below program to execute it.
- package com.java.util.collection.advance.datastructure;
- import java.util.Random;
- public class MinMaxStackFinderApp {
- public static void main(String[] args) {
- MinMaxStack<Integer> stack =new MinMaxStackFinder(10);
- Random random =new Random();
- for(int i =0; i< 10; i++){
- stack.push(random.nextInt(100));
- }
- System.out.println(stack);
- System.out.println("MAX :"+stack.max());
- System.out.println("MIN :"+stack.min());
- stack.pop();
- stack.pop();
- stack.pop();
- stack.pop();
- stack.pop();
- System.out.println(stack);
- System.out.println("MAX :"+stack.max());
- System.out.println("MIN :"+stack.min());
- }
- }
- private final LinkedList<E> mainStack = new LinkedList<E>();
- private final LinkedList<E> minStack = new LinkedList<E>();
- private final Comparator<E> comparator;
- public MinStack(Comparator<E> comparator)
- {
- this.comparator = comparator;
- }
- /**
- * Pushes an element onto the stack.
- *
- *
- * @param e the element to push
- */
- public void push(E e) {
- mainStack.push(e);
- if(minStack.isEmpty())
- {
- minStack.push(e);
- }
- else if(comparator.compare(e, minStack.peek())<=0)
- {
- minStack.push(e);
- }
- else
- {
- minStack.push(minStack.peek());
- }
- }
- /**
- * Pops an element from the stack.
- *
- *
- * @throws NoSuchElementException if this stack is empty
- */
- public E pop() {
- minStack.pop();
- return mainStack.pop();
- }
- /**
- * Returns but not remove smallest element from the stack. Return null if stack is empty.
- *
- */
- public E getMinimum()
- {
- return minStack.peek();
- }
- @Override
- public String toString() {
- StringBuilder sb = new StringBuilder();
- sb.append("Main stack{");
- for (E e : mainStack) {
- sb.append(e.toString()).append(",");
- }
- sb.append("}");
- sb.append(" Min stack{");
- for (E e : minStack) {
- sb.append(e.toString()).append(",");
- }
- sb.append("}");
- sb.append(" Minimum = ").append(getMinimum());
- return sb.toString();
- }
- public static void main(String[] args) {
- MinStack<Integer> st = new MinStack<Integer>(Comparators.INTEGERS);
- st.push(2);
- Assert.assertTrue("2 is min in stack {2}", st.getMinimum().equals(2));
- System.out.println(st);
- st.push(6);
- Assert.assertTrue("2 is min in stack {2,6}", st.getMinimum().equals(2));
- System.out.println(st);
- st.push(4);
- Assert.assertTrue("2 is min in stack {2,6,4}", st.getMinimum().equals(2));
- System.out.println(st);
- st.push(1);
- Assert.assertTrue("1 is min in stack {2,6,4,1}", st.getMinimum().equals(1));
- System.out.println(st);
- st.push(5);
- Assert.assertTrue("1 is min in stack {2,6,4,1,5}", st.getMinimum().equals(1));
- System.out.println(st);
- st.pop();
- Assert.assertTrue("1 is min in stack {2,6,4,1}", st.getMinimum().equals(1));
- System.out.println(st);
- st.pop();
- Assert.assertTrue("2 is min in stack {2,6,4}", st.getMinimum().equals(2));
- System.out.println(st);
- st.pop();
- Assert.assertTrue("2 is min in stack {2,6}", st.getMinimum().equals(2));
- System.out.println(st);
- st.pop();
- Assert.assertTrue("2 is min in stack {2}", st.getMinimum().equals(2));
- System.out.println(st);
- st.pop();
- Assert.assertTrue("null is min in stack {}", st.getMinimum()==null);
- System.out.println(st);
- }
- private final LinkedList<E> mainStack = new LinkedList<E>();
- private final LinkedList<E> minStack = new LinkedList<E>();
- private final Comparator<E> comparator;
- public MinStack(Comparator<E> comparator)
- {
- this.comparator = comparator;
- }
- /**
- * Pushes an element onto the stack.
- *
- *
- * @param e the element to push
- */
- public void push(E e) {
- mainStack.push(e);
- if(minStack.isEmpty())
- {
- minStack.push(e);
- }
- else if(comparator.compare(e, minStack.peek())<=0)
- {
- minStack.push(e);
- }
- else
- {
- minStack.push(minStack.peek());
- }
- }
- /**
- * Pops an element from the stack.
- *
- *
- * @throws NoSuchElementException if this stack is empty
- */
- public E pop() {
- minStack.pop();
- return mainStack.pop();
- }
- /**
- * Returns but not remove smallest element from the stack. Return null if stack is empty.
- *
- */
- public E getMinimum()
- {
- return minStack.peek();
- }
- @Override
- public String toString() {
- StringBuilder sb = new StringBuilder();
- sb.append("Main stack{");
- for (E e : mainStack) {
- sb.append(e.toString()).append(",");
- }
- sb.append("}");
- sb.append(" Min stack{");
- for (E e : minStack) {
- sb.append(e.toString()).append(",");
- }
- sb.append("}");
- sb.append(" Minimum = ").append(getMinimum());
- return sb.toString();
- }
- public static void main(String[] args) {
- MinStack<Integer> st = new MinStack<Integer>(Comparators.INTEGERS);
- st.push(2);
- Assert.assertTrue("2 is min in stack {2}", st.getMinimum().equals(2));
- System.out.println(st);
- st.push(6);
- Assert.assertTrue("2 is min in stack {2,6}", st.getMinimum().equals(2));
- System.out.println(st);
- st.push(4);
- Assert.assertTrue("2 is min in stack {2,6,4}", st.getMinimum().equals(2));
- System.out.println(st);
- st.push(1);
- Assert.assertTrue("1 is min in stack {2,6,4,1}", st.getMinimum().equals(1));
- System.out.println(st);
- st.push(5);
- Assert.assertTrue("1 is min in stack {2,6,4,1,5}", st.getMinimum().equals(1));
- System.out.println(st);
- st.pop();
- Assert.assertTrue("1 is min in stack {2,6,4,1}", st.getMinimum().equals(1));
- System.out.println(st);
- st.pop();
- Assert.assertTrue("2 is min in stack {2,6,4}", st.getMinimum().equals(2));
- System.out.println(st);
- st.pop();
- Assert.assertTrue("2 is min in stack {2,6}", st.getMinimum().equals(2));
- System.out.println(st);
- st.pop();
- Assert.assertTrue("2 is min in stack {2}", st.getMinimum().equals(2));
- System.out.println(st);
- st.pop();
- Assert.assertTrue("null is min in stack {}", st.getMinimum()==null);
- System.out.println(st);
- }
- #include<stdio.h>
- struct stack
- {
- int data;
- int mindata;
- }a[100];
- void push(int *tos,int input)
- {
- if (*tos > 100)
- {
- printf("overflow");
- return;
- }
- (*tos)++;
- a[(*tos)].data=input;
- if (0 == *tos)
- a[*tos].mindata=input;
- else if (a[*tos -1].mindata < input)
- a[*tos].mindata=a[*tos -1].mindata;
- else
- a[*tos].mindata=input;
- }
- int pop(int * tos)
- {
- if (*tos <= -1)
- {
- printf("underflow");
- return -1;
- }
- return(a[(*tos)--].data);
- }
- void display(int tos)
- {
- while (tos > -1)
- {
- printf("%d:%dt",a[tos].data,a[tos].mindata);
- tos--;
- }
- }
- int min(int tos)
- {
- return(a[tos].mindata);
- }
- int main()
- {
- int tos=-1,x,choice;
- while(1)
- {
- printf("press 1-push,2-pop,3-mindata,4-display,5-exit ");
- scanf("%d",&choice);
- switch(choice)
- {
- case 1: printf("enter data to push");
- scanf("%d",&x);
- push(&tos,x);
- break;
- case 2: printf("the poped out data=%d ",pop(&tos));
- break;
- case 3: printf("The min peeped data:%d",min(tos));
- break;
- case 4: printf("The elements of stack n");
- display(tos);
- break;
- default: exit(0);
- }
- }
- struct StackGetMin {
- void push(int x) {
- elements.push(x);
- if (minStack.empty() || x <= minStack.top())
- minStack.push(x);
- }
- bool pop() {
- if (elements.empty()) return false;
- if (elements.top() == minStack.top())
- minStack.pop();
- elements.pop();
- return true;
- }
- bool getMin(int &min) {
- if (minStack.empty()) {
- return false;
- } else {
- min = minStack.top();
- return true;
- }
- }
- stack<int> elements;
- stack<int> minStack;
- };
- struct Node {
- let data: Int
- init(_ d:Int){
- data = d
- }
- }
- struct Stack {
- private var backingStore = [Node]()
- private var minArray = [Int]()
- mutating func push(n:Node) {
- backingStore.append(n)
- minArray.append(n.data)
- minArray.sort(>)
- minArray
- }
- mutating func pop() -> Node? {
- if(backingStore.isEmpty){
- return nil
- }
- let n = backingStore.removeLast()
- var found = false
- minArray = minArray.filter{
- if (!found && $0 == n.data) {
- found = true
- return false
- }
- return true
- }
- return n
- }
- func min() -> Int? {
- return minArray.last
- }
- }
- class MyStackImplementation{
- private final int capacity = 4;
- int min;
- int arr[] = new int[capacity];
- int top = -1;
- public void push ( int val ) {
- top++;
- if(top <= capacity-1){
- if(top == 0){
- min = val;
- arr[top] = val;
- }
- else if(val < min){
- arr[top] = arr[top]+min;
- min = arr[top]-min;
- arr[top] = arr[top]-min;
- }
- else {
- arr[top] = val;
- }
- System.out.println("element is pushed");
- }
- else System.out.println("stack is full");
- }
- public void pop () {
- top--;
- if(top > -1){
- min = arr[top];
- }
- else {min=0; System.out.println("stack is under flow");}
- }
- public int min(){
- return min;
- }
- public boolean isEmpty () {
- return top == 0;
- }
- public static void main(String...s){
- MyStackImplementation msi = new MyStackImplementation();
- msi.push(1);
- msi.push(4);
- msi.push(2);
- msi.push(10);
- System.out.println(msi.min);
- msi.pop();
- msi.pop();
- msi.pop();
- msi.pop();
- msi.pop();
- System.out.println(msi.min);
- }
- }
- class FastStack {
- private static class StackNode {
- private Integer data;
- private StackNode nextMin;
- public StackNode(Integer data) {
- this.data = data;
- }
- public Integer getData() {
- return data;
- }
- public void setData(Integer data) {
- this.data = data;
- }
- public StackNode getNextMin() {
- return nextMin;
- }
- public void setNextMin(StackNode nextMin) {
- this.nextMin = nextMin;
- }
- }
- private LinkedList<StackNode> stack = new LinkedList<>();
- private StackNode currentMin = null;
- public void push(Integer item) {
- StackNode node = new StackNode(item);
- if (currentMin == null) {
- currentMin = node;
- node.setNextMin(null);
- } else if (item < currentMin.getData()) {
- StackNode oldMinNode = currentMin;
- node.setNextMin(oldMinNode);
- currentMin = node;
- }
- stack.addFirst(node);
- }
- public Integer pop() {
- if (stack.isEmpty()) {
- throw new EmptyStackException();
- }
- StackNode node = stack.peek();
- if (currentMin == node) {
- currentMin = node.getNextMin();
- }
- stack.removeFirst();
- return node.getData();
- }
- public Integer getMinimum() {
- if (stack.isEmpty()) {
- throw new NoSuchElementException("Stack is empty");
- }
- return currentMin.getData();
- }
- }
- vector<pair<int,int> >A;
- int sz=0; // to keep track of the size of vector
- class MinStack
- {
- public:
- MinStack()
- {
- A.clear();
- sz=0;
- }
- void push(int x)
- {
- int mn=(sz==0)?x: min(A[sz-1].second,x); //find the minimum value upto this pushed value
- A.push_back(make_pair(x,mn));
- sz++; // increment the size
- }
- void pop()
- {
- if(sz==0) return;
- A.pop_back(); // pop the last inserted element
- sz--; // decrement size
- }
- int top()
- {
- if(sz==0) return -1; // if stack empty return -1
- return A[sz-1].first; // return the top element
- }
- int getMin()
- {
- if(sz==0) return -1;
- return A[sz-1].second; // return the minimum value at sz-1
- }
- };
- **The task can be acheived by creating two stacks:**
- import java.util.Stack;
- /*
- *
- * Find min in stack using O(n) Space Complexity
- */
- public class DeleteMinFromStack {
- void createStack(Stack<Integer> primary, Stack<Integer> minStack, int[] arr) {
- /* Create main Stack and in parallel create the stack which contains the minimum seen so far while creating main Stack */
- primary.push(arr[0]);
- minStack.push(arr[0]);
- for (int i = 1; i < arr.length; i++) {
- primary.push(arr[i]);
- if (arr[i] <= minStack.peek())// Condition to check to push the value in minimum stack only when this urrent value is less than value seen at top of this stack */
- minStack.push(arr[i]);
- }
- }
- int findMin(Stack<Integer> secStack) {
- return secStack.peek();
- }
- public static void main(String args[]) {
- Stack<Integer> primaryStack = new Stack<Integer>();
- Stack<Integer> minStack = new Stack<Integer>();
- DeleteMinFromStack deleteMinFromStack = new DeleteMinFromStack();
- int[] arr = { 5, 5, 6, 8, 13, 1, 11, 6, 12 };
- deleteMinFromStack.createStack(primaryStack, minStack, arr);
- int mimElement = deleteMinFromStack.findMin(primaryStack, minStack);
- /** This check for algorithm when the main Stack Shrinks by size say i as in loop below */
- for (int i = 0; i < 2; i++) {
- primaryStack.pop();
- }
- System.out.println(" Minimum element is " + mimElement);
- }
- }
- /*
- here in have tried to add for loop wherin the main tack can be shrinked/expaned so we can check the algorithm */
- The Code for same is below:
- package com.practical;
- import java.util.Collections;
- import java.util.Iterator;
- import java.util.LinkedList;
- import java.util.List;
- import java.util.Stack;
- public class CognitaStack {
- public School findMin(Stack<School> stack, Stack<School> minStack) {
- if (!stack.empty() && !minStack.isEmpty())
- return (School) minStack.peek();
- return null;
- }
- public School removeSchool(Stack<School> stack, Stack<School> minStack) {
- if (stack.isEmpty())
- return null;
- School temp = stack.peek();
- if (temp != null) {
- // if(temp.compare(stack.peek(), minStack.peek())<0){
- stack.pop();
- minStack.pop();
- // }
- // stack.pop();
- }
- return stack.peek();
- }
- public static void main(String args[]) {
- Stack<School> stack = new Stack<School>();
- Stack<School> minStack = new Stack<School>();
- List<School> lst = new LinkedList<School>();
- School s1 = new School("Polam School", "London", 3);
- School s2 = new School("AKELEY WOOD SENIOR SCHOOL", "BUCKINGHAM", 4);
- School s3 = new School("QUINTON HOUSE SCHOOL", "NORTHAMPTON", 2);
- School s4 = new School("OAKLEIGH HOUSE SCHOOL", " SWANSEA", 5);
- School s5 = new School("OAKLEIGH-OAK HIGH SCHOOL", "Devon", 1);
- School s6 = new School("BritishInter2", "Devon", 7);
- lst.add(s1);
- lst.add(s2);
- lst.add(s3);
- lst.add(s4);
- lst.add(s5);
- lst.add(s6);
- Iterator<School> itr = lst.iterator();
- while (itr.hasNext()) {
- School temp = itr.next();
- if ((minStack.isEmpty()) || (temp.compare(temp, minStack.peek()) < 0)) { // minStack.peek().equals(temp)
- stack.push(temp);
- minStack.push(temp);
- } else {
- minStack.push(minStack.peek());
- stack.push(temp);
- }
- }
- CognitaStack cogStack = new CognitaStack();
- System.out.println(" Minimum in Stack is " + cogStack.findMin(stack, minStack).name);
- cogStack.removeSchool(stack, minStack);
- cogStack.removeSchool(stack, minStack);
- System.out.println(" Minimum in Stack is "
- + ((cogStack.findMin(stack, minStack) != null) ? cogStack.findMin(stack, minStack).name : "Empty"));
- }
- }
- package com.practical;
- import java.util.Comparator;
- public class School implements Comparator<School> {
- String name;
- String location;
- int rank;
- public School(String name, String location, int rank) {
- super();
- this.name = name;
- this.location = location;
- this.rank = rank;
- }
- @Override
- public int hashCode() {
- final int prime = 31;
- int result = 1;
- result = prime * result + ((location == null) ? 0 : location.hashCode());
- result = prime * result + ((name == null) ? 0 : name.hashCode());
- result = prime * result + rank;
- return result;
- }
- @Override
- public boolean equals(Object obj) {
- if (this == obj)
- return true;
- if (obj == null)
- return false;
- if (getClass() != obj.getClass())
- return false;
- School other = (School) obj;
- if (location == null) {
- if (other.location != null)
- return false;
- } else if (!location.equals(other.location))
- return false;
- if (name == null) {
- if (other.name != null)
- return false;
- } else if (!name.equals(other.name))
- return false;
- if (rank != other.rank)
- return false;
- return true;
- }
- public String getName() {
- return name;
- }
- public void setName(String name) {
- this.name = name;
- }
- public String getLocation() {
- return location;
- }
- public void setLocation(String location) {
- this.location = location;
- }
- public int getRank() {
- return rank;
- }
- public void setRank(int rank) {
- this.rank = rank;
- }
- public int compare(School o1, School o2) {
- // TODO Auto-generated method stub
- return o1.rank - o2.rank;
- }
- }
- class SchoolComparator implements Comparator<School> {
- public int compare(School o1, School o2) {
- return o1.rank - o2.rank;
- }
- }
- class Stack {
- private:
- struct stack_node {
- int val;
- stack_node *next;
- };
- stack_node *top;
- stack_node *min_top;
- public:
- Stack() {
- top = nullptr;
- min_top = nullptr;
- }
- void push(int num) {
- stack_node *new_node = nullptr;
- new_node = new stack_node;
- new_node->val = num;
- if (is_empty()) {
- top = new_node;
- new_node->next = nullptr;
- min_top = new_node;
- new_node->next = nullptr;
- } else {
- new_node->next = top;
- top = new_node;
- if (new_node->val <= min_top->val) {
- new_node->next = min_top;
- min_top = new_node;
- }
- }
- }
- void pop(int &num) {
- stack_node *tmp_node = nullptr;
- stack_node *min_tmp = nullptr;
- if (is_empty()) {
- std::cout << "It's emptyn";
- } else {
- num = top->val;
- if (top->val == min_top->val) {
- min_tmp = min_top->next;
- delete min_top;
- min_top = min_tmp;
- }
- tmp_node = top->next;
- delete top;
- top = tmp_node;
- }
- }
- bool is_empty() const {
- return !top;
- }
- void get_min(int &item) {
- item = min_top->val;
- }
- };
- int main() {
- int pop, min_el;
- Stack my_stack;
- my_stack.push(4);
- my_stack.push(6);
- my_stack.push(88);
- my_stack.push(1);
- my_stack.push(234);
- my_stack.push(2);
- my_stack.get_min(min_el);
- cout << "Min: " << min_el << endl;
- my_stack.pop(pop);
- cout << "Popped stock element: " << pop << endl;
- my_stack.pop(pop);
- cout << "Popped stock element: " << pop << endl;
- my_stack.pop(pop);
- cout << "Popped stock element: " << pop << endl;
- my_stack.get_min(min_el);
- cout << "Min: " << min_el << endl;
- return 0;
- }
- Min: 1
- Popped stock element: 2
- Popped stock element: 234
- Popped stock element: 1
- Min: 4
- class MinStackOptimized:
- def __init__(self):
- self.stack = []
- self.min = None
- def push(self, x):
- if not self.stack:
- # stack is empty therefore directly add
- self.stack.append(x)
- self.min = x
- else:
- """
- Directly add (x-self.min) to the stack. This also ensures anytime we have a
- negative number on the stack is when x was less than existing minimum
- recorded thus far.
- """
- self.stack.append(x-self.min)
- if x < self.min:
- # Update x to new min
- self.min = x
- def pop(self):
- x = self.stack.pop()
- if x < 0:
- """
- if popped element was negative therefore this was the minimum
- element, whose actual value is in self.min but stored value is what
- contributes to get the next min. (this is one of the trick we use to ensure
- we are able to get old minimum once current minimum gets popped proof is given
- below in pop method), value stored during push was:
- (x - self.old_min) and self.min = x therefore we need to backtrack
- these steps self.min(current) - stack_value(x) actually implies to
- x (self.min) - (x - self.old_min)
- which therefore gives old_min back and therefore can now be set
- back as current self.min.
- """
- self.min = self.min - x
- def top(self):
- x = self.stack[-1]
- if x < 0:
- """
- As discussed above anytime there is a negative value on stack, this
- is the min value so far and therefore actual value is in self.min,
- current stack value is just for getting the next min at the time
- this gets popped.
- """
- return self.min
- else:
- """
- if top element of the stack was positive then it's simple, it was
- not the minimum at the time of pushing it and therefore what we did
- was x(actual) - self.min(min element at current stage) let's say `y`
- therefore we just need to reverse the process to get the actual
- value. Therefore self.min + y, which would translate to
- self.min + x(actual) - self.min, thereby giving x(actual) back
- as desired.
- """
- return x + self.min
- def getMin(self):
- # Always self.min variable holds the minimum so for so easy peezy.
- return self.min
- public class StackWithMin extends Stack<Integer> {
- private Stack<Integer> min;
- public StackWithMin() {
- min = new Stack<>();
- }
- public void push(int num) {
- if (super.isEmpty()) {
- min.push(num);
- } else if (num <= min.peek()) {
- min.push(num);
- }
- super.push(num);
- }
- public int min() {
- return min.peek();
- }
- public Integer pop() {
- if (super.peek() == min.peek()) {
- min.pop();
- }
- return super.pop();
- }
- }
- public class Stack {
- int[] elements;
- int top;
- Linkedlists min;
- public Stack(int n) {
- elements = new int[n];
- top = 0;
- min = new Linkedlists();
- }
- public void realloc(int n) {
- int[] tab = new int[n];
- for (int i = 0; i < top; i++) {
- tab[i] = elements[i];
- }
- elements = tab;
- }
- public void push(int x) {
- if (top == elements.length) {
- realloc(elements.length * 2);
- }
- if (top == 0) {
- min.pre(x);
- } else if (x < min.head.data) {
- min.pre(x);
- } else {
- min.app(x);
- }
- elements[top++] = x;
- }
- public int pop() {
- int x = elements[--top];
- if (top == 0) {
- }
- if (this.getMin() == x) {
- min.head = min.head.next;
- }
- elements[top] = 0;
- if (4 * top < elements.length) {
- realloc((elements.length + 1) / 2);
- }
- return x;
- }
- public void display() {
- for (Object x : elements) {
- System.out.print(x + " ");
- }
- }
- public int getMin() {
- if (top == 0) {
- return 0;
- }
- return this.min.head.data;
- }
- public static void main(String[] args) {
- Stack stack = new Stack(4);
- stack.push(2);
- stack.push(3);
- stack.push(1);
- stack.push(4);
- stack.push(5);
- stack.pop();
- stack.pop();
- stack.pop();
- stack.push(1);
- stack.pop();
- stack.pop();
- stack.pop();
- stack.push(2);
- System.out.println(stack.getMin());
- stack.display();
- }
- }
- class Stack{
- int min;
- Node top;
- static class Node{
- private int data;
- private Node next;
- private int min;
- Node(int data, int min){
- this.data = data;
- this.min = min;
- this.next = null;
- }
- }
- void push(int data){
- Node temp;
- if(top == null){
- temp = new Node(data,data);
- top = temp;
- top.min = data;
- }
- if(top.min > data){
- temp = new Node(data,data);
- temp.next = top;
- top = temp;
- } else {
- temp = new Node(data, top.min);
- temp.next = top;
- top = temp;
- }
- }
- void pop(){
- if(top != null){
- top = top.next;
- }
- }
- int min(){
- return top.min;
- }
- /*
- * Implementation of Stack that can give minimum in O(1) time all the time
- * This solution uses same data structure for minimum variable, it could be implemented using pointers but that will be more space consuming
- */
- #include <iostream>
- using namespace std;
- typedef struct stackLLNodeType stackLLNode;
- struct stackLLNodeType {
- int item;
- int min;
- stackLLNode *next;
- };
- class DynamicStack {
- private:
- int stackSize;
- stackLLNode *top;
- public:
- DynamicStack();
- ~DynamicStack();
- void push(int x);
- int pop();
- int getMin();
- int size() { return stackSize; }
- };
- void pushOperation(DynamicStack& p_stackObj, int item);
- void popOperation(DynamicStack& p_stackObj);
- int main () {
- DynamicStack stackObj;
- pushOperation(stackObj, 3);
- pushOperation(stackObj, 1);
- pushOperation(stackObj, 2);
- popOperation(stackObj);
- popOperation(stackObj);
- popOperation(stackObj);
- popOperation(stackObj);
- pushOperation(stackObj, 4);
- pushOperation(stackObj, 7);
- pushOperation(stackObj, 6);
- popOperation(stackObj);
- popOperation(stackObj);
- popOperation(stackObj);
- popOperation(stackObj);
- return 0;
- }
- DynamicStack::DynamicStack() {
- // initialization
- stackSize = 0;
- top = NULL;
- }
- DynamicStack::~DynamicStack() {
- stackLLNode* tmp;
- // chain memory deallocation to avoid memory leak
- while (top) {
- tmp = top;
- top = top->next;
- delete tmp;
- }
- }
- void DynamicStack::push(int x) {
- // allocate memory for new node assign to top
- if (top==NULL) {
- top = new stackLLNode;
- top->item = x;
- top->next = NULL;
- top->min = top->item;
- }
- else {
- // allocation of memory
- stackLLNode *tmp = new stackLLNode;
- // assign the new item
- tmp->item = x;
- tmp->next = top;
- // store the minimum so that it does not get lost after pop operation of later minimum
- if (x < top->min)
- tmp->min = x;
- else
- tmp->min = top->min;
- // update top to new node
- top = tmp;
- }
- stackSize++;
- }
- int DynamicStack::pop() {
- // check if stack is empty
- if (top == NULL)
- return -1;
- stackLLNode* tmp = top;
- int curItem = top->item;
- top = top->next;
- delete tmp;
- stackSize--;
- return curItem;
- }
- int DynamicStack::getMin() {
- if (top == NULL)
- return -1;
- return top->min;
- }
- void pushOperation(DynamicStack& p_stackObj, int item) {
- cout<<"Just pushed: "<<item<<endl;
- p_stackObj.push(item);
- cout<<"Current stack min: "<<p_stackObj.getMin()<<endl;
- cout<<"Current stack size: "<<p_stackObj.size()<<endl<<endl;
- }
- void popOperation(DynamicStack& p_stackObj) {
- int popItem = -1;
- if ((popItem = p_stackObj.pop()) == -1 )
- cout<<"Cannot pop. Stack is empty."<<endl;
- else {
- cout<<"Just popped: "<<popItem<<endl;
- if (p_stackObj.getMin() == -1)
- cout<<"No minimum. Stack is empty."<<endl;
- else
- cout<<"Current stack min: "<<p_stackObj.getMin()<<endl;
- cout<<"Current stack size: "<<p_stackObj.size()<<endl<<endl;
- }
- }
- Just pushed: 3
- Current stack min: 3
- Current stack size: 1
- Just pushed: 1
- Current stack min: 1
- Current stack size: 2
- Just pushed: 2
- Current stack min: 1
- Current stack size: 3
- Just popped: 2
- Current stack min: 1
- Current stack size: 2
- Just popped: 1
- Current stack min: 3
- Current stack size: 1
- Just popped: 3
- No minimum. Stack is empty.
- Current stack size: 0
- Cannot pop. Stack is empty.
- Just pushed: 4
- Current stack min: 4
- Current stack size: 1
- Just pushed: 7
- Current stack min: 4
- Current stack size: 2
- Just pushed: 6
- Current stack min: 4
- Current stack size: 3
- Just popped: 6
- Current stack min: 4
- Current stack size: 2
- Just popped: 7
- Current stack min: 4
- Current stack size: 1
- Just popped: 4
- No minimum. Stack is empty.
- Current stack size: 0
- Cannot pop. Stack is empty.
- public interface IMinStack<T extends Comparable<T>> {
- public void push(T val);
- public T pop();
- public T minValue();
- public int size();
- }
- import java.util.Stack;
- public class MinStack<T extends Comparable<T>> implements IMinStack<T> {
- private Stack<T> stack = new Stack<T>();
- private Stack<T> minStack = new Stack<T>();
- @Override
- public void push(T val) {
- stack.push(val);
- if (minStack.isEmpty() || val.compareTo(minStack.peek()) < 0)
- minStack.push(val);
- }
- @Override
- public T pop() {
- T val = stack.pop();
- if ((false == minStack.isEmpty())
- && val.compareTo(minStack.peek()) == 0)
- minStack.pop();
- return val;
- }
- @Override
- public T minValue() {
- return minStack.peek();
- }
- @Override
- public int size() {
- return stack.size();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement