Table of Contents
1. stack
introduce
use
2. queue queue
introduce
use
3. priority_queue priority queue
introduce
use
Simulation implementation
Reuse code
push
pop
How to sort descending order
Functor
Using functors to implement ascending and descending order
Total code for simulation implementation
4. deque double-ended queue
introduce
underlying implementation
Summary about deque
1. stack
Introduction
1. The stack is a special linear list whose elements follow the “last in first out” principle, that is, only insertion and deletion operations are allowed at one end of the list. This mode is called “last in first out” or LIFO ( last in fisrt out).
2. From the perspective of underlying implementation, stack is implemented as a container adapter. What is a container adapter? Let’s explain it first.
Let’s first take a look at the adapters around us. For example, have you noticed your laptop charger?
In fact, the laptop charger is an adapter. What the adapter has to do is convert the voltage. Generally speaking, the battery voltage of a computer is about 14V, and the standard voltage is 220V. If you want to charge the computer, you need to convert the standard voltage. This is the role of the adapter. Adaptation means conversion.
Adapter is a design pattern that converts the interface of one class into the interface of another class that the user expects. You can think of an adapter as a converter.
Container adapters allow programmers to choose an appropriate underlying data structure. For example, stack, when we wrote the C language before, when we wanted to use the stack data structure, did we have to simulate a stack first?
Then you don’t have to go through so much trouble now. If you need to use stacks and queues, just use them directly.
3. The underlying container of stack can be any container class template or other specific container class.
These container classes should support the following operations:
empty: empty operation
back: Get the tail element operation
push_back: tail insertion element operation
pop_back: tail deletion element operation
The underlying implementation of the stack (simplified version):
It can be seen that these methods of the stack are directly reused methods of the container, which embodies the idea of code reuse.
Container here is the container class, it can be vector, deque, list, or it can be omitted. If omitted, the default is the deque class.
use
The
The methods provided by the stack are: empty check, size retrieval, top data retrieval, push (insertion), pop (deletion), exchange and emplace placement.
Here are some explanations of some of the methods:
1. Constructor:
stack<Type, Container> (<data type, container type>) stackName;The data type must be present, and the container type can be vector, deque, or list. (Container type can be omitted, the default is deque)
2. Before using top(), you must determine whether the lower stack is empty. Top() can only be called when it is not empty, otherwise a segfault will occur.
This is because when the stack is empty, the stack’s top function returns super-tail -1 instead of NULL.
3. Like top above, make sure there is at least one element in the stack before calling the pop function.
If the stack is empty, calling pop will throw an EmptyStackException.
4. Regarding emplace, it means “placement”, that is, constructing a new element and placing it on the top of the stack. Emplace and push are very similar, let’s make a distinction here.
For push, you have to construct the object first, and then push it into the stack; emplace actively calls the constructor for you, constructs the object, and then inserts it into the stack.
Example:
#include<iostream>
#include<stack>
using namespace std;
int main() {
stack<int> st;
st.push(1);
st.push(2);
st.push(3);
?
while (!st.empty()) {
cout << st.top() << " ";
st.pop();
}
cout << endl;
return 0;
}
From a low-level perspective, Container is a template, and you can pass it an array or a linked list.
Let’s see how it fits:
2. queue queue
Introduction
1. A queue is a special linear table that can only insert data at the end of the queue and output data at the head of the queue. This mode is called “first in, first out” or FIFO (first in first out).
2. From the perspective of underlying implementation, queue is also implemented as a container adapter.
Show the underlying implementation of the simple version of queue:
The underlying container can be one of the standard container class templates or other specially designed container classes.
The underlying container should support at least the following operations:
empty: Check whether the queue is empty
size: Returns the number of valid elements in the queue
front: Returns a reference to the head element of the queue
back: Returns a reference to the last element of the queue
push_back: queue at the end of the queue
pop_front: Dequeue at the head of the queue
The standard container classesdeque and list satisfy these requirements. In other words, the location of the Container can be passed to deque/list, or it can be omitted. When omitted and not passed, the default Container is deque.
(Why is vector not satisfied? Because vector does not have header deletion. As we said before, vector did not implement header deletion because it thought it was inefficient)
Use
The header file
According to the characteristics of the queue, the implementation methods include: empty detection, size retrieval, queue head retrieval, queue tail retrieval, (queue tail) insertion, (queue head) deletion, exchange and emplace placement.
A few notes:
1. Constructor:
queue<Type, Container> (<data type, container type>) queueName;There must be a data type during initialization, and the container can be omitted. If omitted, it defaults to the deque type.
So constructing a queue can be in two situations:
queue<int> q; ? queue<int,list<int>> q;
Example:
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int main() {
queue<int> q;
q.push(1);
q.push(2);
q.push(3);
?
while (!q.empty()) {
cout << q.front()<<" ";
q.pop();
}
cout << endl;
return 0;
}
This picture illustrates why deque is a container adapter:
3. priority_queue priority queue
Introduction
1. The priority queue is a special queue structure. The order in the queue is not the order of insertion, but is sorted by weight.
It adds a priority to each element, and the element dequeued each time is the element with the highest priority in the queue.
Note: The larger the element, the higher the priority.
How are priorities determined? In fact, when the priority queue is created, its priority has already been set, and the default is descending order.
So how to sort in ascending order? We’ll talk about functors later.
2. Priority queue The bottom layer is implemented as a container adapter.
The underlying container can be any standard container class template or other specifically designed container class.
The container should be accessible via random access iterators and support the following operations:
empty(): Check whether the container is empty
size(): Returns the number of valid elements in the container
front(): Returns a reference to the first element in the container
push_back(): Insert elements at the end of the container
pop_back(): delete the element at the end of the container
The container classes vector and deque meet these needs. If the container class is omitted, vector is used by default.
3. Need to support random access iterators so that the heap structure is always maintained internally.
priority_queue is implemented using a heap, so priority_queue is a heap. You can consider using priority_queue wherever a heap is needed.
Note: By default priority_queue is a large heap.
Use
The header file
Note: You don’t use front to get the top data! Use top.
Example:
#include<iostream>
#include<queue>
using namespace std;
int main() {
priority_queue<int> q;
q.push(4);
q.push(12);
q.push(3);
?
while (!q.empty()) {
cout << q.top()<<" ";
q.pop();
}
cout << endl;
return 0;
}
Simulation Implementation
priority_queue has all the characteristics of a queue, except that it adds sorting internally. Its underlying principle is implemented using the heap.
Now let’s simulate and implement a simple version of it so that we can better understand its underlying principles.
Reuse code
First, let’s write functions such as top and empty that are implemented by reusing code:
#pragma once
#include<iostream>
#include<vector>
using namespace std;
namespace jzy
{
template<class T,class Container = vector<T>> //T is the data storage type in the priority queue
class priority_queue //Container is the data structure in the priority queue
{
public:
void push(const T & amp; val) {}
void pop() {}
T top() {
return _con.front(); //Direct reuse of container methods
}
bool empty() {
return _con.empty();
}
size_t size() {
return _con.size();
}
?
private:
T_val;
Container_con;
};
}
push
Implementation of push: (big root heap) first insert the tail and then adjust upward.
void AdjustUp(Container & amp; _con) {
int child = _con.size()-1;
int parent = (child - 1) / 2;
?
while (child > 0){
if (_con[child] > _con[parent]) {
swap(_con[child], _con[parent]);
child = parent;
parent = (child - 1) / 2;
}
else {
break;
}
}
}
?
void push(const T & val) {
_con.push_back(val);
AdjustUp(_con);
}
pop
Implementation of pop: First swap the head and tail, so that the element with the highest priority comes to the end of the queue for tail deletion. Adjust downward again.
void AdjustDown(Container & amp; _con) {
int parent = 0;
int child = 2 * parent + 1;
?
while (child < _con.size()) {
if (child + 1 < _con.size() & amp; & amp; _con[child + 1] > _con[child]) {
child + + ;
}
?
if(_con[parent] <_con[child]) {
swap(_con[parent], _con[child]);
parent = child;
child = 2 * parent + 1;
}
else {
break;
}
}
}
?
void pop() {
swap(_con.front(), _con[_con.size()-1]);
_con.pop_back();
AdjustDown(_con);
}
How to sort in descending order
The current sorting is in ascending order, so what should I do if I want to sort it in descending order?
I have a very simple method: every time I insert an element and adjust it upwards, I adjust the smaller one upwards. Isn’t that enough?
In fact, just change the symbol:
void AdjustUp(Container & amp; _con) {
int child = _con.size()-1;
int parent = (child - 1) / 2;
?
while (child > 0){
if (_con[child] < _con[parent]) { //This was originally >, now it is changed to <. The smaller it is, the higher it is.
swap(_con[child], _con[parent]);
child = parent;
parent = (child - 1) / 2;
}
else {
break;
}
}
}
However, this approach is not good. If I want to sort in ascending order, I have to change the symbol to >; if I want to sort in descending order, I have to change it back to <, which is troublesome.
Can it be solved using generics?
In fact, in the STL library, it is solved using generics. Let’s learn about it.
In STL, priority_queue has 3 template parameters:
template <class T, class Container = vector<T>, class Compare = less<typename Container::value_type>>
The third template parameter, Compare, defines the comparison method. That is to say, we formulate comparison rules by defining the Compare class.
However, in order to understand parameter Compare, we must first learn a knowledge point: functors.
Function
A functor is not a function, it describes an object, but this object overloads operator(), so it is used like a function.
For example, you define a class A and use A to instantiate object a. At this time a is an ordinary object.
But when you overload operator() (that is, the function call operator) in A, then a is a functor and can be used like this:
class A
{
…
int operator() (int x,int y){
return x + y;
}
};
int mian(){
A a;
cout<<a(1,2); //The object a instantiated by A can be used like a function, and a is called a functor.
return 0;
}
about():
I was confused at first, how can parentheses () be overloaded?
That’s right! () is called the “function call operator”. When we call a function, we often need to pass parameters, so this operator is used.
Therefore, if you want to make an object a functor, you only need to overload operator() in its class.
Use functors to implement ascending and descending order
First implement two classes: Greater and Less, which are used to define ascending order and descending order respectively (these two classes are implemented as templates).
Then add a template parameter compare in the priority_queue class. This parameter is used to receive the type of comparison method (whether ascending or descending order).
compare defaults to descending order. When we want to sort in ascending order, when passing parameters, instantiate an object of Greator type and pass it over.
//First implement the Less and Greater classes to define the size ratio rules
template<class T>
struct Less //less means getting smaller and smaller, that is, descending order
{
bool operator() (const T & amp; x, const T & amp; y) {
return x > y;
}
};
?
template<class T>
struct Greater //Ascending order
{
bool operator() (const T & amp; x, const T & amp; y) {
return x < y;
}
};
?
template<class T,class Container = vector<T>,class Compare=Less<T>> //Add template parameters, default is descending order
class priority_queue
{
Compare com;
public:
void AdjustUp(Container & amp; _con) {
int child = _con.size()-1;
int parent = (child - 1) / 2;
?
while (child > 0){
if (com(_con[child],_con[parent])) {
swap(_con[child], _con[parent]);
child = parent;
parent = (child - 1) / 2;
}
else {
break;
}
}
}
void AdjustDown(Container & amp; _con) {
Compare com;
int parent = 0;
int child = 2 * parent + 1;
?
while (child < _con.size()) {
if (child + 1 < _con.size() & amp; & com(_con[child + 1],_con[child])) {
child + + ;
}
?
if(com(_con[child], _con[parent])) {
swap(_con[parent], _con[child]);
parent = child;
child = 2 * parent + 1;
}
else {
break;
}
}
}
void push(const T & val) {
_con.push_back(val);
AdjustUp(_con);
}
void pop() {
swap(_con.front(), _con[_con.size()-1]);
_con.pop_back();
AdjustDown(_con);
}
…
};
Note: Because we have expanded the STL library, when naming Less/Greater, be careful not to write it as less/greater, otherwise it will have the same name as the one in the library, and the compiler will get confused and not know which one to use.
Test: sort in ascending order
#include"priority_queue.h"
using namespace jzy;
int main() {
priority_queue<int,vector<int>,Greater<int>> pq;
pq.push(7);
pq.push(3);
pq.push(8);
pq.push(2);
pq.push(12);
pq.push(6);
pq.push(3);
?
while (!pq.empty()) {
cout << pq.top() << " ";
pq.pop();
}
return 0;
}
Total code of simulation implementation
priority_queue.h:
#pragma once
#include<iostream>
#include<vector>
using namespace std;
namespace jzy
{
template<class T>
struct Less //less means getting smaller and smaller, that is, descending order
{
bool operator() (const T & amp; x, const T & amp; y) {
return x > y;
}
};
?
template<class T>
struct Greater //Ascending order
{
bool operator() (const T & amp; x, const T & amp; y) {
return x < y;
}
};
?
template<class T,class Container = vector<T>,class Compare=Less<T>>
class priority_queue
{
Compare com;
public:
void AdjustUp(Container & amp; _con) {
int child = _con.size()-1;
int parent = (child - 1) / 2;
?
while (child > 0){
if (com(_con[child],_con[parent])) {
swap(_con[child], _con[parent]);
child = parent;
parent = (child - 1) / 2;
}
else {
break;
}
}
}
void AdjustDown(Container & amp; _con) {
Compare com;
int parent = 0;
int child = 2 * parent + 1;
?
while (child < _con.size()) {
if (child + 1 < _con.size() & amp; & com(_con[child + 1],_con[child])) {
child + + ;
}
?
if(com(_con[child], _con[parent])) {
swap(_con[parent], _con[child]);
parent = child;
child = 2 * parent + 1;
}
else {
break;
}
}
}
void push(const T & val) {
_con.push_back(val);
AdjustUp(_con);
}
void pop() {
swap(_con.front(), _con[_con.size()-1]);
_con.pop_back();
AdjustDown(_con);
}
T top() {
return _con.front();
}
bool empty() {
return _con.empty();
}
size_t size() {
return _con.size();
}
?
private:
T_val;
Container_con;
};
}
4. deque double-ended queue
(Just understand this container, this container is rarely used)
Introduction
1.deque is the abbreviation of “double-ended queue”.
Although it is called a double-ended queue, it has nothing to do with a queue. Deque is a double-opened “continuous” space data structure. The meaning of double opening is that insertion and deletion operations can be performed at both ends, and the time complexity is O(1).
Deque supports random access and insertion and deletion at any position. It seems that deque combines the advantages of vector and list.
But, is deque really perfect?
Not really! The efficiency of deque random access is relatively low. As for why, let us first understand its underlying implementation.
Underlying Implementation
Unlike vector, the bottom layer of deque is not a continuous space in the true sense, but is made up of continuous small spaces. These small spaces are not necessarily continuous and may be located in different areas of the memory. As shown in the picture:
The map here is not the map container in STL. It is an array, and each element of the array is a pointer to another continuous space (buffer buffer). The elements we insert are actually stored in the buffer.
It can be seen that deque has a high space utilization rate and almost no waste of space.
How to expand the capacity?
When a buffer is full and tail insertion is required, the current buffer will not be expanded (because it has a fixed size), but a new buffer space will be opened, and the contents of the tail insertion will be stored in the new buffer. The next element of the pointer array points to the new buffer. The same goes for head plugs. The picture below can help us understand:
It can be seen that head insertion and tail insertion do not need to move data, and the efficiency is naturally high.
If the map is full, then open a larger map and copy the data to the new map.
Regarding the deque iterator, its principle is very complicated and consists of four pointers. node points to the pointer array of the central control area, first and node point to the beginning and end of a space respectively, and cur points to the accessed location. If the accessed element is not in the current space, cur is equal to first in the next space, and then the access continues.
When random access is required, the deque must first be completely copied to a vector, and then the deque must be copied after sorting the vector. This results in the random access efficiency of deque being lower than that of vector.
Summary about deque
Advantages:1. Compared with vector, deque’s head insertion and deletion do not require moving data, but directly open a new buffer and insert it, which is very efficient;
When expanding the capacity, there is no need to open new space or copy data. Instead, a new buffer is directly opened, which is highly efficient.
2. Compared with list, the bottom layer of deque is a continuous map array that stores pointers, which has higher space utilization and does not need to store additional fields. Moreover, deque also supports random access, although it is not efficient.
Disadvantages:1. Not suitable for traversal.
Because when traversing, the deque iterator needs to frequently detect whether it moves to the boundary of a certain small space, resulting in low efficiency.
In sequential scenarios, it may be necessary to traverse frequently. Therefore, in practice, when a linear structure is required, vector and list are given priority in most cases. There are not many applications of deque. One application that can be seen currently is that STL uses It serves as the underlying data structure of stack and queue.
2. The efficiency of intermediate insertion and deletion is not high. (Because the subscript needs to be calculated and the element needs to be moved)