本文概述
- 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
复杂度分析:
- 时间复杂度:
- 对于插入操作:O(1)(由于将" push"插入栈需要持续的时间)
- 对于删除操作:O(1)(由于删除栈中的" pop"需要持续的时间)
- 对于"获取最小值"操作: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
复杂度分析:
- 时间复杂度:
- 对于插入操作:O(1)(由于将" push"插入栈需要持续的时间)
- 对于删除操作:O(1)(由于删除栈中的" pop"需要持续的时间)
- 对于"获取最小值"操作:O(1)(因为我们使用的辅助工具的顶部是最小元素)
- 辅助空间:O(n)。
最坏情况下的复杂度与上述相同, 但在其他情况下, 由于忽略了重复, 因此其占用的空间比上述方法要少一些。
【设计和实现特殊的栈数据结构|添加了空间优化版本】如果你发现上述代码不正确, 或者找到其他解决相同问题的方法, 请写评论。
推荐阅读
- 算法设计(跳转搜索算法原理解析和实现)
- 允许向左/向右/向下和向上移动的最小成本路径
- 算法题(将一个数组拆分成两个相等的和子数组)
- pe装系统图文详细教程
- 本文告诉你bios升级有啥用
- 萝卜家园win10纯净版安装图文详细教程
- 一键系统之家系统安装win7的办法
- 系统之家纯净版xp系统下载
- 系统之家与深度技术比较哪个好用