stack container

concept

1. Stack (stack) is a first in and last out data structure
2. Only the top elements in the stack can be used by the outside world, so the stack is not allowed to traverse

Common interface

1. Constructor

1. stack<T> st; // Stack is implemented by template class, with default constructor
2. stack<T> st1(const stack &st); // copy constructor

2. Data access

1. push(elem); // Add an element to the top of the stack
2. pop(); // Remove an element from the top of the stack
3. top(); // Return stack top element

3. Assignment

1. stack& operator=(const stack &st); // Overloaded equal sign operator

4. Size operation

1. empty(); // Determine whether the stack is empty
2. size(); // Returns the size of the stack

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

int main() {

	// 1. Constructor
	stack<int> st;
	stack<int> st1;

	// 2. Data access and deletion
	// Deposit - in and out
	st.push(1);
	st.push(2);
	st.push(3);
	// Get stack top element
	cout << st.top() << endl; // 3
	// Delete stack top element
	st.pop();
	cout << st.top() << endl; // 2

	// 3. Assignment
	st1 = st;
	// Get stack top element
	cout << st1.top() << endl; // 2

	// 4. Size operation
	// Determine whether the stack is empty
	if (st.empty()) {
		cout << "Stack is empty!" << endl;
	}
	else {
		cout << "Stack is not empty!";
		// If the stack is not empty, the size of the stack is output
		cout << "，And the stack size is:" << st.size() << endl; // Stack is not empty!, And the stack size is: 2
	}

	// Take out all the elements in the stack in some way
	while (!st.empty()) { // As long as the stack is not empty, it enters the loop
		// Get stack top element
		cout << st.top() << " "; // 2 1
		// Delete stack top element
		st.pop();
	}
	cout << endl;

	system("pause");
	return 0;
}

queue container

concept

1. queue is a first in first out data type with two exits
2. Queue containers allow you to add elements from one end and remove elements from the other
3. Only the head and tail of the queue can be used by the outside world, so the queue cannot be traversed
4. The incoming data in the queue is called push; Out of queue data is called out of queue (pop)

Common interface

1. Constructor

1. queue<T> que; // Queue is implemented by template class with default constructor
2. queue<T> que1(const queue &que); // copy constructor

2. Data access

1. push(elem); // Add elements to the end of the queue
2. pop(); // Remove an element from the team head
3. front(); // Returns the first element
4. back(); // Returns the last element

3. Assignment

1. queue& operator=(const queue &que); // Overloaded equal sign operator

4. Size operation

1. empty(); // Determine whether the queue is empty
2. size(); // Returns the size of the queue

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

int main() {

	// 1. Constructor
	queue<int> que;
	queue<int> que1;

	// 2. Data access
	// Save
	que.push(1);
	que.push(2);
	que.push(3);
	// take
	// Take the first element of the team head
	cout << que.front() << endl; // 1
	// Take the first element at the end of the queue
	cout << que.back() << endl; // 3
	// Delete -- delete the first element of the team head
	que.pop();
	cout << que.front() << endl; // 2

	// 3. Assignment
	que1 = que;
	cout << que1.front() << endl; // 2

	// 4. Size operation
	// Determine whether the queue is empty
	if (que.empty()) {
		cout << "The queue is empty!" << endl;
	}
	else {
		cout << "Queue is not empty!";
		// If the queue is not empty, the size of the output queue
		cout << "，And the queue size is:" << que.size() << endl; // The queue is not empty!, And the queue size is: 2
	}

	// Take out all the elements in the queue in some way
	while (!que.empty()) { // When the queue is not empty, it enters the loop
		// Show queue header elements
		cout << que.front() << " "; // 2 3 
		// Delete queue header element
		que.pop();
	}
	cout << endl;

	system("pause");
	return 0;
}

list container

concept

>>List (linked list) can store data in a chain. The linked list in STL is a two-way circular linked list

>>Linked list (composed of a series of nodes) is a discontinuous storage structure on the physical storage unit. The logical order of data elements is realized through the pointers in the linked list

>>The node consists of two parts: one is the data field that stores the data element, and the other is the pointer field that stores the address of the next node

a key

1. Because the storage mode of the linked list is not a continuous memory space, the iterator in the linked list only supports forward and backward, which belongs to a two-way iterator
2. Nature: neither insert nor delete will invalidate the original list iterator, which is not true in other containers, such as vector

advantage

1. Dynamic storage allocation will not cause memory waste and overflow
2. It is very convenient to insert and delete the linked list. You can modify the pointer without moving a large number of elements

shortcoming

The linked list is flexible, but the additional cost of space (pointer field) and time (traversal) is large

summary

In STL, list and vector are the two most commonly used containers, each with advantages and disadvantages

list constructor

Function prototype

1. list<T> li; // List is implemented by template class, and the default constructor is
2. list<T> li1(li.begin(), li.end()); // The constructor copies the container Li interval element to itself
3. list<T> li(n, elem); // The constructor copies n elems to itself
4. list<T> li1(const list &li); // copy constructor

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

void PrintList(list<int> &li) {
	// Traversing the list container with iterators
	for (list<int>::iterator it = li.begin(); it != li.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}

int main() {

	// 1. Constructor
	list<int> li;
	// insert data
	for (int i = 0; i < 5; i++) {
		li.push_back(i + 1);
	}
	// Print elements in container list
	PrintList(li); // 1 2 3 4 5

	// 2. The constructor copies the container li interval element to itself
	list<int> li1(li.begin(), li.end());
	PrintList(li1); // 1 2 3 4 5

	// 3. The constructor copies n elem s to itself
	list<int> li2(6, 6);
	PrintList(li2); // 6 6 6 6 6 6

	// 4. Copy constructor
	list<int> li3(li2);
	PrintList(li3); // 6 6 6 6 6 6

	system("pause");
	return 0;
}

list assignment and exchange

Function prototype

1. list& operator=(const list &li); // Overload assignment operator
2. li1.assign(li.begin(), li.end()); // Copy the data in the [begin, end] interval to itself
3. li1.assign(n, elem); // Assign n elem copies to itself
4. li1.swap(li); // The elements of containers Li and Li1 are interchanged

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

void PrintList(list<int> &li) {
	// Traversing the list container with iterators
	for (list<int>::iterator it = li.begin(); it != li.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}

int main() {

	// Constructor
	list<int> li;
	list<int> li1;
	list<int> li2;
	list<int> li3;
	// insert data
	for (int i = 0; i < 5; i++) {
		li.push_back(i + 1);
	}
	PrintList(li); // 1 2 3 4 5

	// 1. Overload assignment operator
	li1 = li;
	PrintList(li1); // 1 2 3 4 5

	// 2. assign -- copy capacity li interval elements
	// li2.assign(li.begin(), li.begin() + 3); //  Bidirectional iterator, random access is not supported
	li2.assign(li.begin(), ++li.begin());
	PrintList(li2); // 1

	// 3. assign -- copy n elem s to itself
	li3.assign(6, 6);
	PrintList(li3); // 6 6 6 6 6 6

	// 4. Interchange containers - li3 and li
	li.swap(li3);
	PrintList(li); // 6 6 6 6 6 6
	PrintList(li3); // 1 2 3 4 5

	system("pause");
	return 0;
}

list size

Function prototype

1. empty(); // Determine whether the container is empty
2. size(); // The size of the container
3. resize(int num); // Re specify the length of the container as num. if the container becomes longer, fill the new position with the default value; If the container becomes shorter, elements whose end exceeds the length of the container are deleted
4. resize(int num, elem); // Reassign the length of the container to num. if the container becomes longer, fill the new position with elem; If the container becomes shorter, elements whose end exceeds the length of the container are deleted

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

void PrintList(list<int> &li) {
	// Traversing the list container with iterators
	for (list<int>::iterator it = li.begin(); it != li.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}

int main() {

	// Constructor
	list<int> li;

	// 1. Judge whether the container is empty
	if (li.empty()) {
		cout << "The container is empty!" << endl; // The container is empty!
	}

	// insert data
	for (int i = 0; i < 5; i++) {
		li.push_back(i + 1);
	}
	PrintList(li); // 1 2 3 4 5

	// 2. Output container size
	cout << li.size() << endl; // 5

	// 3. Reassign the container length
	// Variable length -- fills the new location with the default value (0)
	li.resize(10);
	// Output data in container 
	PrintList(li); // 1 2 3 4 5 0 0 0 0 0
	// Shorter -- elements exceeding the length will be deleted
	li.resize(3);
	// Output data in container 
	PrintList(li); // 1 2 3

	// 4. Reassign the default values for container length and new location
	// Become -- fill the new position with the second parameter num
	li.resize(5, 666);
	PrintList(li); // 1 2 3 666 666
	// Shorter -- elements exceeding the length will be deleted
	li.resize(2);
	// Output data in container 
	PrintList(li); // 1 2

	system("pause");
	return 0;
}

list insert and delete

Function prototype

1. Two end insertion and deletion

1. push_back(elem); // Insert an element at the end of the container
2. push_front(elem); // Insert an element in the head of the container
3. pop_back(); // Delete the first element at the end of the container
4. pop_front(); // Delete the first element of the container header

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

void PrintList(list<int> &li) {
	// Traversing the list container with iterators
	for (list<int>::iterator it = li.begin(); it != li.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}

int main() {

	// Constructor
	list<int> li;

	// 1. Insert the element at the end of the container
	li.push_back(1);
	li.push_back(2);
	li.push_back(3);
	PrintList(li); // 1 2 3

	// 2. Insert the element in the head of the container
	li.push_front(4);
	li.push_front(5);
	li.push_front(6);
	PrintList(li); // 6 5 4 1 2 3

	// 3. Delete the first element of the container header
	li.pop_front();
	PrintList(li); // 5 4 1 2 3

	// 3. Delete the first element at the end of the container
	li.pop_back();
	PrintList(li); // 5 4 1 2

	system("pause");
	return 0;
}

2. Insert and delete at the specified location

1. insert(const_iterator pos, elem); // The iterator points to the POS insert element
2. insert(const_iterator pos, n, elem); // The iterator inserts n elements into POS
3. insert(const_iterator pos, li.begin(), li.end()); // Insert the container Li interval element into the POS position pointed to by the iterator
4. erase(const_iterator pos); // Delete the element pointed to by the iterator
5. erase(const_iterator start, const_iterator end); // Delete the element that the iterator points to from start to end
6. remove(elem); // Delete all elements in the container that match elem
7. clear(); // Empty container

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

void PrintList(list<int> &li) {
	// Traversing the list container with iterators
	for (list<int>::iterator it = li.begin(); it != li.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}

int main() {

	// Constructor
	list<int> li;
	// Tail interpolation
	li.push_back(1);
	li.push_back(2);
	li.push_back(3);
	PrintList(li); // 1 2 3

	// 1. The iterator points to the position pos to insert the element
	li.insert(li.begin(), 4);
	PrintList(li); // 4 1 2 3

	// 2. The iterator points to the position pos and inserts n elements
	li.insert(li.end(), 5, 6);
	PrintList(li); // 4 1 2 3 6 6 6 6 6

	// 3. Insert the capacity li interval element into the iterator and point to the position pos
	li.insert(++li.begin(), ++li.begin(), --li.end());
	PrintList(li); // 4 1 2 3 6 6 6 6 1 2 3 6 6 6 6 6

	// 4. Delete the position pos pointed by the iterator
	li.erase(li.begin());
	PrintList(li); // 1 2 3 6 6 6 6 1 2 3 6 6 6 6 6

	// 5. Delete the elements from start to end pointed by the iterator
	li.erase(++li.begin(), --(--li.end())); 
	PrintList(li); // 1 6 6

	// 6. Delete all elements matching elem in the container
	li.remove(6);
	PrintList(li); // 1 

	// 7. Empty the container
	li.clear();
	PrintList(li); // empty

	system("pause");
	return 0;
}

list data access

Function prototype

1. front(); // Returns the first element of the container
2. back(); // Returns the last element of the container

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

void PrintList(list<int> &li) {
	// Traversing the list container with iterators
	for (list<int>::iterator it = li.begin(); it != li.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}

int main() {

	// Constructor
	list<int> li;
	// Tail interpolation
	li.push_back(1);
	li.push_back(2);
	li.push_back(3);
	PrintList(li); // 1 2 3

	// 1. Return the first element of the container
	cout << li.front() << endl; // 1

	// 2. Return the last element of the container
	cout << li.back() << endl; // 3

	system("pause");
	return 0;
}

list inversion and sorting

Function prototype

1. reverse(); // Reverse linked list
2. sort(); // Sort linked list

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

void PrintList(list<int> &li) {
	// Traversing the list container with iterators
	for (list<int>::iterator it = li.begin(); it != li.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}

int main() {

	// Constructor
	list<int> li;
	// Tail interpolation
	li.push_back(1);
	li.push_back(7);
	li.push_back(3);
	li.push_back(5);
	li.push_back(6);
	PrintList(li); // 1 7 3 5 6	
		
	// 1. Reverse linked list
	li.reverse();
	PrintList(li); // 6 5 3 7 1

	// 2. Sort linked list
	li.sort();
	PrintList(li); // 1 3 5 6 7

	system("pause");
	return 0;
}

list sort case