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

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

本文概述

题：

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

例子：

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()和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 <---- 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

下面是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()的栈

如果你发现上述代码不正确, 或者找到其他解决相同问题的方法, 请写评论。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: