stack<T>:是一个封装了 deque<T> 容器的适配器类模板,默认实现的是一个后入先出的压入栈。
queue<T>:是一个封装了 deque<T> 容器的适配器类模板,默认实现的是一个先入先出的队列。可为它指定一个符合确定条件的基础容器。
priority_queue<T>:是一个封装了 vector<T> 容器的适配器类模板,默认实现的是一个对元素排序,保证最大元素总在队列最前面的队列。
图 展示了一个理论上的 stack 容器及其一些基本操作。只能访问 stack 顶部的元素;只有在移除 stack 顶部的元素后,才能访问下方的元素。
初始化:
std::stack<std::string> words;
//通过指定第二个模板类型参数,可以使用任意类型的底层容器
std::stack<std::string,std::list<std::string>> fruit;
std::list<double> values {1.414, 3.14159265, 2.71828};
std::stack<double,std::list<double>> my_stack (values);
//拷贝构造函数
std::stack<double,std::list<double>>copy_stack {my_stack}
基本操作:
top():返回一个栈顶元素的引用,类型为 T&。如果栈为空,返回值未定义。
push(const T& obj):可以将对象副本压入栈顶。这是通过调用底层容器的 push_back() 函数完成的。
push(T&& obj):以移动对象的方式将对象压入栈顶。这是通过调用底层容器的有右值引用参数的 push_back() 函数完成的。
pop():弹出栈顶元素。
size():返回栈中元素的个数。
empty():在栈中没有元素的情况下返回 true。
emplace():用传入的参数调用构造函数,在栈顶生成对象。
swap(stack<T> & other_stack):将当前栈中的元素和参数中的元素交换。参数所包含元素的类型必须和当前栈的相同。
2.queue
图展示只能在容器的末尾添加新元素,只能从头部移除元素。
初始化:
std::queue<std::string> words;
//拷贝够咱函数
std::queue<std::string> copy_words {words};
//指定参数模板
std::queue<std::string, std::list<std::string>>words;
基本操作:
front():返回 queue 中第一个元素的引用。如果 queue 是常量,就返回一个常引用;如果 queue 为空,返回值是未定义的。
back():返回 queue 中最后一个元素的引用。如果 queue 是常量,就返回一个常引用;如果 queue 为空,返回值是未定义的。
push(const T& obj):在 queue 的尾部添加一个元素的副本。这是通过调用底层容器的成员函数 push_back() 来完成的。
push(T&& obj):以移动的方式在 queue 的尾部添加元素。这是通过调用底层容器的具有右值引用参数的成员函数 push_back() 来完成的。
pop():删除 queue 中的第一个元素。
size():返回 queue 中元素的个数。
empty():如果 queue 中没有元素的话,返回 true。
emplace():用传给 emplace() 的参数调用 T 的构造函数,在 queue 的尾部生成对象。
swap(queue<T> &other_q):将当前 queue 中的元素和参数 queue 中的元素交换。
具体实例:
模拟超市运转的程序。结账队列的长度是超市运转的关键因素。
它会影响超市可容纳的顾客数——因为太长的队伍会使顾客感到气馁,从而放弃排队。
a)顾客类
#ifndef CUSTOMER_H
#define CUSTOMER_H
class Customer
{
//记录顾客结帐需要的时间
protected:
size_t service_t{};
public:
explicit Customer(size_t st=10):service_t{st}{}
//每个顾客结帐时间不同,每过一分钟,调用一次
Customer& time_decrement()
{
if(service_t >0)
--service_t;//反映顾客结帐所花费的时间
return *this;
}
bool done() const{return service_t==0;}
};
#endif
b)结帐类
#ifndef CHECKOUT_H
#define CHECKOUT_H
#include <queue>
#include "customer.h"
class Checkout
{
//等待结帐的队列
private:
std::queue<Customer> customers;
public:
//向队列中添加新顾客
void add(const Customer& customer){
customers.push(customer);
}
size_t qleng() const {
return customers.size();
}
void time_increment(){
if(!customers.empty()){
//顾客结帐完成,溢出
if(customers.front().time_decrement().done())
customers.pop();
}
}
bool operator<(const Checkout& other) const{
return qleng() < other.qleng();
}
bool operator>(const Checkout& other) const{
return qleng() > other.qleng();
}
};
#endif
c)实现函数
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <numeric>
#include <algorithm>
#include <random>
#include "customer.h"
#include "checkout.h"
using std::string;
using distribution = std::uniform_int_distribution<>;
// 输出时间
void histogram(const std::vector<int>& v, int min)
{
string bar (60, '*');
for (size_t i {}; i < v.size(); ++i)
{
std::cout << std::setw(3) << i+min << " "
<< std::setw(4) << v[i] << " "
<< bar.substr(0, v[i])
<< (v[i] > static_cast<int>(bar.size()) ? "...": "")
<< std::endl;
}
}
int main()
{
std::random_device random_n;
// Setup minimum & maximum checkout periods - times in minutes
int service_t_min {2}, service_t_max {15};
distribution service_t_d {service_t_min, service_t_max};
// Setup minimum & maximum number of customers at store opening
int min_customers {15}, max_customers {20};
distribution n_1st_customers_d {min_customers, max_customers};
// Setup minimum & maximum intervals between customer arrivals
int min_arr_interval {1}, max_arr_interval {5};
distribution arrival_interval_d {min_arr_interval, max_arr_interval};
size_t n_checkouts {};
std::cout << "Enter the number of checkouts in the supermarket: ";
std::cin >> n_checkouts;
if (!n_checkouts)
{
std::cout << "Number of checkouts must be greater than 0. Setting to 1." << std::endl;
n_checkouts = 1;
}
std::vector<Checkout> checkouts {n_checkouts};
std::vector<int> service_times(service_t_max-service_t_min+1);
// Add customers waiting when store opens
int count {n_1st_customers_d(random_n)};
std::cout << "Customers waiting at store opening: " << count << std::endl;
int added {};
int service_t {};
while (added++ < count)
{
service_t = service_t_d(random_n);
std::min_element(std::begin(checkouts), std::end(checkouts))->add(Customer(service_t));
++service_times[service_t - service_t_min];
}
size_t time {};
const size_t total_time {600};
size_t longest_q {};
// Period until next customer arrives
int new_cust_interval {arrival_interval_d(random_n)};
// Run store simulation for period of total_time minutes
while (time < total_time)
{
++time;
// New customer arrives when arrival interval is zero
if (--new_cust_interval == 0)
{
service_t = service_t_d(random_n);
std::min_element(std::begin(checkouts), std::end(checkouts))->add(Customer(service_t));
++service_times[service_t - service_t_min];
for (auto & checkout : checkouts)
longest_q = std::max(longest_q, checkout.qleng());
new_cust_interval = arrival_interval_d(random_n);
}
for (auto & checkout : checkouts)
checkout.time_increment();
}
std::cout << "Maximum queue length = " << longest_q << std::endl;
std::cout << "\nHistogram of service times:\n";
histogram(service_times, service_t_min);
std::cout << "\nTotal number of customers today: "
<< std::accumulate(std::begin(service_times), std::end(service_times), 0)
<< std::endl;
}
priority_queue 模板有 3 个参数,其中两个有默认的参数;
第一个参数是存储对象的类型,
第二个参数是存储元素的底层容器,
第三个参数是函数对象,它定义了一个用来决定元素顺序的断言。
template <typename T, typename Container=std::vector<T>, typename Compare=std::less<T>> class priority_queue
初始化:
std::priority_queue<std::string> words;
//适当类型初始化队列
std::string wrds[] { "one", "two", "three", "four"};
std::priority_queue<std::string> words { std::begin(wrds),std:: end(wrds)};
// "two" "three" "one" "four"
//优先级队列对他们进行排序
std:: string wrds[] {"one", "two", "three", "four"};
std::priority_queue<std::string, std::vector<std::string>,
std: :greater<std::string>> words1 {std::begin (wrds) , std:: end (wrds) };
//"four" "one" "three" "two"
std::vector<int> values{21, 22, 12, 3, 24, 54, 56};
std::priority_queue<int> numbers {std::less<int>(),values};
//56 54 24 22 21 12 3
//指定全部模板参数
std::priority_queue<int, std::vector<int>,std::greater<int>> numbersl{std::greater<int>(), values};
基本操作:
push(const T& obj):将obj的副本放到容器的适当位置,这通常会包含一个排序操作。
push(T&& obj):将obj放到容器的适当位置,这通常会包含一个排序操作。
emplace(T constructor a rgs...):通过调用传入参数的构造函数,在序列的适当位置构造一个T对象。为了维持优先顺序,通常需要一个排序操作。
top():返回优先级队列中第一个元素的引用。
pop():移除第一个元素。
size():返回队列中元素的个数。
empty():如果队列为空的话,返回true。
swap(priority_queue<T>& other):和参数的元素进行交换,所包含对象的类型必须相同。
具体示例:
#include <iostream> // For standard streams
#include <queue> // For priority_queue<T>
#include <string> // For string class
using std::string;
// List contents of a priority queue
template<typename T>
void list_pq(std::priority_queue<T> pq, size_t count = 5)
{
size_t n {count};
while (!pq.empty())
{
std::cout << pq.top() << " ";
pq.pop();
if (--n) continue;
std::cout << std::endl;
n = count;
}
std::cout << std::endl;
}
int main()
{
std::priority_queue<std::string> words;
std::string word;
std::cout << "Enter words separated by spaces, enter Ctrl+D on a separate line to end:\n";
while (true)
{
if ((std::cin >> word).eof())
break;
words.push(word);
}
std::cout << "You entered " << words.size() << " words:" << std::endl;
list_pq(words);
}
结果展示: