博客

相关刷题笔记博客



竞赛常用模板整理（ACM/ICPC/CCSP）




Leetcode算法刷题笔记1-链表



Leetcode算法刷题笔记2-栈、队、堆



Leetcode算法刷题笔记3-递归与回溯



Leetcode算法刷题笔记4-贪心



Leetcode算法刷题笔记5-二叉树



Leetcode算法刷题笔记6-图



Leetcode算法刷题笔记7-动态规划



Leetcode算法刷题笔记8-二分查找

前言

stack成员函数

queue成员函数

heap成员函数

Leetcode 225. 用队列实现栈

使用队列实现栈的下列操作：

push(x) -- 元素 x 入栈
pop() -- 移除栈顶元素
top() -- 获取栈顶元素
empty() -- 返回栈是否为空

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/implement-stack-using-queues/

你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。

#include<queue>
#include<iostream>
using namespace std;

class MyStack {
public:
    MyStack(){}//临时队列，与新元素的次序交换 
    void push(int x){
    	queue<int> temp_queue;
    	temp_queue.push(x);	//对新元素x的操作 
    	while(!_data.empty()){
    		temp_queue.push(_data.front());//只要_data数据队列不为空就循环 
    		_data.pop();
    	}
    	while(!temp_queue.empty()){//只要临时队列temp_queue不为空就循环 
    		_data.push(temp_queue.front());
    		temp_queue.pop();
    	}
	}					
	int pop(){  		//弹出栈顶并返回该元素 
		int x = _data.front();
		_data.pop(); 	//弹出队列头部元素 
		return x;		//返回弹出元素，设置为栈顶 
	}
	int top(){
		return _data.front();//返回栈顶元素，即为队列头部 
	}
	bool empty(){
		return _data.empty();
	}
    private:
    	queue<int> _data;//_data为队列元素，也是我们设置的栈内元素 
  	
};
int main(){
	MyStack S;
	S.push(1);
	S.push(2);
	S.push(6);
	S.push(3);
	cout<<S.top()<<endl;
	S.pop();
	cout<<S.top()<<endl;
	S.push(5);
	cout<<S.top()<<endl;
	return 0;
}

Leetcode 155. 最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。

示例:

输入： [“MinStack”,“push”,“push”,“push”,“getMin”,“pop”,“top”,“getMin”]

[[],[-2],[0],[-3],[],[],[],[]]

输出： [null,null,null,null,-3,null,0,-2]

解释： MinStack minStack = new MinStack(); minStack.push(-2);

minStack.push(0); minStack.push(-3); minStack.getMin(); –> 返回 -3.

minStack.pop(); minStack.top(); –> 返回 0. minStack.getMin();

–> 返回 -2.

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/min-stack/

#include<stack>
#include<iostream>
using namespace std;

class MinStack {
public:
    MinStack(){}//临时队列，与新元素的次序交换 
    void push(int x){
    	_data.push(x);//压入第一个数 
		if(_min.empty()){
			_min.push(x);
		} else{	//若新数据小于最小栈顶，则替换 
			if(x>_min.top()){
				x = _min.top();
			}
			_min.push(x);//压入x到最小栈 
		}
	}					
	void pop(){  		//弹出栈顶和最小栈 
		_data.pop(); 	
		_min.pop();		
	}
	int top(){
		return _data.top();//返回栈顶元素
	}
	int getMin(){  			//getMin返回最小值栈顶元素 
		return _min.top();
	}
    private:
    	stack<int> _data;//数据栈 
  		stack<int> _min; //最小值栈 
};
int main(){
	MinStack minstack;
	minstack.push(-2);
	cout<<"top = "<<minstack.top()<<endl;
	cout<<"min = "<<minstack.getMin()<<endl;
	minstack.push(0);
	cout<<"top = "<<minstack.top()<<endl;
	cout<<"min = "<<minstack.getMin()<<endl;
	minstack.push(-5);
	cout<<"top = "<<minstack.top()<<endl;
	cout<<"min = "<<minstack.getMin()<<endl;
	minstack.pop();
	cout<<"top = "<<minstack.top()<<endl;
	cout<<"min = "<<minstack.getMin()<<endl;
	return 0;
}

堆的删除

public static Integer deleteMax(HeapStruct heapStruct) {
        if (heapStruct == null || heapStruct.getSize() == 0) {
            return null;
        }
        Integer[] elements = heapStruct.getElements();
        Integer maxValue = elements[0];//直接删除堆顶返回
        Integer finalValue = elements[heapStruct.getSize() - 1];//最后一个元素，当做堆顶，持续和左右儿子进行对比
        int parent = 0;
        while (parent * 2 <= heapStruct.getSize() - 1) {
            int child = parent * 2 + 1;
            if (child > heapStruct.getSize() - 1 && elements[child].compareTo(elements[child + 1]) < 0) {
                child = child + 1;//右儿子大。最大的儿子找到
            }
            if (finalValue.compareTo(elements[child]) > 0) {//最后一个元素和最大的儿子进行比较，如果最后的元素大，说明可以做顶，找到了位置。
                break;
            } else {
                elements[parent] = elements[child];//儿子大，儿子上移。持续下一轮的对比。
                parent = child;
            }
        }
        elements[parent] = finalValue;
        elements[heapStruct.getSize() - 1] = null;
        return maxValue;
    }