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

2021年4月15日16:53:27 发表评论 534 次浏览

## 本文概述

Consider the following SpecialStack
16  --> TOP
15
29
19
18

When 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
18

When getMin() is called, it should
return 18 which is the minimum in
the current stack.

Push(int x)//将元素x插入特殊栈

1)将x推入第一个栈(具有实际元素的栈)

2)将x与第二个栈(辅助栈)的顶部元素进行比较。令顶部元素为y。

…..a)如果x小于y, 则将x推入辅助栈。

…..b)如果x大于y, 则将y推入辅助栈。

int Pop()//从特殊栈中删除一个元素并返回删除的元素

1)从辅助栈中弹出顶部元素。

2)从实际栈中弹出顶部元素, 然后将其返回。

int getMin()//返回特殊栈中的最小元素

1)返回辅助栈的顶部元素。

When we insert 18, both stacks change to following.
Actual Stack
18 <--- top
Auxiliary Stack
18 <---- top

When 19 is inserted, both stacks change to following.
Actual Stack
19 <--- top
18
Auxiliary Stack
18 <---- top
18

When 29 is inserted, both stacks change to following.
Actual Stack
29 <--- top
19
18
Auxiliary Stack
18 <---- top
18
18

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

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

## 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
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
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
# 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)。
使用辅助栈存储值。

## 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)。
最坏情况下的复杂度与上述相同, 但在其他情况下, 由于忽略了重复, 因此其占用的空间比上述方法要少一些。