这是一个面试问题。
你需要设计一个栈，它可以保存整数值，使得
getMinimum()函数可以返回栈中最小的元素。例如：
案件编号#1
5 ← TOP
1
4
6
2当调用getMinimum()时，它应该返回1，这是栈中的最小元素。
案件 #2
stack.pop()
stack.pop()Note: Both 5 and 1 are popped out of the stack. So after this, the stack looks like
4 ← TOP
6
2当调用
getMinimum()时，它应该返回2，这是栈中的最小值。限制条件：
- getMinimum should return the minimum value in O(1)
- Space constraint also has to be considered while designing it and if you use extra space, it should be of constant space.
编辑：这不符合“恒定空间”约束-它基本上会使所需空间加倍。我非常怀疑是否存在一种不这样做的解决方案，而不会在某个地方破坏运行时复杂度（例如使推/弹出O（n））。请注意，这不会改变所需空间的复杂度，例如，如果您拥有具有O（n）空间要求的堆栈，则仍将为O（n），只是具有不同的常数因子。
非常数空间解决方案
保持“重复”堆栈中的“所有比堆栈中低的所有值都低的最小值”。当您弹出主堆栈时，也要弹出min堆栈。当您推动主堆栈时，推入新元素或当前最小值中较低的任何一个。然后， getMinimum() 实现为 minStack.peek()。
保持“重复”堆栈中的“所有比堆栈中低的所有值都低的最小值”。当您弹出主堆栈时，也要弹出min堆栈。当您推动主堆栈时，推入新元素或当前最小值中较低的任何一个。然后， getMinimum() 实现为 minStack.peek()。
所以以您的例子为例，我们将会有：
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
请告诉我，如果这不够信息。当你领悟时，它很简单，但一开始可能需要一点思考 :)
当然，缺点是它会使空间需求加倍。但执行时间并没有显著受到影响——即复杂度仍然相同。
编辑：有一种稍微麻烦但占用空间更好的变体。我们仍然有最小栈，但只有在从主栈弹出的值等于最小栈上的值时才从最小栈弹出。我们只在将值推入主栈时，该值小于或等于当前最小值时才推到最小栈上。这允许重复的最小值。 getMinimum() 仍然只是一个查看操作。例如，将原始版本推送1再次进行时，我们将获得：
Real stack Min stack
1 --> TOP 1
5 1
1 2
4
6
2
由于1 == 1，因此从上面的两个栈中弹出，剩下：
Real stack Min stack
5 --> TOP 1
1 2
4
6
2
再次弹出，仅从主堆栈弹出，因为5>1:
Real stack Min stack
1 1
4 2
6
2
再次弹出会弹出两个堆栈，因为1 == 1：
Real stack Min stack
4 2
6
2
这样做最坏的空间复杂度相同（原始堆栈的两倍），但如果我们很少得到“新的最小值或相等值”，则空间利用率要好得多。
编辑：这是Pete邪恶计划的实施方案。我没有彻底测试过，但我认为这是可以的 :)
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;
}
}
添加一个字段来保存最小值，并在Pop（）和Push（）过程中更新它。这样getMinimum（）就会变成O（1），但Pop（）和Push（）需要做更多的工作。
如果弹出最小值，则Pop（）将为O（n），否则它们仍然都为O（1）。当调整大小时，Push（）根据堆栈实现变为O（n）。
这是一个快速实现。
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();
}
}
它明确地存储当前的最小值，如果最小值改变，它不是推送该值，而是推送一个与新最小值相反的“同一差值”值（如果min = 7，你推5，则推3而不是5 - | 7-5 | = 3，并将min设置为5;如果此时在min为5时弹出3，则看到弹出的值小于min，因此反转过程以获取7作为新的min，然后返回以前的min）。由于任何不会引起当前的最小值的更改的价值都大于当前的最小值，因此您可以使用某些值来区分会改变最小值以及不会改变最小值的值。
在使用固定大小整数的语言中，你从表示值中借用了一点空间，因此可能会发生下溢并导致assert失败。但除此之外，它是恒定的额外空间，所有操作仍然是O(1)。
基于链表的堆栈有其他地方可以借用一点，例如在C中，可以借用下一个指针的最低有效位，或者在Java中可以借用链表中对象的类型。对于Java而言，这意味着与连续堆栈相比，使用的空间更多，因为您每个链接都有对象开销：
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;
}
在C中，没有这种开销，而且您可以借用下一个指针的LSB：
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.;
然而，这些算法都不是真正的O(1)。它们在实践中不需要更多的空间，因为它们利用了这些语言中数字、对象或指针表示中的漏洞。但是，如果使用一个更紧凑的表示方法的理论机器，每种情况下都需要在该表示中添加一个额外的位。
我找到了一个满足所有提到的约束条件（常量时间操作）和常量额外空间的解决方案。
这个想法是存储最小值与输入数值之间的差值，并在其不再是最小值时更新最小值。
代码如下：
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;
}
}
功劳归于：https://leetcode.com/discuss/15679/share-my-java-solution-with-only-one-stack
好的，push和pop运行时间的约束是什么？如果它们不需要是恒定的，那么只需计算这两个操作的最小值（使它们成为O（n））。否则，我不知道如何用恒定的额外空间来完成此操作。
假设我们将要处理的堆栈是这样的:
6 , minvalue=2
2 , minvalue=2
5 , minvalue=3
3 , minvalue=3
9 , minvalue=7
7 , minvalue=7
8 , minvalue=8
在上面的表示中，堆栈仅由左值构建，右值[最小值]仅用于说明目的，将存储在一个变量中。
实际问题是当最小值被移除时：在这一点上，我们如何知道下一个最小元素而不必迭代堆栈。
例如，在我们的堆栈中弹出6时，我们知道这不是最小元素，因为最小元素是2，所以我们可以安全地删除此元素而不更新最小值。
但是当我们弹出2时，我们可以看到当前的最小值是2，如果将其弹出，则需要将最小值更新为3。
点1：
Now if you observe carefully we need to generate minvalue=3 from this particular state [2 , minvalue=2].
Or if you go deeper in the stack we need to generate minvalue=7 from this particular state [3 , minvalue=3]
or if you go deeper still in the stack then we need to generate minvalue=8 from this particular state [7 , minvalue=7]
Did you notice something in common in all of the above three cases? The value which we need to generate depends upon two variable which are both equal. Correct.
Why is this happening because when we push some element smaller then the current minvalue, then we basically push that element in the stack and updated the same number in minvalue also.
点二：
So we are basically storing duplicate of the same number once in stack and once in minvalue variable.
We need to focus on avoiding this duplication and store something useful data in the stack or the minvalue to generate the previous minimum as shown in CASES above.
Let s focus on what should we store in stack when the value to store in push is less than the minimum value. Let s name this variable y, so now our stack will look something like this:
6 , minvalue=2
y1 , minvalue=2
5 , minvalue=3
y2 , minvalue=3
9 , minvalue=7
y3 , minvalue=7
8 , minvalue=8
我将它们重命名为y1，y2，y3，以避免混淆，因为它们都具有相同的值。
第三点：
Now let s try to find some constraint s over y1, y2 and y3.
Do you remember when exactly we need to update the minvalue while doing pop(), only when we have popped the element which is equal to the minvalue.
If we pop something greater than the minvalue then we don t have to update minvalue.
So to trigger the update of minvalue, y1,y2&y3 should be smaller than there corresponding minvalue. [We are avoiding equality to avoid duplicate[Point2]]
so the constrain is [ y < minValue ].
Now let s come back to populate y, we need to generate some value and put y at the time of push, remember.
Let s take the value which is coming for push to be x which is less that the prevMinvalue, and the value which we will actually push in stack to be y.
So one thing is obvious that the newMinValue=x, and y < newMinvalue.
现在，我们需要计算y（记住y可以是任何小于newMinValue（x）的数字，因此我们需要找到一些数字来满足我们的约束条件），并借助prevMinvalue和x（newMinvalue）来完成。
Let s do the math:
x < prevMinvalue [Given]
x - prevMinvalue < 0
x - prevMinValue + x < 0 + x [Add x on both side]
2*x - prevMinValue < x
this is the y which we were looking for less than x(newMinValue).
y = 2*x - prevMinValue. or y = 2*newMinValue - prevMinValue or y = 2*curMinValue - prevMinValue [taking curMinValue=newMinValue].
因此，在推动 x 时，如果它小于 prevMinValue，则我们会推动 y [2 * x-prevMinValue] 并更新 newMinValue = x。
And at the time of pop if the stack contains something less than the minValue then that s our trigger to update the minValue.
We have to calculate prevMinValue from the curMinValue and y.
y = 2*curMinValue - prevMinValue [Proved]
prevMinValue = 2*curMinvalue - y .
2 * curMinValue - y 是我们现在需要更新为 prevMinValue 的数字。
相同逻辑的代码如下，时间复杂度是O(1)，空间复杂度也是O(1)。
// C++ program to implement a stack that supports
// getMinimum() in O(1) time and O(1) extra space.
#include <bits/stdc++.h>
using namespace std;
// A user defined stack that supports getMin() in
// addition to push() and pop()
struct MyStack
{
stack<int> s;
int minEle;
// Prints minimum element of MyStack
void getMin()
{
if (s.empty())
cout << "Stack is empty
";
// variable minEle stores the minimum element
// in the stack.
else
cout <<"Minimum Element in the stack is: "
<< minEle << "
";
}
// Prints top element of MyStack
void peek()
{
if (s.empty())
{
cout << "Stack is empty ";
return;
}
int t = s.top(); // Top element.
cout << "Top Most Element is: ";
// If t < minEle means minEle stores
// value of t.
(t < minEle)? cout << minEle: cout << t;
}
// Remove the top element from MyStack
void pop()
{
if (s.empty())
{
cout << "Stack is empty
";
return;
}
cout << "Top Most Element Removed: ";
int t = s.top();
s.pop();
// Minimum will change as the minimum element
// of the stack is being removed.
if (t < minEle)
{
cout << minEle << "
";
minEle = 2*minEle - t;
}
else
cout << t << "
";
}
// Removes top element from MyStack
void push(int x)
{
// Insert new number into the stack
if (s.empty())
{
minEle = x;
s.push(x);
cout << "Number Inserted: " << x << "
";
return;
}
// If new number is less than minEle
if (x < minEle)
{
s.push(2*x - minEle);
minEle = x;
}
else
s.push(x);
cout << "Number Inserted: " << x << "
";
}
};
// Driver Code
int main()
{
MyStack s;
s.push(3);
s.push(5);
s.getMin();
s.push(2);
s.push(1);
s.getMin();
s.pop();
s.getMin();
s.pop();
s.peek();
return 0;
}
我们可以在O(n)时间和O(1)空间复杂度中完成此操作，像这样：
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
这是我实施的版本。
struct MyStack {
int element;
int *CurrentMiniAddress;
};
void Push(int value)
{
// Create you structure and populate the value
MyStack S = new MyStack();
S->element = value;
if(Stack.Empty())
{
// Since the stack is empty, point CurrentMiniAddress to itself
S->CurrentMiniAddress = S;
}
else
{
// Stack is not empty
// Retrieve the top element. No Pop()
MyStack *TopElement = Stack.Top();
// Remember Always the TOP element points to the
// minimum element in ths whole stack
if (S->element CurrentMiniAddress->element)
{
// If the current value is the minimum in the whole stack
// then S points to itself
S->CurrentMiniAddress = S;
}
else
{
// So this is not the minimum in the whole stack
// No worries, TOP is holding the minimum element
S->CurrentMiniAddress = TopElement->CurrentMiniAddress;
}
}
Stack.Add(S);
}
void Pop()
{
if(!Stack.Empty())
{
Stack.Pop();
}
}
int GetMinimum(Stack &stack)
{
if(!stack.Empty())
{
MyStack *Top = stack.top();
// Top always points to the minimumx
return Top->CurrentMiniAddress->element;
}
}
这是我的O(1)运行的代码。我之前发布的代码在弹出最小元素时出现了问题。我修改了我的代码。这个代码使用另一个栈，维护当前插入元素之上的栈中最小元素。
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
试试看。我认为它回答了这个问题。每对的第二个元素给出了在插入该元素时看到的最小值。
我在这里发布完整的代码，以查找给定堆栈中的最小值和最大值。
时间复杂度为O(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()+"
MinMaxStackFinder [minStack=" + minStack + "
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());
}
}
如果您遇到任何问题，请告诉我。
Thanks, Vikash
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();
}
}
这是我用O(1)运行的代码。我用了向量对，其中包含推入的值，也包含到达该推入值的最小值。
这是我实现的C++版本。
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 */
A practical implementation for finding minimum in a Stack of User Designed Object, named: School
堆栈将基于特定地区分配给学校的排名将学校存储在堆栈中，例如，findMin（）给出了我们获得入学申请最多的学校，而这又由使用以前赛季学校排名的比较器来定义。
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;
}
}
This Example covers the following: 1. Implementation of Stack for User defined Objects, here, School 2. Implementation for the hashcode() and equals() method using all fields of Objects to be compared 3. A practical implementation for the scenario where we rqeuire to get the Stack contains operation to be in order of O(1)
这是根据Jon Skeet的回答所解释的PHP实现，它是最大堆栈的略微更好的空间复杂度实现，时间复杂度为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
";
print "Max: {$stack->getMax()}
";
print "Pop: {$stack->pop()}
";
print "Pop: {$stack->pop()}
";
print "Stack: $stack
";
print "Max: {$stack->getMax()}
";
print "Pop: {$stack->pop()}
";
print "Pop: {$stack->pop()}
";
print "Stack: $stack
";
print "Max: {$stack->getMax()}
";
// 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
";
} 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
你可以扩展你原来的堆栈类，并将最小值跟踪添加到其中。像往常一样让原始父类处理其他所有事情。
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();
}
}
我认为你可以简单地在你的栈实现中使用LinkedList。
第一次推送值时，将该值作为链表头。
每当你推一个值时，如果新值小于头部数据，就进行一个前置操作（即将头变成新值）。
如果没有，就进行附加操作。 (If you want the Simplified Chinese version: 如果没有，则进行附加操作。)
当你执行pop()操作时，你需要检查min是否等于linkedlist.head.data，如果是，那么将head移动到head.next；
这是我的代码。
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();
}
}
这是我在Java中使用链表的解决方案。
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;
從電影中學習中文是一種有趣的方式。
從電影中學習中文是一種有趣的方式。
public class MinStack<E>{
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);
}
}
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
namespace Solution
{
public class MinStack
{
public MinStack()
{
MainStack=new Stack<int>();
Min=new Stack<int>();
}
static Stack<int> MainStack;
static Stack<int> Min;
public void Push(int item)
{
MainStack.Push(item);
if(Min.Count==0 || item<Min.Peek())
Min.Push(item);
}
public void Pop()
{
if(Min.Peek()==MainStack.Peek())
Min.Pop();
MainStack.Pop();
}
public int Peek()
{
return MainStack.Peek();
}
public int GetMin()
{
if(Min.Count==0)
throw new System.InvalidOperationException("Stack Empty");
return Min.Peek();
}
}
}
Saw a brilliant solution here: https://www.geeksforgeeks.org/design-a-stack-that-supports-getmin-in-o1-time-and-o1-extra-space/
以下是我按照算法编写的Python代码：
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
从栈中获取最小元素。我们需要使用两个栈。即栈s1和栈s2。
递归调用步骤2至4
如果堆栈s1添加了新元素。则从堆栈s2弹出元素。
将新元素与s2比较。哪一个更小，就推到s2中去。
从包含最小元素的堆栈s2中弹出。
代码看起来像：
package Stack;
import java.util.Stack;
public class getMin
{
Stack<Integer> s1= new Stack<Integer>();
Stack<Integer> s2 = new Stack<Integer>();
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 have better solution, with O(1) time and with no extra space, You need to push element as String as <original_value,minimum_value>. For example find this stack of string.
|-1,-1| (|-1,-1|)
1,1 一，一
|2,2| = 2.2
| 5,3 | 的中文翻译是 |5,3|。
| 3，3 |
现在，您可以仅使用 peek 并检查给定实例的最小值来始终找到当前实例的最小值。 这是不需要额外空间的 O(1) 时间。
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);
}
}
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 <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;
}
}
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.
#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:%d ",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
");
display(tos);
break;
default: exit(0);
}
}
I found this solution here
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
}
}