これは面接の質問です。
getMinimum()関数がスタック内の最小要素を返すように、整数値を保持するスタックを設計する必要があります。例えば：
ケース＃1
5 ← TOP14
6
2getMinimum（）が呼び出されると、スタック内の最小要素である1を返す必要があります。
ケース＃2
stack.pop()
stack.pop()注：5と1の両方がスタックからポップされます。したがって、この後、スタックは次のようになります
4 ←
TOP62が
getMinimum()呼び出されると、スタックの最小値である2を返す必要があります。制約：
- getMinimumは、O（1）の最小値を返す必要があります
- スペースの制約も設計時に考慮する必要があり、余分なスペースを使用する場合は、一定のスペースにする必要があります。
編集：これは「一定のスペース」制約に失敗します-基本的に必要なスペースが2倍になります。ランタイムの複雑さをどこかで壊さずに（たとえば、プッシュ/ポップO（n）を作成する）、それを行わないソリューションがあるかどうかは非常に疑わしいです。これによって必要なスペースの複雑さが変わることはないことに注意してください。たとえば、O（n）のスペース要件を持つスタックがある場合でも、定数係数が異なるだけでO（n）になります。
非定空間ソリューション
「スタックの下位にあるすべての値の最小値」の「重複」スタックを保持します。メインスタックをポップするときは、最小スタックもポップします。メインスタックをプッシュするときは、新しい要素または現在の最小値のいずれか低い方をプッシュします。getMinimum()次に、として実装されますminStack.peek()。
したがって、あなたの例を使用すると、次のようになります。
Real stack Min stack
5 --> TOP 1
1 1
4 2
6 2
2 2
2回ポップすると、次のようになります。
Real stack Min stack
4 2
6 2
2 2
十分な情報がない場合はお知らせください。簡単に理解できますが、最初は少し頭を悩ませる必要があるかもしれません:)
（もちろん、欠点は、必要なスペースが2倍になることです。ただし、実行時間に大きな影響はありません。つまり、同じ複雑さです。）
編集：少し厄介なバリエーションがありますが、一般的にはより良いスペースがあります。最小スタックはまだありますが、メインスタックからポップする値が最小スタックの値と等しい場合にのみ、最小スタックからポップします。メインスタックにプッシュされる値が現在の最小値以下の場合にのみ、最小スタックにプッシュします。これにより、最小値を複製できます。まだただのぞき見操作です。たとえば、元のバージョンを取得して1をもう一度押すと、次のようになります。getMinimum()
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
これは、同じ最悪の場合のスペースの複雑さ（元のスタックの2倍）になりますが、「新しい最小値または等しい」がめったに得られない場合は、スペースの使用量がはるかに良くなります。
編集：これはピートの邪悪な計画の実装です。徹底的にテストしていませんが、大丈夫だと思います:)
using System.Collections.Generic;
public class FastMinStack<T>
{
private readonly Stack<T> stack = new Stack<T>();
// Could pass this in to the constructor
private readonly IComparer<T> comparer = Comparer<T>.Default;
private T currentMin;
public T Minimum
{
get { return currentMin; }
}
public void Push(T element)
{
if (stack.Count == 0 ||
comparer.Compare(element, currentMin) <= 0)
{
stack.Push(currentMin);
stack.Push(element);
currentMin = element;
}
else
{
stack.Push(element);
}
}
public T Pop()
{
T ret = stack.Pop();
if (comparer.Compare(ret, currentMin) == 0)
{
currentMin = stack.Pop();
}
return ret;
}
}
最小値を保持するフィールドを追加し、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();
}
}
現在の最小値を明示的に保存し、最小値が変更された場合、値をプッシュする代わりに、新しい最小値の反対側に同じ差の値をプッシュします (最小値 = 7 で 5 をプッシュすると、代わりに 3 がプッシュされます ( 5- |7-5| = 3) 最小値を 5 に設定します。次に、最小値が 5 のときに 3 をポップすると、ポップされた値が最小値より小さいことがわかります。そのため、手順を逆にして新しい最小値の 7 を取得し、前の値を返します。分）。現在の最小値を変更しない値は現在の最小値よりも大きいため、最小値を変更する値と変更しない値を区別するために使用できるものがあります。
固定サイズの整数を使用する言語では、値の表現から少しスペースを借りているため、アンダーフローしてアサートが失敗する可能性があります。しかし、それ以外の場合、それは一定の余分なスペースであり、すべての操作は依然として 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ですか？定数である必要がない場合は、これら2つの演算の最小値を計算するだけです（O（n）にします）。そうでなければ、私はこれが一定の追加スペースでどのように行われることができるかわかりません。
次のように、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
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);
}
}
特定のスタックで最小値と最大値を見つけるために、ここに完全なコードを投稿しています。
時間計算量は 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()+"\nMinMaxStackFinder [minStack=" + minStack + "\n maxStack="
+ maxStack + "]" ;
}
}
// You can use the below program to execute it.
package com.java.util.collection.advance.datastructure;
import java.util.Random;
public class MinMaxStackFinderApp {
public static void main(String[] args) {
MinMaxStack<Integer> stack =new MinMaxStackFinder(10);
Random random =new Random();
for(int i =0; i< 10; i++){
stack.push(random.nextInt(100));
}
System.out.println(stack);
System.out.println("MAX :"+stack.max());
System.out.println("MIN :"+stack.min());
stack.pop();
stack.pop();
stack.pop();
stack.pop();
stack.pop();
System.out.println(stack);
System.out.println("MAX :"+stack.max());
System.out.println("MIN :"+stack.min());
}
}
問題に直面している場合はお知らせください
ありがとう、ヴィカシュ
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);
}
}
これは、O(1) で最大のスタックを取得するためのわずかに優れたスペースの複雑さの実装として、Jon Skeet の回答で説明されているものの PHP 実装です。
<?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
別の種類のスタックを使用しました。これが実装です。
//
// 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
それを試してみてください。私はそれが質問に答えると思います。各ペアの 2 番目の要素は、その要素が挿入されたときに見られる最小値を示します。
ユーザーが設計したオブジェクトのスタックで最小値を見つけるための実用的な実装: 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;
}
}
この例では、次のことを扱います。 1. ユーザー定義オブジェクト (ここでは School) のスタックの実装 2. 比較するオブジェクトのすべてのフィールドを使用する hashcode() および equals() メソッドの実装 3. シナリオの実用的な実装スタックを取得するための rqeuire には、O(1) の順序になる操作が含まれています
これが私のバージョンの実装です。
構造体 MyStack {
int 要素;
int *CurrentMiniAddress;
};
void プッシュ (int 値)
{
// 構造を作成し、値を入力します
MyStack S = 新しい MyStack();
S->要素 = 値;
if(Stack.Empty())
{
// スタックが空なので、CurrentMiniAddress を自分自身にポイントします
S->CurrentMiniAddress = S;
}
そうしないと
{
// スタックは空ではありません
// 最上位の要素を取得します。ポップなし()
MyStack *TopElement = Stack.Top();
// TOP 要素は常に
// スタック全体の最小要素
if (S->エレメントCurrentMiniAddress->エレメント)
{
// 現在の値がスタック全体で最小の場合
// 次に、S は自分自身を指します
S->CurrentMiniAddress = S;
}
そうしないと
{
// したがって、これはスタック全体の最小値ではありません
// 心配はいりません。TOP は最小要素を保持しています
S->CurrentMiniAddress = TopElement->CurrentMiniAddress;
}
}
Stack.Add(S);
}
ボイドポップ()
{
if(!Stack.Empty())
{
スタック.ポップ();
}
}
int GetMinimum(スタック & スタック)
{
if(!stack.Empty())
{
MyStack *Top = stack.top();
// Top は常に minimumx を指します
Top->CurrentMiniAddress->要素を返します。
}
}
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
}
};
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
}
}