欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

包含min函数的栈

程序员文章站 2024-01-29 12:50:04
...

题目描述:

定义栈的数据结构,请在该类型中实现一个能够得到栈最小元素的min函数。在该栈中调用push、pop、top、min的时间复杂度都是o(1)。

 解读:(借助于辅助栈)

这里要再定义一个辅助栈,用来存放每次入栈时的最小元素,这样两个栈同时压入数据,数据栈数据正常数据压入和弹出,辅助栈压入数据的时候,要看压入的数据是否大于辅助栈的栈顶数据(如果大于栈顶数据,则复制此时辅助栈栈顶数据,再次压入辅助栈中),详细步骤见下图:

  • 首先两个栈左边为数据栈,右边为辅助栈,当为空时,两个栈数据进入
  • 第二个数据5压入数据栈,但是5大于3,所以此时最小的数据是3,把3压入辅助栈
  • 第三个数据4压入数据栈,但是4大于3,所以此时最小的数据是3,把3压入辅助栈
  • 第四个数据0压入数据栈,此时0小于3,所以此时最小的数据是0,把0压入辅助栈
  • 数据栈弹出数据,弹出栈顶0,辅助栈弹出栈顶数据0,每次辅助栈弹出时,都是当前数据栈中最小的数据

包含min函数的栈

class solution{
	private:
		stack<int> data_stack;
		stack<int> min_stack;
	public:
		void push(int value){
			if(data_stack.isEmpty()&&min_stack.isEmpty())
			{
				data_stack.push(value);
				min_stack.push(value);
			}
			else
			{
				if(value>min_stack.top())
				{
					data_stack.push(value);
					min_stack.push(min_stack.top());
				}
				else
				{
					data_stack.push(value);
					min_stack.push(value);
				}
			}
				
		}
		
		void pop()
		{
			if(!data_stack.isEmpty()&&!min_stack.isEmpty)
			{
				data_stack.pop();
				min_stack.pop();
				//return min_stack.top();
			}

			
		}
		
		int top()
		{
			return data_stack.top();
			
		}
		
		int min()
		{
			return min_stack.top();
		}
		
		bool empty()
		{
			if(data_stack.isEmpty)
				return true;
			else
				return false;
		}
	
	
}