第 16.5 節

stack / queue / list containers

0瀏覽次數0訪問次數--跳出率--平均停留

Stack container

stack 基本概念

Concept: A stack is a First In Last Out (FILO) data structure that only has one exit point.

Description: 11-15-2015_195707

Only the top element of the stack is accessible from the outside, so traversal is not permitted.

Data entering the stack is called --- stack push push

Popping data from a stack is called --- popping pop

Stacks in daily life:

Common interfaces of a stack.

Function Description: Common public interfaces for stack container

Constructor:

stack<T> stk; //stack is implemented using a template class; the default construction form of stack objects
stack(const stack &stk); //copy constructor

Assignment operation:

stack& operator=(const stack &stk); //overloading the equality operator

Data Access:

push(elem); //Add an element to the top of the stack
pop(); //Remove the first element from the top of the stack
top(); //return the top element of the stack

Size Operations:

empty(); //Check if the stack is empty
size(); //return stack size

Example:

#include <stack>

//栈容器常用接口
void test01()
{
    //创建栈容器 栈容器必须符合先进后出
    stack<int> s;

    //向栈中添加元素，叫做 压栈 入栈
    s.push(10);
    s.push(20);
    s.push(30);

    while (!s.empty()) {
        //输出栈顶元素
        cout << "栈顶元素为： " << s.top() << endl;
        //弹出栈顶元素
        s.pop();
    }
    cout << "栈的大小为：" << s.size() << endl;

}

int main() {

    test01();


    return 0;
}

Running/Observation Results: After running, the corresponding content will be printed according to the output statements. The variable values can be inferred based on the order of initialization, assignment, and function calls.

Summary:

Push ---入栈
Pop --- 出栈
return top of stack --- top
Check if the stack is empty --- empty
Return stack size

queue container

Queue Basic Concepts

Concept: A Queue is a First In First Out (FIFO) data structure, which has two ends.

Description: 2015-11-15_214429

Queue container allows adding elements from one end and removing elements from the other end.

In a queue, only the head and tail are accessible to external operations, which means that queue does not permit traversal behavior.

Adding data to a queue is called --- enqueue push

Removing data from a queue is called --- dequeue pop

Queues in Life:

1547606785041

Common interfaces for queue

Function Description: Common public interfaces for stack container

Constructor:

queue<T> que; //queue is implemented using template classes, the default constructor form for queue objects
queue(const queue &que); //copy constructor

Assignment operation:

queue& operator=(const queue &que); //overloading the equality operator

Data Access:

push(elem); //add elements to the end of the queue
pop(); //Remove the first element from the front of the queue
back(); //Returns the last element
front(); //return the first element

Size Operations:

empty(); //Check if the stack is empty
size(); //return stack size

Example:

#include <queue>
#include <string>
class Person
{
public:
    Person(string name, int age)
    {
        this->m_Name = name;
        this->m_Age = age;
    }

    string m_Name;
    int m_Age;
};

void test01() {

    //创建队列
    queue<Person> q;

    //准备数据
    Person p1("唐僧", 30);
    Person p2("孙悟空", 1000);
    Person p3("猪八戒", 900);
    Person p4("沙僧", 800);

    //向队列中添加元素  入队操作
    q.push(p1);
    q.push(p2);
    q.push(p3);
    q.push(p4);

    //队列不提供迭代器，更不支持随机访问 
    while (!q.empty()) {
        //输出队头元素
        cout << "队头元素-- 姓名： " << q.front().m_Name 
              << " 年龄： "<< q.front().m_Age << endl;
        
        cout << "队尾元素-- 姓名： " << q.back().m_Name  
              << " 年龄： " << q.back().m_Age << endl;
        
        cout << endl;
        //弹出队头元素
        q.pop();
    }

    cout << "队列大小为：" << q.size() << endl;
}

int main() {

    test01();


    return 0;
}

Running/Observing the results: After running, the example will print variable values or addresses; address values depend on the runtime environment, so focus on observing the relative positioning and pointer changes of similar objects.

Summary:

Enqueue --- push
dequeue --- pop
Return the front element --- front
Return the element at the back of the queue --- back
Check if the queue is empty --- empty
Return queue size --- size

list container

A list is an ordered, mutable collection of items in programming, allowing duplicates and indexed access. It supports operations like adding, removing, and accessing elements by position.

Function: Chain storage of data.

Linked list is a non-contiguous storage structure in physical memory, where the logical order of data elements is achieved through pointer links within the list.

The composition of a linked list: a linked list consists of a series of nodes.

The composition of a node consists of two parts: one is the data field that stores data elements, and the other is the pointer field that stores the address of the next node.

The list in the STL is a doubly circular linked list.

Description: 2015-11-15_225145

Due to the non-contiguous memory storage of linked lists, iterators in a list only support moving forward and backward, making them bidirectional iterators.

Advantages of a list:

Efficient for sequential access and iteration.
Supports dynamic resizing (grows or shrinks as needed).
Easy to insert or remove elements at any position (especially with linked lists).
Provides a flexible way to store and manage collections of data.

Uses dynamic memory allocation to prevent memory waste and overflow.
Linked lists are very convenient for performing insertion and deletion operations, as modifying pointers is sufficient rather than needing to move a large number of elements.

Disadvantages of lists:

Linked lists are flexible, but they come with extra overhead in space (pointer fields) and time (traversal).

An important property of list is that insert and delete operations do not invalidate existing list iterators, which is not the case with vector.

In summary, list and vector are the two most commonly used containers in STL, each with its own advantages and disadvantages.

list constructor

Description:

Create a list container.

Function prototype:

list<T> lst; //list implemented using template classes; the default construction form of an object:
list(beg,end); //The constructor copies the elements in the range [beg, end) to itself.
list(n,elem); //The constructor copies n elements to itself.
list(const list &lst); //Copy constructor.

Example:

#include <list>

void printList(const list<int>& L) {

    for (list<int>::const_iterator it = L.begin(); it != L.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;
}

void test01()
{
    list<int>L1;
    L1.push_back(10);
    L1.push_back(20);
    L1.push_back(30);
    L1.push_back(40);

    printList(L1);

    list<int>L2(L1.begin(),L1.end());
    printList(L2);

    list<int>L3(L2);
    printList(L3);

    list<int>L4(10, 1000);
    printList(L4);
}

int main() {
    // 程序从 main 函数开始执行，下面的语句会按顺序运行。

    test01();


    // 返回 0 表示程序正常结束。
    return 0;
}

Summary: The construction method for list is similar to other commonly used STL containers; familiarize yourself with it.

list assignment and swap

Description:

Assigning values to a list container and swapping list containers.

Function prototype:

assign(beg, end); // Copies the data in the range [beg, end) to itself.
assign(n, elem); // Copies n elements to itself.
list& operator=(const list &lst); //overloading the equality operator
swap(lst); //Swap the list elements with themselves.

Example:

#include <list>

void printList(const list<int>& L) {

    for (list<int>::const_iterator it = L.begin(); it != L.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;
}

//赋值和交换
void test01()
{
    list<int>L1;
    L1.push_back(10);
    L1.push_back(20);
    L1.push_back(30);
    L1.push_back(40);
    printList(L1);

    //赋值
    list<int>L2;
    L2 = L1;
    printList(L2);

    list<int>L3;
    L3.assign(L2.begin(), L2.end());
    printList(L3);

    list<int>L4;
    L4.assign(10, 100);
    printList(L4);

}

//交换
void test02()
{

    list<int>L1;
    L1.push_back(10);
    L1.push_back(20);
    L1.push_back(30);
    L1.push_back(40);

    list<int>L2;
    L2.assign(10, 100);

    cout << "交换前： " << endl;
    printList(L1);
    printList(L2);

    cout << endl;

    L1.swap(L2);

    cout << "交换后： " << endl;
    printList(L1);
    printList(L2);

}

int main() {

    //test01();

    test02();


    return 0;
}

Summary: List assignment and swap operations can be used flexibly.

List Size Operations

Description:

Perform operations on the size of the list container.

Function prototype:

size(); // Returns the number of elements in the container
empty(); //Determine whether the container is empty
resize(num); //Reassign the container's length to num; if the container lengthens, fill the new positions with default values.

// If the container becomes shorter, elements at the end that exceed the container length are deleted.

resize(num, elem); // Resize the container to length num, filling any new positions with the value of elem if the container expands.

// If the container becomes shorter, elements at the end that exceed the container length are deleted.

Example:

#include <list>

void printList(const list<int>& L) {

    for (list<int>::const_iterator it = L.begin(); it != L.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;
}

//大小操作
void test01()
{
    list<int>L1;
    L1.push_back(10);
    L1.push_back(20);
    L1.push_back(30);
    L1.push_back(40);

    if (L1.empty())
    {
        cout << "L1为空" << endl;
    }
    else
    {
        cout << "L1不为空" << endl;
        cout << "L1的大小为： " << L1.size() << endl;
    }

    //重新指定大小
    L1.resize(10);
    printList(L1);

    L1.resize(2);
    printList(L1);
}

int main() {

    test01();


    return 0;
}

Summary:

Check if empty --- empty
return element count --- size
Reset the count --- resize

list insertion and deletion

Description:

Performing data insertion and deletion on list containers

Function prototype:

push_back(elem);//add an element at the end of the container
pop_back();//Remove the last element from the container
push_front(elem);// Inserts an element at the front of the container.
pop_front(); // Remove the first element from the beginning of the container
insert(pos,elem); // Inserts a copy of the element at the given position, returns the position of the new data.
insert(pos,n,elem); // Inserts n copies of elem at position pos, with no return value.
insert(pos, beg, end); // Insert data from the range [beg, end) at position pos; no return value.
clear(); //Remove all data from the container
erase(beg,end);//Removes elements in the range [beg,end) and returns the position of the next element.
erase(pos);// Delete data at the specified position and return the position of the next data.
Removes all elements from the container that match the value of elem.

Example:

#include <list>

void printList(const list<int>& L) {

    for (list<int>::const_iterator it = L.begin(); it != L.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;
}

//插入和删除
void test01()
{
    list<int> L;
    //尾插
    L.push_back(10);
    L.push_back(20);
    L.push_back(30);
    //头插
    L.push_front(100);
    L.push_front(200);
    L.push_front(300);

    printList(L);

    //尾删
    L.pop_back();
    printList(L);

    //头删
    L.pop_front();
    printList(L);

    //插入
    list<int>::iterator it = L.begin();
    L.insert(++it, 1000);
    printList(L);

    //删除
    it = L.begin();
    L.erase(++it);
    printList(L);

    //移除
    L.push_back(10000);
    L.push_back(10000);
    L.push_back(10000);
    printList(L);
    L.remove(10000);
    printList(L);
    
    //清空
    L.clear();
    printList(L);
}

int main() {

    test01();


    return 0;
}

Summary:

Tail insertion --- push_back
Pop back --- pop_back
push_front --- 头插
delete from front --- pop_front
insert
erase
Remove
clear

list data access

Description:

Accessing data within a list container.

Function prototype:

front(); //return the first element.
back(); //Return the last element.

Example:

#include <list>

//数据存取
void test01()
{
    list<int>L1;
    L1.push_back(10);
    L1.push_back(20);
    L1.push_back(30);
    L1.push_back(40);

    
    //cout << L1.at(0) << endl;//错误 不支持at访问数据
    //cout << L1[0] << endl; //错误  不支持[]方式访问数据
    cout << "第一个元素为： " << L1.front() << endl;
    cout << "最后一个元素为： " << L1.back() << endl;

    //list容器的迭代器是双向迭代器，不支持随机访问
    list<int>::iterator it = L1.begin();
    //it = it + 1;//错误，不可以跳跃访问，即使是+1
}

int main() {

    test01();


    return 0;
}

Summary:

Data in a list container cannot be accessed via or at() methods.
Return the first element --- front
return the last element

list reverse and sort

Description:

Reverse the elements in the container, and sort the data within it.

Function prototype:

reverse(); // reverse a linked list
sort(); //linked list sorting

Example:

void printList(const list<int>& L) {

    for (list<int>::const_iterator it = L.begin(); it != L.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;
}

bool myCompare(int val1 , int val2)
{
    return val1 > val2;
}

//反转和排序
void test01()
{
    list<int> L;
    L.push_back(90);
    L.push_back(30);
    L.push_back(20);
    L.push_back(70);
    printList(L);

    //反转容器的元素
    L.reverse();
    printList(L);

    //排序
    L.sort(); //默认的排序规则 从小到大
    printList(L);

    L.sort(myCompare); //指定规则，从大到小
    printList(L);
}

int main() {

    test01();


    return 0;
}

Summary:

reverse --- reverse
Sort --- sort (member function)

## Sorting example

Case description: Sorting a custom Person data type, where Person has attributes: name, age, and height.

Sort by age in ascending order; if ages are the same, sort by height in descending order.

Example:

#include <list>
#include <string>
class Person {
public:
    Person(string name, int age , int height) {
        m_Name = name;
        m_Age = age;
        m_Height = height;
    }

public:
    string m_Name;  //姓名
    int m_Age;      //年龄
    int m_Height;   //身高
};

bool ComparePerson(Person& p1, Person& p2) {

    if (p1.m_Age == p2.m_Age) {
        return p1.m_Height  > p2.m_Height;
    }
    else
    {
        return  p1.m_Age < p2.m_Age;
    }

}

void test01() {

    list<Person> L;

    Person p1("刘备", 35 , 175);
    Person p2("曹操", 45 , 180);
    Person p3("孙权", 40 , 170);
    Person p4("赵云", 25 , 190);
    Person p5("张飞", 35 , 160);
    Person p6("关羽", 35 , 200);

    L.push_back(p1);
    L.push_back(p2);
    L.push_back(p3);
    L.push_back(p4);
    L.push_back(p5);
    L.push_back(p6);

    for (list<Person>::iterator it = L.begin(); it != L.end(); it++) {
        cout << "姓名： " << it->m_Name << " 年龄： " << it->m_Age 
              << " 身高： " << it->m_Height << endl;
    }

    cout << "---------------------------------" << endl;
    L.sort(ComparePerson); //排序

    for (list<Person>::iterator it = L.begin(); it != L.end(); it++) {
        cout << "姓名： " << it->m_Name << " 年龄： " << it->m_Age 
              << " 身高： " << it->m_Height << endl;
    }
}

int main() {

    test01();


    return 0;
}

Summary:

When dealing with custom data types, it's essential to define a sorting rule; otherwise, the compiler won't know how to sort the elements.
Advanced sorting simply adds another layer of logical rules on top of the sorting criteria, and it's not complex.