刷题：栈的相关操作

﹏ヽ暗。殇╰゛Y 2022-01-29 13:06 195阅读 0赞

### 刷题：栈的相关操作 ###

*  1. 设计一个具有getMin功能的栈
 *  2. 用一个栈实现另一栈的排序
 *  3.Next Greater Node In Linked List

# 1. 设计一个具有getMin功能的栈 #

**要求**：pop、push、getMin等函数的功能的时间复杂度都是O(1)。

**思路**：用两个标准栈来实现。其中一个栈用于存储数据（称为**数据栈，stackData**），另一个栈用于存储当前数据栈中的最小值（称为**最小栈，stackMin**）。

**入栈规则：**  
假设入栈的数据为 num，则将其压入stackData中，然后判断stackMin是否为空。

1.  如果stackMin 为空，则将num 也压入stackMin中。
2.  如果stackMin 不为空，则比较 num 与 stackMin 栈顶元素的大小。
3.  如果num 小于等于 stackMin 栈顶元素，则将num 压入stackMin中。
4.  如果num 大于 stackMin 栈顶元素，则stackMin不做操作。

**出栈规则：**  
将stackData的栈顶元素出栈，如该元素等于stackMin的栈顶元素，则stackMin将栈顶元素出栈。如该元素大于stackMin的栈顶元素，则stackMin不做操作。

**获取栈中最小元素时，只需要输出stackMin的栈顶元素。**

具体代码为：

class New_stack
    {
    public:
    	New_stack();
    	~New_stack();
    	void push(int n);
    	void pop();
    	int top();
    	int getMin();
    
    private:
    	stack<int> stack_data;
    	stack<int> stack_min;
    };
    
    New_stack::New_stack()
    {
    }
    
    New_stack::~New_stack()
    {
    }
    
    void New_stack::push(int n)
    {
    	stack_data.push(n);
    
    	if (stack_min.empty())
    		stack_min.push(n);
    	else if (n <= stack_min.top())
    		stack_min.push(n);
    
    }
    int New_stack::top()
    {
    	return stack_data.top();
    }
    void New_stack::pop()
    {
    	if (stack_data.empty())
    		cout << "The stack is empty !" << endl;
    	if (stack_data.top() == stack_min.top())
    		stack_min.pop();
    
    	stack_data.pop();
    }
    int New_stack::getMin()
    {
    	if (stack_data.empty())
    		cout << "The stack is empty !" << endl;
    	return stack_min.top();
    }

测试代码：

int main()
    {
    	
    	cout <<"the stack who has getMin functon " << endl;
    	New_stack stack_min;
    	stack_min.push(10);
    	stack_min.push(12);
    	stack_min.push(5);
    	stack_min.push(3);
    	stack_min.push(54);
    
    	for (int i = 0; i < 5; ++i)
    	{
    		cout << "the stack min value: " << stack_min.getMin() << endl;
    		stack_min.pop();
    	}
    	return 0;
    }

测试结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3MDk3NjA_size_16_color_FFFFFF_t_70]

# 2. 用一个栈实现另一栈的排序 #

**要求**：一个栈中的元素为整型，现在将栈从顶到底按从大到小的顺序排序。只允许申请一个栈。除此之外，可以申请新的变量，但是不允许使用其他的数据结构。

**思路**：申请一个栈用于存储临时的排序结果（记为**temp\_stack**），申请一个变量用于记录排序栈的栈顶元素（记为**cur**）。如果temp\_stack为空，则将cur压人temp\_stack中；如果temp\_stack不为空且cur 小于等于temp\_stack的栈顶元素，则将压入temp\_stack中；如果temp\_stack不为空且cur 大于temp\_stack的栈顶元素，则需要将temp\_stack栈中的元素压入排序栈中，直到cur值小于等于temp\_stack的元素或temp\_stack为空。用这种方式排序后，temp\_stack栈从顶到底的元素顺序为从小到大的顺序。因此，还需要将temp\_stack栈中的元素压入原始栈中。从而实现栈从顶到底按从大到小的顺序排序。

代码：

void sortStackbyStack(stack<int> &s)
    {
    	stack<int> temp_stack;
    	int cur = 0;
    	while (!s.empty())
    	{
    		cur = s.top();
    		s.pop();
    		while (!temp_stack.empty() && temp_stack.top() < cur)
    		{
    			s.push(temp_stack.top());
    			temp_stack.pop();
    		}
    		temp_stack.push(cur);
    	}
    	while (!temp_stack.empty())
    	{
    		s.push(temp_stack.top());
    		temp_stack.pop();
    	}
    }

测试代码：

int main()
    {
        stack<int> s;
    	cout << endl <<"用栈将另一个栈排序： " << endl;
    	cout <<"    原始栈： " ;
    	s.push(1); s.push(5); s.push(6); s.push(4); s.push(7);
    	for (int i = 0; i < 5; ++i)
    	{
    		cout << s.top() << " ";
    		s.pop();
    	}
    	cout << endl;
    	cout << "    排序栈： ";
    	s.push(1); s.push(5); s.push(6); s.push(4); s.push(7);
    	sortStackbyStack(s);
    	for (int i = 0; i < 5; ++i)
    	{
    		cout << s.top() << " ";
    		s.pop();
    	}
    	cout << endl;
    	return 0;
    }

测试结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3MDk3NjA_size_16_color_FFFFFF_t_70 1]

# 3.Next Greater Node In Linked List #

[Leetcode1019题][Leetcode1019]

该题是查找链表中当前元素后面第一个大于当前元素值的元素。用暴力法解决该问题时间复杂度是O(n^2)。但是这种做法肯定难以让人满意。所以需要寻找一种更好的方法。

该问题的最优解是用栈来处理。具体思路为：  
栈内存放的是**结点的编号**。 每压入一个编号前，先检查该编号对应元素是否大于栈顶的编号对应元素，、如果大于，则栈顶编号出列，且栈顶编号对应元素的greater为 当前编号对应元素。如果不大于，则继续压栈。

这样做的目的是 **用栈来记录哪些节点未找到它的目标节点**。没找到目标节点的节点就保留在栈中，那些找到目标节点的节点则记录它的目标节点然后出栈。

具体代码为：

vector<int> nextLargerNodes(ListNode* head) {
    	stack<int> hole;
    	vector<int> values;
    	for (auto node = head; node; node = node->next)//获取链表中节点的值，将其保存在values中，以便进行处理。
    	 {
    		values.push_back(node->val);
    	}
    	vector<int> res(values.size(), 0);
    	for (auto i = 0; i < values.size(); ++i) 
    	{
    		//查找目标值的过程
    		while (!hole.empty() && values[i] > values[hole.top()]) 
    		{
    			res[hole.top()] = values[i];
    			hole.pop();
    		}
    		hole.push(i);
    	}
    	return res;
    }

运行结果为：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3MDk3NjA_size_16_color_FFFFFF_t_70 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3MDk3NjA_size_16_color_FFFFFF_t_70]: /images/20220129/e35a6ccba0674444997e1978e88e625a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3MDk3NjA_size_16_color_FFFFFF_t_70 1]: /images/20220129/5f4c1c79cad347f5b8a1380c9a37df67.png
[Leetcode1019]: https://leetcode.com/problems/next-greater-node-in-linked-list/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3MDk3NjA_size_16_color_FFFFFF_t_70 2]: /images/20220129/dc25d2dc6ec447ec895a39cff5a49689.png