stack queue priority_queue
知识点
模拟实现
Stack.h
#pragma once
#include <vector>
#include <list>
#include <deque>
namespace zoya
{
template<class T,class Container=deque<T>>
class stack
{
public:
stack() {}
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
_con.pop_back();
}
const T& top()
{
return _con.back();
}
size_t size() const
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
private:
Container _con;
};
}
Queue.h
#pragma once
#include <vector>
#include <list>
#include <deque>
namespace zoya
{
template<class T,class Container=deque<T>>
class queue
{
public:
queue() {}
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
_con.pop_front();
}
const T& front()
{
return _con.front();
}
const T& back()
{
return _con.back();
}
size_t size() const
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
private:
Container _con;
};
}
PriorityQueue.h
#pragma once
#include <vector>
namespace zoya
{
template<class T>
class Less
{
public:
bool operator()(const T& x, const T& y)
{
return x < y;
}
};
template<class T>
class Greater
{
public:
bool operator()(const T& x, const T& y)
{
return x > y;
}
};
template<class T,class Container=vector<T>,class Compare=Less<T>>
class priority_queue
{
public:
void adjust_up(size_t child)
{
Compare com;
size_t parent = (child - 1) / 2;
while (child > 0)
{
if (com(_con[parent], _con[child]))
{
swap(_con[child], _con[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void push(const T& x)
{
_con.push_back(x);
adjest_up(_con.size() - 1);
}
void adjust_down(size_t parent)
{
Compare com;
size_t child = parent * 2 + 1;
while (child < _con.size())
{
if (child + 1 < _con.size() && com(_con[child], _con[parent]))
{
++child;
}
if (com(_con[parent], _con[child]))
{
swap(_con[parent], _con[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void pop()
{
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
adjust_down(0);
}
const T& top()
{
return _con[0];
}
size_t size() const
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
private:
Container _con;
};
}
Test.cpp
#include <stack>
#include <list>
#include <queue>
#include <iostream>
using namespace std;
#include "Stack.h"
#include "Queue.h"
#include "PriorityQueue.h"
class Date
{
friend ostream& operator<<(ostream& _cout, const Date& d);
public:
Date(int year = 1900, int month = 1, int day = 1)
: _year(year)
, _month(month)
, _day(day)
{
}
bool operator<(const Date& d)const
{
return (_year < d._year) ||
(_year == d._year && _month < d._month) ||
(_year == d._year && _month == d._month && _day < d._day);
}
bool operator>(const Date& d)const
{
return (_year > d._year) ||
(_year == d._year && _month > d._month) ||
(_year == d._year && _month == d._month && _day > d._day);
}
private:
int _year;
int _month;
int _day;
};
ostream& operator<<(ostream& _cout, const Date& d)
{
_cout << d._year << "-" << d._month << "-" << d._day;
return _cout;
}
struct LessPDate
{
bool operator()(Date* p1, Date* p2)
{
return *p1 < *p2;
}
};
int main()
{
//priority_queue<Date> q1;
priority_queue<Date, vector<Date>, greater<Date>> q1;
q1.push(Date(2025, 10, 29));
q1.push(Date(2025, 10, 28));
q1.push(Date(2025, 10, 30));
while (!q1.empty())
{
std::cout << ' ' << q1.top();
q1.pop();
}
std::cout << '\n';
priority_queue<Date*, vector<Date*>, LessPDate> q2;
q2.push(new Date(2025, 10, 29));
q2.push(new Date(2025, 10, 28));
q2.push(new Date(2025, 10, 30));
while (!q2.empty())
{
std::cout << ' ' << *q2.top();
q2.pop();
}
std::cout << '\n';
return 0;
}
作业
- 下列代码的运行结果是（ ）
#include <iostream>
#include <queue>
#include <string>
using namespace std;
int main()
{
priority_queue<int> a;
priority_queue<int, vector<int>, greater<int> > c;
priority_queue<string> b;
for (int i = 0; i < 5; i++)
{
a.push(i);
c.push(i);
}
while (!a.empty())
{
cout << a.top() << ' ';
a.pop();
}
cout << endl;
while (!c.empty())
{
cout << c.top() << ' ';
c.pop();
}
cout << endl;
b.push("abc");
b.push("abcd");
b.push("cbd");
while (!b.empty())
{
cout << b.top() << ' ';
b.pop();
}
cout << endl;
return 0;
}
A. 4 3 2 1 0 0 1 2 3 4 cbd abcd abc
B. 0 1 2 3 4 0 1 2 3 4 cbd abcd abc
C. 4 3 2 1 0 4 3 2 1 0 abc abcd cbd
D. 0 1 2 3 4 4 3 2 1 0 cbd abcd abc
- 解答：A
优先级队列默认情况为：大堆，这是解题的关键
priority_queue a; //a是大堆
priority_queue<int, vector, greater > c; //c指定了比较规则，是小堆
priority_queue b; //b是大堆
因此分别建堆的过程是建立a大堆，c小堆，b大堆
所以出队的顺序就按照其优先级大小出队
- 假设cont是一个Container 的示例，里面包含数个元素，那么当CONTAINER为：1.vector 2.list 3.deque
会导致下面的代码片段崩溃的Container 类型是（ ）
Container cont = { 1, 2, 3, 4, 5 };
Container::iterator iter, tempIt;
for (iter = cont.begin(); iter != cont.end();)
{
tempIt = iter;
++iter;
cont.erase(tempIt);
}
解答：1、3
++iter;
cont.erase(tempIt);
是否安全，关键在于：
erase()会不会让iter失效？- 迭代器失效（dangling）后还使用，就可能导致 崩溃。
- 分析三种容器行为：
vector
vector::erase(it)会导致 该迭代器以及它后面的所有迭代器全部失效。- 因为元素会向前移动。
- 所以：即使你先
++iter，再erase(tempIt)，iter 也会被影响，从而在下一轮iter++出问题。
可能崩溃
list
list::erase(it)只会使当前被删除的it失效。- 其他迭代器不会失效。
++iter;提前移动迭代器，不会出错。
安全
deque
deque::erase(it)：行为类似于 vector。- 具体实现依赖于系统，但在某些标准库中，删除某些位置（尤其是前部）时，也会让其它迭代器失效。
- 所以：不完全安全，可能造成崩溃。
可能崩溃
- 仿函数比起一般函数具有很多优点，以下描述错误的是()
A.在同一时间里，由某个仿函数所代表的单一函数，可能有不同的状态
B.仿函数即使定义相同，也可能有不同的类型
C.仿函数通常比一般函数速度快
D.仿函数使程序代码变简单
解答：C
- A：“在同一时间里，由某个仿函数所代表的单一函数，可能有不同的状态”
解释：
仿函数是对象，可以包含成员变量，所以不同对象可以在同一个操作中保持不同状态。
#include <iostream>
using namespace std;
struct Add {
int base;
Add(int b) : base(b) {}
int operator()(int x) {
return x + base;
}
};
int main() {
Add add10(10); // 状态是 base = 10
Add add20(20); // 状态是 base = 20
cout << add10(5) << endl; // 输出 15
cout << add20(5) << endl; // 输出 25
return 0;
}
说明：
虽然两个对象 add10 和 add20 都是 Add 类的仿函数，但它们的 状态（base）不同，调用同一个 operator() 函数，结果不同。这就是 A 所说的 “同一时间内，同一个仿函数有不同状态”。
- B：“仿函数即使定义相同，也可能有不同的类型”
解释：
两个结构体可以定义完全相同的 operator() 实现，但它们仍然是不同的类型。
示例代码：
#include <iostream>
using namespace std;
struct FunctorA {
int operator()(int x) { return x * 2; }
};
struct FunctorB {
int operator()(int x) { return x * 2; }
};
int main() {
FunctorA a;
FunctorB b;
cout << a(3) << endl; // 输出 6
cout << b(3) << endl; // 输出 6
// cout << (a == b); // 编译错误：不同类型，不能比较
return 0;
}
说明：
虽然 FunctorA 和 FunctorB 都实现了 operator()(int)，行为一样，但它们是不同的类型，不能互换。这就说明了 B 的正确性。
- C：不一定。
仿函数通常是类对象，调用时可以被内联（inline）优化，而普通函数尤其是函数指针则不易内联。所以仿函数通常更快，不是更慢。
且，仿函数 ≠ 模板函数
仿函数是指重载了 operator() 的类对象
模板函数是函数的泛型定义
两者不等价，也不冲突，一个仿函数可以是模板类，但不一定是。
// 仿函数，不是模板
struct Multiply {
int operator()(int x) { return x * 2; }
};
// 模板函数，不是仿函数
template<typename T>
T square(T x) { return x * x; }
学习笔记&练习 文章被收录于专栏
学习过程中的一些记录
美团HR面2544人在聊