【C++】stack/queue/list-創(chuàng)新互聯(lián)
文章目錄
一、stack（棧）（先進(jìn)后出、【頭部插入、刪除】、不許遍歷） 1 基本概念（棧是自頂向下(top在下)，堆是向上）
- 注意事項(xiàng)
- 1 emplace 與 push 的區(qū)別
- 一、stack（棧）（先進(jìn)后出、【頭部插入、刪除】、不許遍歷）
- 1 基本概念（棧是自頂向下(top在下)，堆是向上）
- 2 stack 常用接口（構(gòu)造函數(shù)、賦值操作、數(shù)據(jù)存儲(chǔ)、empty、size）
- 二、queue （隊(duì)列）（先進(jìn)先出、【頭部刪除、尾部插入】、不許遍歷）
- 1 queue 基本概念[kju:]
- 2 queue 常用接口（構(gòu)造函數(shù)、賦值操作、數(shù)據(jù)存儲(chǔ)、empty、size）
- 3 priority_queue
- 3.1 用pair＜int,int＞建立優(yōu)先隊(duì)列（小根堆）
- 三、list（最常用）（雙向迭代器、單向鏈表/雙向循環(huán)鏈表、可以遍歷）
- 1 list基本概念（插入刪除效率高，隨機(jī)存儲(chǔ)不行）
- 2 list構(gòu)造函數(shù)（默認(rèn)構(gòu)造、區(qū)間拷貝、n個(gè)元素拷貝、拷貝）
- 3 list 賦值和交換（operator=、assign、swap）
- 4 list 大小操作 (size、emply、resize) (無容量capacity)
- 5 list 插入和刪除 (insert、erase、remove（移除指定數(shù)據(jù)）、clear)（迭代器找位置）
- 6 list 數(shù)據(jù)存?。╢ront、back、不支持[ ]和at的方式)（迭代器找位置）
- 7 list 反轉(zhuǎn)和排序（L.reverse()(反轉(zhuǎn))、L.sort()（排序，鏈表內(nèi)部提供））
注意：
- 所有不支持隨機(jī)訪問迭代器的容器，不可以用標(biāo)準(zhǔn)算法（自帶的全局函數(shù)）（
eg. sort()） - stack 和 queue(priority_queue) 不支持 clear() 函數(shù)
while (!que.empty()) // 有clear()功能
{que.pop();
}1.直接傳入對(duì)象（int, double 或者 構(gòu)造好了的對(duì)象）
//假設(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.在傳入時(shí)候構(gòu)造對(duì)象
S.push(data(1,2));
S.emplce(data(1,2));3.emplace可以直接傳入構(gòu)造對(duì)象需要的元素，然后自己調(diào)用其構(gòu)造函數(shù)！
S.emplace(1,2)意思是，emplace這樣接受新對(duì)象的時(shí)候，自己會(huì)調(diào)用其構(gòu)造函數(shù)生成對(duì)象然后放在容器內(nèi)（比如這里傳入了1，2，它則會(huì)自動(dòng)調(diào)用一次data(1,2))，而push，只能讓其構(gòu)造函數(shù)構(gòu)造好了對(duì)象之后，再使用拷貝構(gòu)造函數(shù)！相當(dāng)于emplace直接把原料拿進(jìn)家，造了一個(gè)。而push是造好了之后，再復(fù)制到自己家里，多了復(fù)制這一步。所以emplace相對(duì)于push，使用第三種方法會(huì)更節(jié)省內(nèi)存。
注意：
emplace_back(type) 對(duì)應(yīng) push_back(type)
emplace(i, type) 對(duì)應(yīng)于 insert(type, i)
emplace_front(type) 對(duì)應(yīng)于 push_front()一、stack（棧）（先進(jìn)后出、【頭部插入、刪除】、不許遍歷） 1 基本概念（棧是自頂向下(top在下)，堆是向上）
- stack是一種先進(jìn)后出(First In Last Out,FILO)的數(shù)據(jù)結(jié)構(gòu)，它只有一個(gè)出口（棧容器）
- 棧中只有頂端向下的元素才可以被外界使用，因此棧不允許有遍歷行為
棧中進(jìn)入數(shù)據(jù)稱為 ——入棧 s.push（）
棧中彈出數(shù)據(jù)稱為 ——出棧 s.pop（）
//構(gòu)造函數(shù)
stacks;? ? ? //stack采用類模板實(shí)現(xiàn)， stack對(duì)象的默認(rèn)構(gòu)造形式
stacks1(s); ?//拷貝構(gòu)造函數(shù)
//賦值操作
s=s1;? ? //重載等號(hào)操作符
//數(shù)據(jù)存取
s.push(40);? ? ?//向棧頂添加元素
s.pop();? ? ? ? //從棧頂移除第一個(gè)元素
s.top() ? ? //返回棧頂元素值
//大小操作
s.empty() ? ? ? //判斷堆棧是否為空
s.size()? ? ? ? //返回棧的大?。ㄔ貍€(gè)數(shù)） #include//棧容器常用接口
void test01()
{//特點(diǎn)：符合先進(jìn)后出數(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是一種先進(jìn)先出(First In First Out,FIFO)的數(shù)據(jù)結(jié)構(gòu)，它有兩個(gè)出口（隊(duì)列容器）
- 隊(duì)列容器允許從隊(duì)尾新增元素，從另隊(duì)頭移除元素
- 隊(duì)列中只有隊(duì)頭和隊(duì)尾才可以被外界使用，因此隊(duì)列不允許有遍歷行為
隊(duì)列中進(jìn)數(shù)據(jù)稱為 — 入隊(duì) q.push（）
隊(duì)列中出數(shù)據(jù)稱為 — 出隊(duì) q.pop（）
//構(gòu)造函數(shù)
queueq; ? ? //queue采用類模板實(shí)現(xiàn)，queue對(duì)象的默認(rèn)構(gòu)造形式
queueq1（q）; //拷貝構(gòu)造函數(shù)
//賦值操作
q=q1; ? ? ? //重載等號(hào)操作符
//數(shù)據(jù)存取
q.push(p1); ? ? ? ? //往隊(duì)尾添加元素
q.pop(); ? ? ? ? //從隊(duì)頭移除第一個(gè)元素
q.back(); ? ? ? //返回最后一個(gè)元素值
q.front() ? ? ? //返回第一個(gè)元素值
//大小操作
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;
};
//隊(duì)列 Queue
void test01() {//創(chuàng)建隊(duì)列
queueq;
//準(zhǔn)備數(shù)據(jù)
Person p1("唐僧", 30);
Person p2("孫悟空", 1000);
Person p3("豬八戒", 900);
Person p4("沙僧", 800);
//向隊(duì)列中添加元素 入隊(duì)操作
q.push(p1);
q.push(p2);
q.push(p3);
q.push(p4);
//隊(duì)列不提供迭代器，更不支持隨機(jī)訪問
while (!q.empty()) {//輸出隊(duì)頭元素
cout<< "隊(duì)頭元素-- 姓名： "<< q.front().m_Name
<< " 年齡： "<< q.front().m_Age<< endl;
cout<< "隊(duì)尾元素-- 姓名： "<< q.back().m_Name
<< " 年齡： "<< q.back().m_Age<< endl;
cout<< endl;
//彈出隊(duì)頭元素
q.pop();
}
cout<< "隊(duì)列大小為："<< q.size()<< endl;
}
int main() {test01();
system("pause");
return 0;
} - 比較對(duì)象是pair的第一個(gè)元素
priority_queue,vector>,greater>>pq; - 取元素
1.pq.top().first;
2.pq.top().second;- 鏈表（list）：是一種物理存儲(chǔ)單元上非連續(xù)的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接實(shí)現(xiàn)的（指針域）
- STL中的鏈表是一個(gè)雙向循環(huán)鏈表，由于鏈表的存儲(chǔ)方式并不是連續(xù)的內(nèi)存空間，因此鏈表list中的迭代器只支持前移和后移，屬于雙向迭代器，只支持it++、it-- ，不支持 it = it + 1（不能跳躍式的訪問）
（1）鏈表的組成：鏈表由一系列結(jié)點(diǎn)組成
（2）結(jié)點(diǎn)的組成：一個(gè)是存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)域，一個(gè)是存儲(chǔ)下一個(gè)結(jié)點(diǎn)地址的指針域
（3）list的優(yōu)點(diǎn)：
- 采用動(dòng)態(tài)存儲(chǔ)分配，不會(huì)造成內(nèi)存浪費(fèi)和溢出
- 鏈表執(zhí)行插入和刪除操作十分方便，修改指針即可，不需要移動(dòng)大量元素
（4）list的缺點(diǎn)：
- 容器遍歷速度沒有數(shù)組快
- 鏈表靈活，但是空間(指針域) 和 時(shí)間（遍歷）額外耗費(fèi)較大
（5）List有一個(gè)重要的性質(zhì)：
- 插入操作和刪除操作都不會(huì)造成原有l(wèi)ist迭代器的失效，這在vector是不成立的（vector會(huì)從新找一塊更長的存儲(chǔ)空間，原有迭代器失效）
總結(jié)：STL中List和vector是兩個(gè)最常被使用的容器，各有優(yōu)缺點(diǎn)
- 兩個(gè)指針，next指針指向下一個(gè)節(jié)點(diǎn)，prev指針指向上一個(gè)節(jié)點(diǎn)（雙向）
- 最后一個(gè)節(jié)點(diǎn)記錄第一個(gè)節(jié)點(diǎn)的位置，前一個(gè)節(jié)點(diǎn)記錄最后一個(gè)節(jié)點(diǎn)的位置（循環(huán)）
listL1;? ? ? ? //list采用類模板實(shí)現(xiàn)，對(duì)象的默認(rèn)構(gòu)造形式：
listL2(L1.begin(), L1.end());? //構(gòu)造函數(shù)將[beg, end)區(qū)間中的元素拷貝給本身。
listL4(5, 10); ? //構(gòu)造函數(shù)將5個(gè)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個(gè)elem
listL4(10, 1000);
printList(L4);
}
int main() {test01();
system("pause");
return 0;
} //assign 賦值函數(shù)
L3.assign(L2.begin(), L2.end()); //將[beg, end)區(qū)間中的數(shù)據(jù)拷貝賦值給本身。
L4.assign(10, 100);? ? //將n個(gè)elem拷貝賦值給本身。
//operator= 重載
L2 = L1;? ? ? ? //重載等號(hào)操作符
//swap 互換函數(shù)
L1.swap(L2);? ? ? ? //將L1與L2的元素互換。//(無容量capacity)
L1.size() //返回容器中元素的個(gè)數(shù)
L1.empty() //判斷容器是否為空
//resize 重新指定容器的長度（大小）
L1.resize(10); //10個(gè)0
//重新指定容器的長度為10，若容器變長，則以默認(rèn)值0填充新位置。
//如果容器變短，則末尾超出容器長度的元素被刪除。
L1.resize(10,1000); //10個(gè)1000
//重新指定容器的長度為10，若容器變長，則以1000值填充新位置。
//如果容器變短，則末尾超出容器長度的元素被刪除。- 最好把鏈表當(dāng)作動(dòng)態(tài)的雙端數(shù)組（deque）來使用，只訪問或者增刪頭端或者尾端的數(shù)據(jù)，這樣速度快
//it表示某個(gè)迭代器，n為整數(shù)。該函數(shù)的功能是將it迭代器前進(jìn)或后退n個(gè)位置。
//n為正數(shù)時(shí)表示將it右移（前進(jìn)）n個(gè)位置，n為負(fù)數(shù)時(shí)表示將it左移（后退）n個(gè)位置
#includeusing namespace std;
advance(it, n); // 要判斷 n 是否越界 （雙向循環(huán)鏈表也要防止越界）
Data.insert(it, tem2); //插入數(shù)據(jù)
Data.erase(it); //刪除數(shù)據(jù) //兩端插入、刪除操作
L.push_back(10);???? //在容器尾部加入一個(gè)元素
L.pop_back();??? //刪除容器中最后一個(gè)元素
L.push_front(100);?? //在容器開頭插入一個(gè)元素
L.pop_front();??? //從容器開頭移除第一個(gè)元素
//insert 指定位置插入
list::iterator it;
L.insert(it, 10);? //在迭代器位置插10元素，返回新數(shù)據(jù)的位置。
L.insert(it, 2, 10); //在迭代器位置插入2個(gè)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ù)，返回下一個(gè)數(shù)據(jù)的位置。
L.erase(it);? ? //刪除迭代器位置的數(shù)據(jù)，返回下一個(gè)數(shù)據(jù)的位置。
//remove 移除指定數(shù)據(jù)（特有）
L.remove(100);???? //刪除容器中所有與100值匹配的元素。
//clear 清除所有元素
L.clear();????? //移除容器的所有數(shù)據(jù) - 不支持[ ]和at的方式。因?yàn)閘ist鏈表存儲(chǔ)方式不是連續(xù)的，它的迭代器不支持隨機(jī)訪問，是雙向迭代器，只能前移后移，無法跳躍式訪問（不支持 it = it + 1）。
//不支持[ ]和at的方式
L.front()? ? ? ? //返回第一個(gè)元素。
L.back()? ? ? ? //返回最后一個(gè)元素。
//只支持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;//錯(cuò)誤 不支持at訪問數(shù)據(jù)
//cout<< L1[0]<< endl; //錯(cuò)誤 不支持[]方式訪問數(shù)據(jù)
//不支持隨機(jī)訪問迭代器
cout<< "第一個(gè)元素為： "<< L1.front()<< endl;
cout<< "最后一個(gè)元素為： "<< L1.back()<< endl;
//list容器的迭代器是雙向迭代器，不支持隨機(jī)訪問
list::iterator it = L1.begin();
it++;//只能++，--
//it = it + 1;//錯(cuò)誤，不可以跳躍訪問，即使是+1
}
int main() {test01();
system("pause");
return 0;
} L.reverse(); ????//反轉(zhuǎn)鏈表
L.sort(); ???? //鏈表排序//默認(rèn)排序規(guī)則從小到大- 注意：所有不支持隨機(jī)訪問迭代器的容器，不可以用標(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)
{//降序，就讓第一個(gè)數(shù)大于第二個(gè)數(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);
//所有不支持隨機(jī)訪問迭代器的容器，不可以用標(biāo)準(zhǔn)算法
//不支持隨機(jī)訪問迭代器的容器，內(nèi)部會(huì)提供對(duì)應(yīng)一些算法
L.sort();//默認(rèn)排序規(guī)則從小到大
cout<< "排序后："<< endl;
printList(L);
L.sort(myCompare); //寫一個(gè)回調(diào)函數(shù)，從大到小
printList(L);
}
int main() {test01();
test02();
system("pause");
return 0;
} 8、C++ STL 中l(wèi)ist是雙向循環(huán)鏈表，雙向可以理解，有兩個(gè)指針域，指向前一結(jié)點(diǎn)和指向后一結(jié)點(diǎn)，雙向可以實(shí)現(xiàn)從末尾結(jié)點(diǎn)到頭結(jié)點(diǎn)的遍歷，但循環(huán)實(shí)現(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é)點(diǎn)嗎？實(shí)際輸出錯(cuò)誤！
//若為循環(huán)鏈表，那end()是指向哪里？
return 0;
}
一個(gè)node結(jié)構(gòu)自己是不知道自己是list中的第幾個(gè)(沒有儲(chǔ)存相應(yīng)的信息)。但是，最末一個(gè)node，它的后指針是指向鏈表的終結(jié)記號(hào)，然后終結(jié)記號(hào)的node也有一個(gè)指針，才指向list的第一個(gè)node。所以，++it指向的是終結(jié)記號(hào)，上面是沒有數(shù)據(jù)的，當(dāng)然輸出錯(cuò)誤。
雙向的意思是：你可以在首端加入新的數(shù)據(jù)node，也可以在末端加入新的數(shù)據(jù)node，但不表示你可以無限循環(huán)的遍歷它。另外，List模板，不建議你使用iterator(迭代器)，因?yàn)槊恳粋€(gè)node都不知道自己是第幾個(gè)node，如果你使用迭代器指定你要訪問第n個(gè)node的數(shù)據(jù)，它總是從首元素開始一個(gè)個(gè)數(shù)到第n，然后才返回?cái)?shù)據(jù)給你。最好把鏈表當(dāng)作動(dòng)態(tài)的雙端數(shù)組（deque）來使用，只訪問或者增刪頭端或者尾端的數(shù)據(jù)，這樣速度快
你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧
本文題目：【C++】stack/queue/list-創(chuàng)新互聯(lián)
URL標(biāo)題：http://www.muchs.cn/article8/peeop.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供ChatGPT、虛擬主機(jī)、網(wǎng)站維護(hù)、網(wǎng)站排名、動(dòng)態(tài)網(wǎng)站、商城網(wǎng)站
聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)
猜你還喜歡下面的內(nèi)容
- JavaScript中如何實(shí)現(xiàn)調(diào)用Java方法-創(chuàng)新互聯(lián)
- CentOS7卸載Apachemariadbphp等方法-創(chuàng)新互聯(lián)
- php禁止用戶重復(fù)提交表單的方法-創(chuàng)新互聯(lián)
- C++·入門·04|引用-創(chuàng)新互聯(lián)
- Element表格嵌入復(fù)選框以及單選框的方法是什么-創(chuàng)新互聯(lián)
- JavaIO流常見面試題有哪些-創(chuàng)新互聯(lián)
- JS怎么實(shí)現(xiàn)簡單短信驗(yàn)證碼界面-創(chuàng)新互聯(lián)
- Google最新收錄規(guī)則，怎樣才能讓網(wǎng)站快速被Google收錄 2015-02-07
- 講述一下google和百度優(yōu)化之間的差異化 2016-01-23
- 成都谷歌推廣商告訴你利用 Google Play 政策來打造用戶信任的應(yīng)用 2016-04-09
- 大數(shù)據(jù)告訴你：Google排名高的是什么樣的頁面 ？ 2023-05-05
- 【SEO優(yōu)化公司】google網(wǎng)站SEO優(yōu)化入門技巧 2016-11-14
- 我們?nèi)绾胃行У氖褂胓oogle分析工具 2013-04-29
- Google Ads廣告中的無效點(diǎn)擊來源及解決策略 2015-04-24
- Google 計(jì)劃引入新的廣告過濾器，讓廣告客戶更好地控制廣告 2016-10-19
- 外貿(mào)企業(yè)為什么要做Google SEO（谷歌優(yōu)化）？ 2023-05-05
- 淺析：百度seo和google seo算法 2015-11-01
- google優(yōu)化排名怎么做？ 2016-09-26
- 如何在Google Chrome中停用混合內(nèi)容安全警告 2016-09-19