栈&队列面试题之实现一个栈...(Push,Pop,Min)

桃扇骨 2022-09-25 12:29 153阅读 0赞

# 实现一个栈，要求实现Push(压栈),Pop(出栈),Min(返回最小值的操作)的时间复杂度为O(1) #

我们知道栈是后进先出的一种数据结构，这种数据结构只允许在栈顶进行插入删除，所以要实现栈这种数据结构最好的结构就是顺序表.当尾插尾删多的时候，链表存在开辟空间和删除空间的时间消耗所以此时顺序表优于链表.结构选好之后就是如何求出栈的元素的最小值了？

**思路一：**

如果一次可以将同一个数据进行两次压栈

**一.要压入的数据比栈顶的数据大**

(1).将原来栈顶的元素保存起来再Pop掉

(2).将新元素压栈，再将原来栈顶的元素压栈

**二.要压入的数据比栈顶的数据小**

直接将该数据两次压栈

如果每次都如此压栈的话到最后栈顶的元素一定是所有数据中最小的元素，而且也不会改变入栈的顺序

**思路二：**

利用两个栈，一个栈按照正确的压栈顺序压栈，一个栈用来存储最小值；

(1).如果Stack1是空栈或者要入栈的元素小于Stack2的栈顶元素则将该数据即压入Stack1,也压入Stack2中

(2).如果要入栈的元素大于Stack2的栈顶元素则只需要将该数据压入Stack1中

此时Stack2中一定保存的是原来入栈元素的最小值了

以上两种想法都是以空间换时间，时间复杂度为O(1)

**思路一的实现：**

//两个元素为一组，栈顶为最小的元素
    template<typename T>
    class MinStack
    {
    public:
    	void Push(const T& d)
    	{
    		if(_ptr.empty() || d <= _ptr.top())
    			//要入栈的元素小于栈顶元素
    		{
    			_ptr.push(d);
    			_ptr.push(d);
    		}
    		else
    		{
    			T mindata=_ptr.top();
    			_ptr.push(d);
    			_ptr.push(mindata);
    		}
    	}
    	void Pop()
    	{
    		assert(!_ptr.empty());
    		_ptr.pop();
    		_ptr.pop();
    	}
    	T& MinData()
    	{
    		return _ptr.top();
    	}
    	T& top()
    	{
    		assert(!_ptr.empty());
    		T mindata=_ptr.top();
    		_ptr.pop();
    		T &ret=_ptr.top();
    		_ptr.push(mindata);
    		return ret;
    	}
    protected:
    	stack<T> _ptr;
    };

**思路二的实现：**

//利用两个栈，其中一个存储最小值
    template<typename T>
    class MinStack2
    {
    public:
    	void Push(const T& d)
    	{
    		if(_ptr1.empty() || d <= _ptr2.top())
    		{
    			_ptr1.push(d);
    			_ptr2.push(d);
    		}
    		else
    		{
    			_ptr1.push(d);
    		}
    	}
    	void Pop()
    	{
    		assert(!_ptr1.empty());
    		if(_ptr1.top() == _ptr2.top())
    		{
    			//当两个栈的栈顶元素相同时同时出栈
    			_ptr1.pop();
    			_ptr2.pop();
    		}
    		_ptr1.pop();
    	}
    	T& MinData()
    	{
    		return _ptr2.top();
    	}
    protected:
    	stack<T> _ptr1;   //存放数据
    	stack<T> _ptr2;   //最小值
    };

注意：

在想法二的Pop函数的实现中\_ptr2也需要调整，当两个栈栈顶元素一致时才可调整\_ptr2的栈顶元素，否则栈的最小值会一直是原先的最小值，无法动态修改.

test.cpp

void testMinStack()
    {
    	MinStack<int> ms;
    	ms.Push(5);
    	ms.Push(1);
    	ms.Push(2);
    	ms.Push(3);
    	ms.Pop();
    	cout<<ms.top()<<endl;  //3
    	cout<<"最小元素为:";
    	cout<<ms.MinData()<<endl;
    }
    
    void testMinStack2()
    {
    	MinStack2<int> ms2;
    	ms2.Push(5);
    	ms2.Push(3);
    	ms2.Push(6);
    	ms2.Push(0);
    	ms2.Push(2);
    	cout<<"最小元素为:";
    	cout<<ms2.MinData()<<endl;   //0
    	ms2.Pop();
    	ms2.Pop();
    	cout<<"最小元素为:";
    	cout<<ms2.MinData()<<endl;   //3
    }
    
    int main()
    {
    	//testMinStack();
    	testMinStack2();
    	system("pause");
    	return 0;
    }

通过测试以上两种代码都是可实现的...