文章目錄

• 注意事項
• • 1 emplace 與 push 的區(qū)別
• 一、stack（棧）（先進后出、【頭部插入、刪除】、不許遍歷）
• • 1 基本概念（棧是自頂向下(top在下)，堆是向上）
  • 2 stack 常用接口（構(gòu)造函數(shù)、賦值操作、數(shù)據(jù)存儲、empty、size）
• 二、queue （隊列）（先進先出、【頭部刪除、尾部插入】、不許遍歷）
• • 1 queue 基本概念[kju:]
  • 2 queue 常用接口（構(gòu)造函數(shù)、賦值操作、數(shù)據(jù)存儲、empty、size）
  • 3 priority_queue
  • • 3.1 用pair＜int,int＞建立優(yōu)先隊列（小根堆）
• 三、list（最常用）（雙向迭代器、單向鏈表/雙向循環(huán)鏈表、可以遍歷）
• • 1 list基本概念（插入刪除效率高，隨機存儲不行）
  • 2 list構(gòu)造函數(shù)（默認(rèn)構(gòu)造、區(qū)間拷貝、n個元素拷貝、拷貝）
  • 3 list 賦值和交換（operator=、assign、swap）
  • 4 list 大小操作 (size、emply、resize) (無容量capacity)
  • 5 list 插入和刪除 (insert、erase、remove（移除指定數(shù)據(jù)）、clear)（迭代器找位置）
  • 6 list 數(shù)據(jù)存取（front、back、不支持[ ]和at的方式)（迭代器找位置）
  • 7 list 反轉(zhuǎn)和排序（L.reverse()(反轉(zhuǎn))、L.sort()（排序，鏈表內(nèi)部提供））

創(chuàng)新互聯(lián)公司-專業(yè)網(wǎng)站定制、快速模板網(wǎng)站建設(shè)、高性價比賓縣網(wǎng)站開發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫,直接使用。一站式賓縣網(wǎng)站制作公司更省心,省錢,快速模板網(wǎng)站建設(shè)找我們，業(yè)務(wù)覆蓋賓縣地區(qū)。費用合理售后完善，十年實體公司更值得信賴。注意事項

注意：

1. 所有不支持隨機訪問迭代器的容器，不可以用標(biāo)準(zhǔn)算法（自帶的全局函數(shù)）（eg. sort()）
2. stack 和 queue(priority_queue) 不支持 clear() 函數(shù)

while (!que.empty()) // 有clear()功能
{que.pop();
}

1 emplace 與 push 的區(qū)別

1.直接傳入對象（int, double 或者 構(gòu)造好了的對象）

//假設(shè)棧內(nèi)的數(shù)據(jù)類型是data
class data {int a;
  int b;
public:
  data(int x, int y):a(x), b(y) {}
};
//push
data d(1,2);
stackS;
S.push(d) 或 S.emplace(d);

2.在傳入時候構(gòu)造對象

S.push(data(1,2));
S.emplce(data(1,2));

3.emplace可以直接傳入構(gòu)造對象需要的元素，然后自己調(diào)用其構(gòu)造函數(shù)！

S.emplace(1,2)

意思是，emplace這樣接受新對象的時候，自己會調(diào)用其構(gòu)造函數(shù)生成對象然后放在容器內(nèi)（比如這里傳入了1，2，它則會自動調(diào)用一次data(1,2))，而push，只能讓其構(gòu)造函數(shù)構(gòu)造好了對象之后，再使用拷貝構(gòu)造函數(shù)！相當(dāng)于emplace直接把原料拿進家，造了一個。而push是造好了之后，再復(fù)制到自己家里，多了復(fù)制這一步。所以emplace相對于push，使用第三種方法會更節(jié)省內(nèi)存。

注意：
emplace_back(type) 對應(yīng) push_back(type)
emplace(i, type) 對應(yīng)于 insert(type, i)
emplace_front(type) 對應(yīng)于 push_front()

---

一、stack（棧）（先進后出、【頭部插入、刪除】、不許遍歷） 1 基本概念（棧是自頂向下(top在下)，堆是向上）

• stack是一種先進后出(First In Last Out,FILO)的數(shù)據(jù)結(jié)構(gòu)，它只有一個出口（棧容器）
• 棧中只有頂端向下的元素才可以被外界使用，因此棧不允許有遍歷行為

棧中進入數(shù)據(jù)稱為 ——入棧  s.push（）
棧中彈出數(shù)據(jù)稱為 ——出棧  s.pop（）

2 stack 常用接口（構(gòu)造函數(shù)、賦值操作、數(shù)據(jù)存儲、empty、size）

//構(gòu)造函數(shù)
stacks;? ? ? //stack采用類模板實現(xiàn)， stack對象的默認(rèn)構(gòu)造形式                                           
stacks1(s); ?//拷貝構(gòu)造函數(shù)
//賦值操作
s=s1;? ?          //重載等號操作符
//數(shù)據(jù)存取
s.push(40);? ? ?//向棧頂添加元素
s.pop();? ? ? ? //從棧頂移除第一個元素 
s.top() ? ?     //返回棧頂元素值
//大小操作
s.empty() ? ? ? //判斷堆棧是否為空
s.size()? ? ? ? //返回棧的大小（元素個數(shù)）

#include//棧容器常用接口
void test01()
{//特點：符合先進后出數(shù)據(jù)結(jié)構(gòu)
    stacks;
 
    //向棧中添加元素，叫做 壓棧 入棧
    s.push(10);
    s.push(20);
    s.push(30);
    s.push(40);
 
    cout<< "棧的大小為："<< s.size()<< endl;
    //只要棧不為空，查看棧頂，并且執(zhí)行出棧操作
    while (!s.empty()) {//輸出棧頂元素
        cout<< "棧頂元素為： "<< s.top()<< endl;
        //彈出棧頂元素
        s.pop();
    }
    cout<< "棧的大小為："<< s.size()<< endl;
 
}
 
int main() {test01();
 
    system("pause");
 
    return 0;
}

二、queue （隊列）（先進先出、【頭部刪除、尾部插入】、不許遍歷） 1 queue 基本概念[kju:]

• Queue是一種先進先出(First In First Out,FIFO)的數(shù)據(jù)結(jié)構(gòu)，它有兩個出口（隊列容器）
• 隊列容器允許從隊尾新增元素，從另隊頭移除元素
• 隊列中只有隊頭和隊尾才可以被外界使用，因此隊列不允許有遍歷行為

隊列中進數(shù)據(jù)稱為 — 入隊 q.push（）
隊列中出數(shù)據(jù)稱為 — 出隊 q.pop（）

2 queue 常用接口（構(gòu)造函數(shù)、賦值操作、數(shù)據(jù)存儲、empty、size）

//構(gòu)造函數(shù)
queueq; ? ?  //queue采用類模板實現(xiàn)，queue對象的默認(rèn)構(gòu)造形式                                  
queueq1（q）; //拷貝構(gòu)造函數(shù)
//賦值操作
q=q1; ? ? ?         //重載等號操作符
//數(shù)據(jù)存取
q.push(p1); ? ? ? ?  //往隊尾添加元素
q.pop(); ? ? ? ?     //從隊頭移除第一個元素
q.back(); ? ? ?      //返回最后一個元素值
q.front() ? ? ?      //返回第一個元素值
//大小操作
q.empty() ? ? ? ?      //判斷堆棧是否為空
q.size() ? ? ? ?       //返回棧的大小

#include#include 
class Person
{public:
    Person(string name, int age)
    {this->m_Name = name;
        this->m_Age = age;
    }
 
    string m_Name;
    int m_Age;
};
 
//隊列 Queue
void test01() {//創(chuàng)建隊列
    queueq;
 
    //準(zhǔn)備數(shù)據(jù)
    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();
 
    system("pause");
 
    return 0;
}

3 priority_queue 3.1 用pair＜int,int＞建立優(yōu)先隊列（小根堆）

• 比較對象是pair的第一個元素

priority_queue,vector>,greater>>pq;

• 取元素

1.pq.top().first;
2.pq.top().second;

三、list（最常用）（雙向迭代器、單向鏈表/雙向循環(huán)鏈表、可以遍歷） 1 list基本概念（插入刪除效率高，隨機存儲不行）

• 鏈表（list）：是一種物理存儲單元上非連續(xù)的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接實現(xiàn)的（指針域）
• STL中的鏈表是一個雙向循環(huán)鏈表，由于鏈表的存儲方式并不是連續(xù)的內(nèi)存空間，因此鏈表list中的迭代器只支持前移和后移，屬于雙向迭代器，只支持it++、it-- ，不支持 it = it + 1（不能跳躍式的訪問）

（1）鏈表的組成：鏈表由一系列結(jié)點組成
（2）結(jié)點的組成：一個是存儲數(shù)據(jù)元素的數(shù)據(jù)域，一個是存儲下一個結(jié)點地址的指針域
（3）list的優(yōu)點：

• 采用動態(tài)存儲分配，不會造成內(nèi)存浪費和溢出
• 鏈表執(zhí)行插入和刪除操作十分方便，修改指針即可，不需要移動大量元素

（4）list的缺點：

• 容器遍歷速度沒有數(shù)組快
• 鏈表靈活，但是空間(指針域) 和 時間（遍歷）額外耗費較大

（5）List有一個重要的性質(zhì)：

• 插入操作和刪除操作都不會造成原有l(wèi)ist迭代器的失效，這在vector是不成立的（vector會從新找一塊更長的存儲空間，原有迭代器失效）

總結(jié)：STL中List和vector是兩個最常被使用的容器，各有優(yōu)缺點

1. 兩個指針，next指針指向下一個節(jié)點，prev指針指向上一個節(jié)點（雙向）
2. 最后一個節(jié)點記錄第一個節(jié)點的位置，前一個節(jié)點記錄最后一個節(jié)點的位置（循環(huán)）

2 list構(gòu)造函數(shù)（默認(rèn)構(gòu)造、區(qū)間拷貝、n個元素拷貝、拷貝）

listL1;? ? ? ?                 //list采用類模板實現(xiàn)，對象的默認(rèn)構(gòu)造形式：                                
listL2(L1.begin(), L1.end());? //構(gòu)造函數(shù)將[beg, end)區(qū)間中的元素拷貝給本身。                                
listL4(5, 10); ?              //構(gòu)造函數(shù)將5個10拷貝給本身
listL3(L2); ?                 //拷貝構(gòu)造函數(shù)。

//list容器的構(gòu)造
void printList(const list& L) { //只讀迭代器
    for (list::const_iterator it = L.begin(); it != L.end(); it++) {cout<< *it<< " ";
    }
    cout<< endl;
}
 
void test01()
{//創(chuàng)建list容器
    listL1;//默認(rèn)構(gòu)造
 
    //添加數(shù)據(jù)
    L1.push_back(10);
    L1.push_back(20);
    L1.push_back(30);
    L1.push_back(40);
 
    printList(L1);
 
    //區(qū)間方式
    listL2(L1.begin(), L1.end());
    printList(L2);
 
    //拷貝構(gòu)造
    listL3(L2);
    printList(L3);
 
    //n個elem
    listL4(10, 1000);
    printList(L4);
}
 
int main() {test01();
 
    system("pause");
 
    return 0;
}

3 list 賦值和交換（operator=、assign、swap）

//assign 賦值函數(shù)
L3.assign(L2.begin(), L2.end());  //將[beg, end)區(qū)間中的數(shù)據(jù)拷貝賦值給本身。
L4.assign(10, 100);? ?            //將n個elem拷貝賦值給本身。
//operator= 重載
L2 = L1;? ? ? ?      //重載等號操作符
//swap 互換函數(shù)
L1.swap(L2);? ? ? ?  //將L1與L2的元素互換。

4 list 大小操作 (size、emply、resize) (無容量capacity)

//(無容量capacity)
L1.size()     //返回容器中元素的個數(shù)
L1.empty()    //判斷容器是否為空

//resize 重新指定容器的長度（大?。?L1.resize(10); //10個0
//重新指定容器的長度為10，若容器變長，則以默認(rèn)值0填充新位置。
//如果容器變短，則末尾超出容器長度的元素被刪除。
L1.resize(10,1000); //10個1000
//重新指定容器的長度為10，若容器變長，則以1000值填充新位置。
//如果容器變短，則末尾超出容器長度的元素被刪除。

5 list 插入和刪除 (insert、erase、remove（移除指定數(shù)據(jù)）、clear)（迭代器找位置）

• 最好把鏈表當(dāng)作動態(tài)的雙端數(shù)組（deque）來使用，只訪問或者增刪頭端或者尾端的數(shù)據(jù)，這樣速度快

//it表示某個迭代器，n為整數(shù)。該函數(shù)的功能是將it迭代器前進或后退n個位置。
//n為正數(shù)時表示將it右移（前進）n個位置，n為負(fù)數(shù)時表示將it左移（后退）n個位置
#includeusing namespace std;
advance(it, n);  // 要判斷 n 是否越界 （雙向循環(huán)鏈表也要防止越界）   

Data.insert(it, tem2); //插入數(shù)據(jù)
Data.erase(it);        //刪除數(shù)據(jù)

//兩端插入、刪除操作
L.push_back(10);???? //在容器尾部加入一個元素
L.pop_back();???     //刪除容器中最后一個元素
L.push_front(100);?? //在容器開頭插入一個元素
L.pop_front();???    //從容器開頭移除第一個元素

//insert 指定位置插入
list::iterator it;
L.insert(it, 10);?        //在迭代器位置插10元素，返回新數(shù)據(jù)的位置。
L.insert(it, 2, 10);      //在迭代器位置插入2個10數(shù)據(jù)，無返回值。
L.insert(it, L2.begin(), L2.end());??//在迭代器位置插入[beg,end)區(qū)間的數(shù)據(jù)，無返回值。

//erase 指定位置刪除
L.erase(L.begin(), L.end());?//刪除[beg,end)區(qū)間的數(shù)據(jù)，返回下一個數(shù)據(jù)的位置。
L.erase(it);?       ? //刪除迭代器位置的數(shù)據(jù)，返回下一個數(shù)據(jù)的位置。

//remove 移除指定數(shù)據(jù)（特有）
L.remove(100);????  //刪除容器中所有與100值匹配的元素。

//clear 清除所有元素
L.clear();?????     //移除容器的所有數(shù)據(jù)

6 list 數(shù)據(jù)存?。╢ront、back、不支持[ ]和at的方式)（迭代器找位置）

• 不支持[ ]和at的方式。因為list鏈表存儲方式不是連續(xù)的，它的迭代器不支持隨機訪問，是雙向迭代器，只能前移后移，無法跳躍式訪問（不支持 it = it + 1）。

//不支持[ ]和at的方式
L.front()? ? ? ?    //返回第一個元素。 
L.back()? ? ? ?     //返回最后一個元素。
      
//只支持it++、it-- ，不支持 it = it + 1;  
//雙向迭代器，不可以跳躍訪問，即使是+1
list::iterator it = L.begin();
int a = *it; //返回迭代器所在的位置

//數(shù)據(jù)存取
void test01()
{listL1;
    L1.push_back(10);
    L1.push_back(20);
    L1.push_back(30);
    L1.push_back(40);
 
 
    //cout<< L1.at(0)<< endl;//錯誤 不支持at訪問數(shù)據(jù)
    //cout<< L1[0]<< endl; //錯誤  不支持[]方式訪問數(shù)據(jù)
     //不支持隨機訪問迭代器
    cout<< "第一個元素為： "<< L1.front()<< endl;
    cout<< "最后一個元素為： "<< L1.back()<< endl;
 
    //list容器的迭代器是雙向迭代器，不支持隨機訪問
    list::iterator it = L1.begin();
    it++;//只能++，--
    //it = it + 1;//錯誤，不可以跳躍訪問，即使是+1
}
 
int main() {test01();
 
    system("pause");
 
    return 0;
}

7 list 反轉(zhuǎn)和排序（L.reverse()(反轉(zhuǎn))、L.sort()（排序，鏈表內(nèi)部提供））

L.reverse(); ????//反轉(zhuǎn)鏈表
L.sort(); ????   //鏈表排序//默認(rèn)排序規(guī)則從小到大

• 注意：所有不支持隨機訪問迭代器的容器，不可以用標(biāo)準(zhǔn)算法（自帶的全局函數(shù)）

void printList(const list& L) {for (list::const_iterator it = L.begin(); it != L.end(); it++) {cout<< *it<< " ";
    }
    cout<< endl;
}
 //回調(diào)函數(shù)
bool myCompare(int val1, int val2)
{//降序，就讓第一個數(shù)大于第二個數(shù)
    return val1 >val2;
}
 
//list容器反轉(zhuǎn)和排序
//反轉(zhuǎn)                                
void test01()
{listL;
    L.push_back(90);
    L.push_back(30);
    L.push_back(20);
    L.push_back(70);
    cout<< "反轉(zhuǎn)前： "<< endl;
    printList(L);
 
    //反轉(zhuǎn)容器的元素
    L.reverse();
    cout<< "反轉(zhuǎn)后： "<< endl;
    printList(L);
 
}
//排序                                  
void test02()
{listL;
    L.push_back(90);
    L.push_back(30);
    L.push_back(20);
    L.push_back(70);
    cout<< "排序前： "<< endl;
    printList(L);
 
    //所有不支持隨機訪問迭代器的容器，不可以用標(biāo)準(zhǔn)算法
    //不支持隨機訪問迭代器的容器，內(nèi)部會提供對應(yīng)一些算法
 
    L.sort();//默認(rèn)排序規(guī)則從小到大
    cout<< "排序后："<< endl;
    printList(L);
 
    L.sort(myCompare);  //寫一個回調(diào)函數(shù)，從大到小
    printList(L);
 
}
int main() {test01();
    test02();
 
    system("pause");
 
    return 0;
}

8、C++ STL 中l(wèi)ist是雙向循環(huán)鏈表，雙向可以理解，有兩個指針域，指向前一結(jié)點和指向后一結(jié)點，雙向可以實現(xiàn)從末尾結(jié)點到頭結(jié)點的遍歷，但循環(huán)實現(xiàn)什么功能？

#include#includeint main()
{listli;
    for (int i = 0; i< 5; ++i)
    {li.push_back(i);
    }
    list::iterator it = li.end();
    cout<< *(--it); //輸出4
    cout<< *(++it); //若為循環(huán)鏈表，不是應(yīng)該回到頭結(jié)點嗎？實際輸出錯誤！
    //若為循環(huán)鏈表，那end()是指向哪里？
    return 0;
}

• 一個node結(jié)構(gòu)自己是不知道自己是list中的第幾個(沒有儲存相應(yīng)的信息)。但是，最末一個node，它的后指針是指向鏈表的終結(jié)記號，然后終結(jié)記號的node也有一個指針，才指向list的第一個node。所以，++it指向的是終結(jié)記號，上面是沒有數(shù)據(jù)的，當(dāng)然輸出錯誤。

• 雙向的意思是：你可以在首端加入新的數(shù)據(jù)node，也可以在末端加入新的數(shù)據(jù)node，但不表示你可以無限循環(huán)的遍歷它。另外，List模板，不建議你使用iterator(迭代器)，因為每一個node都不知道自己是第幾個node，如果你使用迭代器指定你要訪問第n個node的數(shù)據(jù)，它總是從首元素開始一個個數(shù)到第n，然后才返回數(shù)據(jù)給你。最好把鏈表當(dāng)作動態(tài)的雙端數(shù)組（deque）來使用，只訪問或者增刪頭端或者尾端的數(shù)據(jù)，這樣速度快

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

本文題目：【C++】stack/queue/list-創(chuàng)新互聯(lián)
URL標(biāo)題：http://jinyejixie.com/article8/peeop.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供ChatGPT、虛擬主機、網(wǎng)站維護、網(wǎng)站排名、動態(tài)網(wǎng)站、商城網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)