Entcasting Sie einen Stapel so, dass getMinimum () O (1) sein sollte

Dies ist eine der Fragen eines Interviews. Sie müssen einen Stapel entcasting, der einen ganzzahligen Wert enthält, sodass die function getMinimum () das Mindestelement im Stapel zurückgeben soll.

Zum Beispiel: Betrachten Sie das folgende Beispiel

 Fall 1

 5 -> TOP
 1
 4
 6
 2

 Wenn getMinimum () aufgerufen wird, sollte 1 zurückgegeben werden, was das minimale Element ist 
 im Stapel. 

 Fall # 2

 stack.pop ()
 stack.pop ()

 Hinweis: Sowohl 5 als auch 1 werden aus dem Stapel ausgeblendet.  Also danach der Stapel
 sieht aus wie,

 4 -> TOP
 6
 2

 Wenn getMinimum () aufgerufen wird, sollte es 2 zurückgeben, das ist das Minimum in der 
 Stapel.

Contrients:

  1. getMinimum sollte den Minimalwert in O (1) zurückgeben
  2. Die Raumbeschränkung muss auch berücksichtigt werden, wenn Sie sie entcasting, und wenn Sie zusätzlichen Raum verwenden, sollte sie konstanten Raum haben.

EDIT: Dies scheitert die “Constant Space” Einschränkung – es verdoppelt im Grunde den benötigten Speicherplatz. Ich bezweifle sehr, dass es eine Lösung gibt, die das nicht tut, ohne die Laufzeitkomplexität irgendwo zu zerstören (zB push / pop O (n) machen). Beachten Sie, dass dies die Komplexität des benötigten Platzes nicht ändert, zB wenn Sie einen Stack mit O (n) Platzbedarf haben, ist dies immer noch O (n) nur mit einem anderen konstanten Faktor.

Nicht-Konstanten-Raum-Lösung

Behalte einen “doppelten” Stapel von “Minimum aller Werte im Stapel unten”. Wenn du den Hauptstapel platzierst, öffne den Min-Stapel ebenfalls. Wenn Sie den Hauptstapel drücken, drücken Sie entweder das neue Element oder die aktuelle Min., Je nachdem, welcher Wert niedriger ist. getMinimum() wird dann als nur minStack.peek() implementiert.

Mit Ihrem Beispiel hätten wir:

 Real stack Min stack 5 --> TOP 1 1 1 4 2 6 2 2 2 

Nachdem du zweimal gepoppt hast, bekommst du:

 Real stack Min stack 4 2 6 2 2 2 

Bitte lassen Sie mich wissen, wenn das nicht genug Informationen sind. Es ist einfach, wenn Sie es grok, aber es könnte ein bisschen Kopf kratzen erstens 🙂

(Der Nachteil ist natürlich, dass es den Platzbedarf verdoppelt. Die Ausführungszeit leidet jedoch nicht signifikant – dh es ist immer noch die gleiche Komplexität.)

EDIT: Es gibt eine Variante, die etwas fummeliger ist, aber im Allgemeinen einen besseren Platz hat. Wir haben immer noch den Min-Stack, aber wir machen nur dann einen Pop-Up, wenn der Wert, den wir vom Main-Stack bekommen, dem Wert auf dem Minimum-Stack entspricht. Wir schieben nur auf den Min-Stack, wenn der Wert, der auf den Main-Stack geschoben wird, kleiner oder gleich dem aktuellen Min-Wert ist. Dies ermöglicht doppelte Minwerte. getMinimum() ist immer noch eine Peek-Operation. Wenn wir zum Beispiel die ursprüngliche Version nehmen und 1 erneut drücken, bekommen wir:

 Real stack Min stack 1 --> TOP 1 5 1 1 2 4 6 2 

Popping aus den oben genannten Pops von beiden Stacks, weil 1 == 1, so dass:

 Real stack Min stack 5 --> TOP 1 1 2 4 6 2 

Das erneute Poppen erscheint nur vom Hauptstapel, weil 5> 1:

 Real stack Min stack 1 1 4 2 6 2 

Durch erneutes Aufspringen werden beide Stapel wieder geöffnet, weil 1 == 1:

 Real stack Min stack 4 2 6 2 

Dies führt zu der gleichen Komplexität des Worst-Case-Platzes (das Doppelte des ursprünglichen Stacks), aber zu einer viel besseren Platznutzung, wenn wir selten ein “neues Minimum oder gleich” erhalten.

EDIT: Hier ist eine Implementierung von Pete’s bösen Schema. Ich habe es nicht gründlich getestet, aber ich denke, es ist in Ordnung 🙂

 using System.Collections.Generic; public class FastMinStack { private readonly Stack stack = new Stack(); // Could pass this in to the constructor private readonly IComparer comparer = Comparer.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; } } 

Fügen Sie ein Feld hinzu, das den Minimalwert enthält, und aktualisieren Sie es während Pop () und Push (). Auf diese Weise wird getMinimum () O (1) sein, aber Pop () und Push () müssen etwas mehr arbeiten.

Wenn minimaler Wert ausgegeben wird, ist Pop () O (n), andernfalls sind sie immer noch O (1). Bei der Größenänderung wird Push () zu O (n) gemäß der Stack-Implementierung.

Hier ist eine schnelle Implementierung

 public sealed class MinStack { private int MinimumValue; private readonly Stack Stack = new Stack(); 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(); } } 

Es speichert das aktuelle Minimum explizit, und wenn das Minimum sich ändert, drückt es einen Wert auf die andere Seite des neuen Minimums (wenn min = 7 und du drückst 5, drückt es stattdessen auf 3 | 7-5 | = 3) und setzt min auf 5, wenn Sie dann 3 drücken, wenn min 5 ist, sieht er, dass der gedrückte Wert kleiner als min ist, kehrt also die Prozedur um, um 7 für die neue min zu erhalten, und gibt dann die vorherige zurück Mindest). Da jeder Wert, der keine Änderung verursacht, das aktuelle Minimum größer als das aktuelle Minimum ist, haben Sie etwas, das verwendet werden kann, um zwischen Werten, die das Minimum ändern, und solchen, die dies nicht ändern, zu unterscheiden.

In Sprachen, die Ganzzahlen fester Größe verwenden, leihen Sie etwas Platz aus der Repräsentation der Werte, so dass es unterlaufen kann und die Assert fehlschlägt. Aber sonst ist es ständig mehr Platz und alle Operationen sind immer noch O (1).

Stapel, die stattdessen auf verketteten Listen basieren, haben andere Stellen, an denen Sie etwas ausleihen können, z. B. in C das niedrigstwertige Bit des nächsten pointerss oder in Java der Typ der Objekte in der verknüpften Liste. Für Java bedeutet dies, dass im Vergleich zu einem zusammenhängenden Stapel mehr Platz benötigt wird, da Sie den Objekt-Overhead pro Link haben:

 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; } 

In C ist der Overhead nicht vorhanden, und Sie können den LSB des nächsten pointerss ausleihen:

 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.; 

Keines davon ist jedoch wirklich O (1). Sie benötigen in der Praxis keinen Platz mehr, da sie Löcher in den Darstellungen von Zahlen, Objekten oder pointersn in diesen Sprachen ausnutzen. Aber eine theoretische Maschine, die eine kompaktere Darstellung verwendet, würde erfordern, dass zu dieser Darstellung in jedem Fall ein zusätzliches Bit hinzugefügt wird.

Ich fand eine Lösung, die alle genannten Einschränkungen (konstante Zeitoperationen) und konstanten zusätzlichen Platz erfüllt.

Die Idee besteht darin, die Differenz zwischen dem Minimalwert und der Eingangsnummer zu speichern und den Minimalwert zu aktualisieren, wenn dieser nicht mehr das Minimum ist.

Der Code ist wie folgt:

 public class MinStack { long min; Stack 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; } } 

Der Kredit geht an: https://leetcode.com/discuss/15679/share-my-java-solution-with-only-one-stack

Nun, was sind die Laufzeitbeschränkungen von push und pop ? Wenn es nicht erforderlich ist, dass sie konstant sind, dann berechne einfach den minimalen Wert in diesen zwei Operationen (mache sie zu O ( n )). Ansonsten sehe ich nicht, wie dies mit konstantem zusätzlichen Platz gemacht werden kann.

Hier ist mein Code, der mit O (1) läuft. Der vorherige Code, den ich gepostet habe, hatte ein Problem, wenn das minimale Element gepoppt wurde. Ich habe meinen Code geändert. Dieser verwendet einen anderen Stapel, der das minimale Element im Stapel über dem aktuell gedrückten Element hält.

  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); } } 

Ich habe einen anderen Stapel benutzt. Hier ist die Implementierung.

 // // main.cpp // Eighth // // Created by chaitanya on 4/11/13. // Copyright (c) 2013 cbilgika. All rights reserved. // #include  #include  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<::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; } 

Ausgabe:

 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 

Versuch es. Ich denke, es beantwortet die Frage. Das zweite Element jedes Paares gibt den Mindestwert an, der beim Einfügen des Elements angezeigt wurde.

Ich poste hier den kompletten Code, um min und max in einem gegebenen Stapel zu finden.

Die Zeitkomplexität wird O (1) sein.

 package com.java.util.collection.advance.datastructure; /** * * @author vsinha * */ public abstract interface Stack { /** * 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 extends Stack { public abstract int min(); public abstract int max(); } package com.java.util.collection.advance.datastructure; import java.util.Arrays; /** * * @author vsinha * * @param  */ public class MyStack implements Stack { 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 Stack by double of its current length 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 implements MinMaxStack { private MyStack minStack; private MyStack maxStack; public MinMaxStackFinder (int intialCapacity){ super(intialCapacity); minStack =new MyStack(); maxStack =new MyStack(); } 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 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()); } } 

Lassen Sie es mich wissen, wenn Sie Probleme haben

Danke, Vikash

Sie könnten Ihre ursprüngliche Stack-class erweitern und einfach die Min-Tracking hinzufügen. Lassen Sie die ursprüngliche Elternklasse alles andere wie gewohnt behandeln.

 public class StackWithMin extends Stack { private Stack 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(); } } 

Hier ist meine Lösung in Java mit liked Liste.

 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; } 

}

Hier ist meine Version der Implementierung.

  Struktur MyStack {
     int Element;
     int * AktuelleMiniAddress;
  };

  void Push (int Wert)
  {
     // Erstellen Sie Ihre Struktur und füllen Sie den Wert
     MyStack S = neuer MyStack ();
     S-> Element = Wert;

     if (Stapel.Empty ())
     {    
         // Da der Stapel leer ist, zeigen Sie CurrentMiniAddress auf sich selbst
         S-> CurrentMiniAddress = S;

     }
     sonst
     {
          // Stapel ist nicht leer

          // Abrufen des obersten Elements.  Kein Pop ()
          MyStack * TopElement = Stack.Top ();

          // Remember Immer das TOP-Element zeigt auf die
          // minimales Element im gesamten Stack
          if (S-> Element CurrentMiniAddress-> Element)
          {
             // Wenn der aktuelle Wert das Minimum im gesamten Stapel ist
             // dann zeigt S auf sich selbst
             S-> CurrentMiniAddress = S;
          }
              sonst
              {
                  // Das ist also nicht das Minimum im gesamten Stack
                  // Keine Sorge, TOP hält das minimale Element
                  S-> CurrentMiniAddress = TopElement-> CurrentMiniAddress;
              }

     }
         Stapel.Zug (S);
  }

  void Pop ()
  {
      if (! Stapel.Empty ())
      {
         Stapel.Pop ();
      }  
  }

  int GetMinimum (Stapel & Stapel)
  {
        if (! stack.Empty ())
        {
             MyStack * Oben = stack.top ();
             // Top zeigt immer auf das Minimumx
             Zurück Top-> CurrentMiniAddress-> Element;
         }
  }
 #include 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:%d\t",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); } } 

Ich habe diese Lösung hier gefunden

 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 elements; stack 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 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(); } } 

Hier ist mein Code, der mit O (1) läuft. Hier verwendete ich Vektorpaare, die den Wert enthalten, der gedrückt wurde, und auch den Minimalwert bis zu diesem gedrückten Wert.

Hier ist meine Version von C ++ Implementierung.

 vector >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 primary, Stack 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 secStack) { return secStack.peek(); } public static void main(String args[]) { Stack primaryStack = new Stack(); Stack minStack = new Stack(); 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 */ 

Eine praktische Implementierung, um das Minimum in einem Stapel benutzerdefinierter Objekte mit dem Namen Schule zu finden

Der Stack wird die Schulen im Stapel speichern, basierend auf dem Rang, der einer Schule in einer bestimmten Region zugewiesen wird, zB findMin () gibt der Schule, wo wir die maximale Anzahl von Anmeldungen erhalten, die wiederum von der Komparator, der Rang verwendet, der mit den Schulen in der vorherigen Jahreszeit verbunden ist.

 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 stack, Stack minStack) { if (!stack.empty() && !minStack.isEmpty()) return (School) minStack.peek(); return null; } public School removeSchool(Stack stack, Stack 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 stack = new Stack(); Stack minStack = new Stack(); List lst = new LinkedList(); 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 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")); } } 

Auch das Schulobjekt ist wie folgt:

 package com.practical; import java.util.Comparator; public class School implements Comparator { 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 { public int compare(School o1, School o2) { return o1.rank - o2.rank; } } 

Dieses Beispiel deckt folgendes ab: 1. Implementierung eines Stacks für benutzerdefinierte Objekte, hier, Schule 2. Implementierung für die Hashcode () und equals () Methode unter Verwendung aller Felder von zu vergleichenden Objekten 3. Eine praktische Implementierung für das Szenario, in dem wir rqeuire, um den Stapel zu erhalten, enthält die Operation in der Reihenfolge von O (1)

Here’s the PHP implementation of what explained in Jon Skeet’s answer as the slightly better space complexity implementation to get the maximum of stack in O(1).

 < ?php /** * An ordinary stack implementation. * * In real life we could just extend the built-in "SplStack" class. */ class BaseIntegerStack { /** * Stack main storage. * * @var array */ private $storage = []; // ------------------------------------------------------------------------ // Public API // ------------------------------------------------------------------------ /** * Pushes to stack. * * @param int $value New item. * * @return bool */ public function push($value) { return is_integer($value) ? (bool) array_push($this->storage, $value) : false; } /** * Pops an element off the stack. * * @return int */ public function pop() { return array_pop($this->storage); } /** * See what's on top of the stack. * * @return int|bool */ public function top() { return empty($this->storage) ? false : end($this->storage); } // ------------------------------------------------------------------------ // Magic methods // ------------------------------------------------------------------------ /** * String representation of the stack. * * @return string */ public function __toString() { return implode('|', $this->storage); } } // End of BaseIntegerStack class /** * The stack implementation with getMax() method in O(1). */ class Stack extends BaseIntegerStack { /** * Internal stack to keep track of main stack max values. * * @var BaseIntegerStack */ private $maxStack; /** * Stack class constructor. * * Dependencies are injected. * * @param BaseIntegerStack $stack Internal stack. * * @return void */ public function __construct(BaseIntegerStack $stack) { $this->maxStack = $stack; } // ------------------------------------------------------------------------ // Public API // ------------------------------------------------------------------------ /** * Prepends an item into the stack maintaining max values. * * @param int $value New item to push to the stack. * * @return bool */ public function push($value) { if ($this->isNewMax($value)) { $this->maxStack->push($value); } parent::push($value); } /** * Pops an element off the stack maintaining max values. * * @return int */ public function pop() { $popped = parent::pop(); if ($popped == $this->maxStack->top()) { $this->maxStack->pop(); } return $popped; } /** * Finds the maximum of stack in O(1). * * @return int * @see push() */ public function getMax() { return $this->maxStack->top(); } // ------------------------------------------------------------------------ // Internal helpers // ------------------------------------------------------------------------ /** * Checks that passing value is a new stack max or not. * * @param int $new New integer to check. * * @return boolean */ private function isNewMax($new) { return empty($this->maxStack) OR $new > $this->maxStack->top(); } } // End of Stack class // ------------------------------------------------------------------------ // Stack Consumption and Test // ------------------------------------------------------------------------ $stack = new Stack( new BaseIntegerStack ); $stack->push(9); $stack->push(4); $stack->push(237); $stack->push(5); $stack->push(556); $stack->push(15); print "Stack: $stack\n"; print "Max: {$stack->getMax()}\n\n"; print "Pop: {$stack->pop()}\n"; print "Pop: {$stack->pop()}\n\n"; print "Stack: $stack\n"; print "Max: {$stack->getMax()}\n\n"; print "Pop: {$stack->pop()}\n"; print "Pop: {$stack->pop()}\n\n"; print "Stack: $stack\n"; print "Max: {$stack->getMax()}\n"; // Here's the sample output: // // Stack: 9|4|237|5|556|15 // Max: 556 // // Pop: 15 // Pop: 556 // // Stack: 9|4|237|5 // Max: 237 // // Pop: 5 // Pop: 237 // // Stack: 9|4 // Max: 9 

Here is the C++ implementation of Jon Skeets Answer . It might not be the most optimal way of implementing it, but it does exactly what it’s supposed to.

 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 empty\n"; } 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; } }; 

And here is the driver for the class

 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; } 

Ausgabe:

 Min: 1 Popped stock element: 2 Popped stock element: 234 Popped stock element: 1 Min: 4 

We can do this in O(n) time and O(1) space complexity, like so:

 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 

I think you can simply use a LinkedList in your stack implementation.

First time you push a value, you put this value as the linkedlist head.

then each time you push a value, if the new value < head.data, make a prepand operation ( which means the head becomes the new value )

if not, then make an append operation.

When you make a pop(), you check if min == linkedlist.head.data, if yes, then head=head.next;

Hier ist mein Code.

 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(); } } 
 public class MinStack{ private final LinkedList mainStack = new LinkedList(); private final LinkedList minStack = new LinkedList(); private final Comparator comparator; public MinStack(Comparator 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 st = new MinStack(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); } } 
 using System; using System.Collections.Generic; using System.IO; using System.Linq; namespace Solution { public class MinStack { public MinStack() { MainStack=new Stack(); Min=new Stack(); } static Stack MainStack; static Stack Min; public void Push(int item) { MainStack.Push(item); if(Min.Count==0 || item 

Saw a brilliant solution here: https://www.geeksforgeeks.org/design-a-stack-that-supports-getmin-in-o1-time-and-o1-extra-space/

Bellow is the python code I wrote by following the algorithm:

 class Node: def __init__(self, value): self.value = value self.next = None class MinStack: def __init__(self): self.head = None self.min = float('inf') # @param x, an integer def push(self, x): if self.head == None: self.head = Node(x) self.min = x else: if x >= self.min: n = Node(x) n.next = self.head self.head = n else: v = 2 * x - self.min n = Node(v) n.next = self.head self.head = n self.min = x # @return nothing def pop(self): if self.head: if self.head.value < self.min: self.min = self.min * 2 - self.head.value self.head = self.head.next # @return an integer def top(self): if self.head: if self.head.value < self.min: self.min = self.min * 2 - self.head.value return self.min else: return self.head.value else: return -1 # @return an integer def getMin(self): if self.head: return self.min else: return -1 

To getMin elements from Stack. We have to use Two stack .ie Stack s1 and Stack s2.

  1. Initially, both stacks are empty, so add elements to both stacks

———————Recursively call Step 2 to 4———————–

  1. if New element added to stack s1.Then pop elements from stack s2

  2. compare new elments with s2. which one is smaller , push to s2.

  3. pop from stack s2(which contains min element)

Code looks like:

 package Stack; import java.util.Stack; public class getMin { Stack s1= new Stack(); Stack s2 = new Stack(); void push(int x) { if(s1.isEmpty() || s2.isEmpty()) { s1.push(x); s2.push(x); } else { s1. push(x); int y = (Integer) s2.pop(); s2.push(y); if(x < y) s2.push(x); } } public Integer pop() { int x; x=(Integer) s1.pop(); s2.pop(); return x; } public int getmin() { int x1; x1= (Integer)s2.pop(); s2.push(x1); return x1; } public static void main(String[] args) { getMin s = new getMin(); s.push(10); s.push(20); s.push(30); System.out.println(s.getmin()); s.push(1); System.out.println(s.getmin()); } } 

I think only push operation suffers, is enough. My implementation includes a stack of nodes. Each node contain the data item and also the minimum on that moment. This minimum is updated each time a push operation is done.

Here are some points for understanding:

  • I implemented the stack using Linked List.

  • A pointer top always points to the last pushed item. When there is no item in that stack top is NULL.

  • When an item is pushed a new node is allocated which has a next pointer that points to the previous stack and top is updated to point to this new node.

Only difference with normal stack implementation is that during push it updates a member min for the new node.

Please have a look at code which is implemented in C++ for demonstration purpose.

 /* * 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  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: "< 

And the output of the program looks like this:

 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> { public void push(T val); public T pop(); public T minValue(); public int size(); } 

 import java.util.Stack; public class MinStack> implements IMinStack { private Stack stack = new Stack(); private Stack minStack = new Stack(); @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(); } }