设计和实现特殊的栈数据结构|添加了空间优化版本

本文概述

C++
Java
Python3
C++
Java

题：
设计一个数据结构SpecialStack, 它支持所有栈操作, 例如push(), pop(), isEmpty(), isFull()和附加操作getMin(), 该操作应返回SpecialStack中的最小元素。 SpecialStack的所有这些操作必须为O(1)。要实现SpecialStack, 你应该只使用标准的Stack数据结构, 而不能使用其他数据结构, 例如数组, 列表等。
例子：

Consider the following SpecialStack 16--> TOP 15 29 19 18When getMin() is called it should return 15, which is the minimum element in the current stack. If we do pop two times on stack, the stack becomes 29--> TOP 19 18When getMin() is called, it should return 18 which is the minimum in the current stack.

解：
使用两个栈：一个用于存储实际的栈元素, 另一个作为辅助栈来存储最小值。这样做的方式是进行push()和pop()操作, 以使辅助栈的顶部始终最小。让我们看看push()和pop()操作如何工作。
Push(int x)//将元素x插入特殊栈
1)将x推入第一个栈(具有实际元素的栈)
2)将x与第二个栈(辅助栈)的顶部元素进行比较。令顶部元素为y。
…..a)如果x小于y, 则将x推入辅助栈。
…..b)如果x大于y, 则将y推入辅助栈。
int Pop()//从特殊栈中删除一个元素并返回删除的元素
1)从辅助栈中弹出顶部元素。
2)从实际栈中弹出顶部元素, 然后将其返回。
必须执行步骤1, 以确保还为将来的操作更新了辅助栈。
int getMin()//返回特殊栈中的最小元素
1)返回辅助栈的顶部元素。
我们可以看到以上所有操作均为O(1).
让我们来看一个例子。让我们假设两个栈最初都是空的, 并且将18、19、29、15和16插入到SpecialStack中。

When we insert 18, both stacks change to following. Actual Stack 18 < --- top Auxiliary Stack 18 < ---- topWhen 19 is inserted, both stacks change to following. Actual Stack 19 < --- top 18 Auxiliary Stack 18 < ---- top 18When 29 is inserted, both stacks change to following. Actual Stack 29 < --- top 19 18 Auxiliary Stack 18 < ---- top 18 18When 15 is inserted, both stacks change to following. Actual Stack 15 < --- top 29 19 18 Auxiliary Stack 15 < ---- top 18 18 18When 16 is inserted, both stacks change to following. Actual Stack 16 < --- top 15 29 19 18 Auxiliary Stack 15 < ---- top 15 18 18 18

下面是SpecialStack类的实现。在下面的实现中，SpecialStack继承了Stack，并有一个作为辅助堆栈的Stack对象min。
C++

#include < iostream> #include < stdlib.h> using namespace std; /* A simple stack class with basic stack funtionalities */ class Stack { private : static const int max = 100; int arr[max]; int top; public : Stack() { top = -1; } bool isEmpty(); bool isFull(); int pop(); void push( int x); }; /* Stack's member method to check if the stack is iempty */ bool Stack::isEmpty() { if (top == -1) return true ; return false ; } /* Stack's member method to check if the stack is full */ bool Stack::isFull() { if (top == max - 1) return true ; return false ; } /* Stack's member method to remove an element from it */ int Stack::pop() { if (isEmpty()) { cout < < "Stack Underflow" ; abort (); } int x = arr[top]; top--; return x; } /* Stack's member method to insert an element to it */ void Stack::push( int x) { if (isFull()) { cout < < "Stack Overflow" ; abort (); } top++; arr[top] = x; } /* A class that supports all the stack operations and one additional operation getMin() that returns the minimum element from stack at any time.This class inherits from the stack class and uses an auxiliarry stack that holds minimum elements */ class SpecialStack : public Stack { Stack min; public : int pop(); void push( int x); int getMin(); }; /* SpecialStack's member method to insert an element to it. This method makes sure that the min stack is also updated with appropriate minimum values */ void SpecialStack::push( int x) { if (isEmpty() == true ) { Stack::push(x); min.push(x); } else { Stack::push(x); int y = min.pop(); min.push(y); if (x < y) min.push(x); else min.push(y); } } /* SpecialStack's member method to remove an element from it. This method removes top element from min stack also. */ int SpecialStack::pop() { int x = Stack::pop(); min.pop(); return x; } /* SpecialStack's member method to get minimum element from it. */ int SpecialStack::getMin() { int x = min.pop(); min.push(x); return x; } /* Driver program to test SpecialStack methods */ int main() { SpecialStack s; s.push(10); s.push(20); s.push(30); cout < < s.getMin() < < endl; s.push(5); cout < < s.getMin(); return 0; }

Java

//Java implementation of SpecialStack //Note : here we use Stack class for //Stack implementation import java.util.Stack; /* A class that supports all the stack operations and one additional operation getMin() that returns the minimum element from stack at any time. This class inherits from the stack class and uses an auxiliarry stack that holds minimum elements */ class SpecialStack extends Stack< Integer> { Stack< Integer> min = new Stack< > (); /* SpecialStack's member method to insert an element to it. This method makes sure that the min stack is also updated with appropriate minimum values */ void push( int x) { if (isEmpty() == true ) { super .push(x); min.push(x); } else { super .push(x); int y = min.pop(); min.push(y); if (x < y) min.push(x); else min.push(y); } } /* SpecialStack's member method to insert an element to it. This method makes sure that the min stack is also updated with appropriate minimum values */ public Integer pop() { int x = super .pop(); min.pop(); return x; } /* SpecialStack's member method to get minimum element from it. */ int getMin() { int x = min.pop(); min.push(x); return x; } /* Driver program to test SpecialStack methods */ public static void main(String[] args) { SpecialStack s = new SpecialStack(); s.push( 10 ); s.push( 20 ); s.push( 30 ); System.out.println(s.getMin()); s.push( 5 ); System.out.println(s.getMin()); } } //This code is contributed by Sumit Ghosh

Python3

# Python3 program for the # above approach # A simple stack class with # basic stack funtionalities class stack: def __init__( self ): self .array = [] self .top = - 1 self . max = 100 # Stack's member method to check # if the stack is iempty def isEmpty( self ): if self .top = = - 1 : return True else : return False # Stack's member method to check # if the stack is full def isFull( self ): if self .top = = self . max - 1 : return True else : return False # Stack's member method to # insert an element to it def push( self , data): if self .isFull(): print ( 'Stack OverFlow' ) return else : self .top + = 1 self .array.append(data) # Stack's member method to # remove an element from it def pop( self ): if self .isEmpty(): print ( 'Stack UnderFlow' ) return else : self .top - = 1 return self .array.pop() # A class that supports all the stack # operations and one additional # operation getMin() that returns the # minimum element from stack at # any time.This class inherits from # the stack class and uses an # auxiliarry stack that holds # minimum elements class SpecialStack(stack): def __init__( self ): super ().__init__() self . Min = stack() # SpecialStack's member method to # insert an element to it. This method # makes sure that the min stack is also # updated with appropriate minimum # values def push( self , x): if self .isEmpty(): super ().push(x) self . Min .push(x) else : super ().push(x) y = self . Min .pop() self . Min .push(y) if x < = y: self . Min .push(x) else : self . Min .push(y) # SpecialStack's member method to # remove an element from it. This # method removes top element from # min stack also. def pop( self ): x = super ().pop() self . Min .pop() return x # SpecialStack's member method # to get minimum element from it. def getmin( self ): x = self . Min .pop() self . Min .push(x) return x # Driver code if __name__ = = '__main__' :s = SpecialStack() s.push( 10 ) s.push( 20 ) s.push( 30 ) print (s.getmin()) s.push( 5 ) print (s.getmin()) # This code is contributed by rachitkatiyar99

输出如下

10 5

复杂度分析：

时间复杂度：
1. 对于插入操作：O(1)(由于将" push"插入栈需要持续的时间)
2. 对于删除操作：O(1)(由于删除栈中的" pop"需要持续的时间)
3. 对于"获取最小值"操作：O(1)(因为我们使用的辅助栈的顶部是最小元素)
辅助空间：O(n)。
使用辅助栈存储值。

空间优化版本
可以优化上述方法。我们可以限制辅助栈中的元素数量。仅当主栈的传入元素小于或等于辅助栈的顶部时, 我们才可以推送。同样, 在弹出过程中, 如果弹出元素等于辅助栈的顶部, 请删除辅助栈的顶部元素。以下是push()和pop()的修改后的实现。
C++

/* SpecialStack's member method to insert an element to it. This method makes sure that the min stack is also updated with appropriate minimum values */ void SpecialStack::push( int x) { if (isEmpty() == true ) { Stack::push(x); min.push(x); } else { Stack::push(x); int y = min.pop(); min.push(y); /* push only when the incoming element of main stack is smaller than or equal to top of auxiliary stack */ if (x < = y) min.push(x); } } /* SpecialStack's member method to remove an element from it. This method removes top element from min stack also. */ int SpecialStack::pop() { int x = Stack::pop(); int y = min.pop(); /* Push the popped element y back only if it is not equal to x */ if (y != x) min.push(y); return x; }

Java

/* SpecialStack's member method to insert an element to it. This method makes sure that the min stack is also updated with appropriate minimum values */ void push( int x) { if (isEmpty() == true ) { super .push(x); min.push(x); } else { super .push(x); int y = min.pop(); min.push(y); /* push only when the incoming element of main stack is smaller than or equal to top of auxiliary stack */ if (x < = y) min.push(x); } } /* SpecialStack's member method to remove an element from it. This method removes top element from min stack also. */ public Integer pop() { int x = super .pop(); int y = min.pop(); /* Push the popped element y back only if it is not equal to x */ if (y != x) min.push(y); return x; } //This code is contributed by Sumit Ghosh

复杂度分析：

时间复杂度：
1. 对于插入操作：O(1)(由于将" push"插入栈需要持续的时间)
2. 对于删除操作：O(1)(由于删除栈中的" pop"需要持续的时间)
3. 对于"获取最小值"操作：O(1)(因为我们使用的辅助工具的顶部是最小元素)
辅助空间：O(n)。
最坏情况下的复杂度与上述相同, 但在其他情况下, 由于忽略了重复, 因此其占用的空间比上述方法要少一些。

设计一个支持O(1)时间和O(1)额外空间的getMin()的栈
【设计和实现特殊的栈数据结构|添加了空间优化版本】如果你发现上述代码不正确, 或者找到其他解决相同问题的方法, 请写评论。