在家做十字繡兼職網(wǎng)站今日國際新聞最新消息
目錄
前言
Everyday English
棧(Stack)
圖文解釋
實現(xiàn)添加刪除元素
實現(xiàn)查看清空棧
完整代碼
運行示例
棧的選擇題
隊列(Queue)
圖文解釋
隊列的基本用法
完整代碼?
運行結(jié)果?
隊列的好處?
結(jié)尾?
前言
今天我們將學習兩個新的數(shù)據(jù)結(jié)構(gòu)——棧和隊列。
Everyday English
A friend in need is a friend indeed.
患難見真情。
棧(Stack)
圖文解釋
棧最直白的想象就是羽毛球筒了(假設(shè)從一個口取)。
比如說我想按照紅-橙-黃的順序放進去,并取出橙色羽毛去,得進行以下操作:
1.放入紅-橙-黃色羽毛球。
2.取出頂部的黃色羽毛球。
3.取出頂部的橙色羽毛球。
下面請欣賞我的純手繪圖片:
現(xiàn)在請你把注意力放在黃色羽毛球上,它在放進筒時是最后一個放進去的,而被取出來時是第一個被取出來的;而紅色羽毛球卻是最后一個被取出來的。所以棧有一個很重要的性質(zhì):
先進后出,后進先出(LIFO:Last in first out)
實現(xiàn)添加刪除元素
添加:將元素入棧并使指針右移一位。
void add(int n)//添加元素至棧頂
{tmp++;a[tmp]=n;
}
?刪除:將元素出棧并使指針左移一位。
void pop()//刪除棧頂元素
{a[tmp]=0;//這一步可要可不要tmp--;
}
實現(xiàn)查看清空棧
查看:把數(shù)組從1-tmp輸出一下即可。
void look(int n[])
{for(int i=1;i<=tmp;i++){cout<<n[i]<<" ";}
}
清空:把數(shù)組歸零,并把指針賦值為1。?
void empty(int n[])
{for(int i=1;i<=tmp;i++){n[i]=0;}tmp=0;
}
完整代碼
#include<bits/stdc++.h>
using namespace std;
string op="";
int a[1005],tmp=0,n;
char b[1005],m;
void add(int n)//添加元素至棧頂
{tmp++;a[tmp]=n;
}
void pop()//刪除棧頂元素
{a[tmp]=0;//這一步可要可不要tmp--;
}
void look(int n[])
{cout<<"The stack is:"; for(int i=1;i<=tmp;i++){cout<<n[i]<<" ";}
}
void empty(int n[])
{for(int i=1;i<=tmp;i++){n[i]=0;}tmp=0;cout<<"The stack is empty now."<<endl;
}
int main()
{memset(a,0,sizeof(a));while(1){cin>>op;if(op[0]=='s') return 0;else {if(op[0]=='a') cin>>n,add(n);if(op[0]=='p') pop();if(op[0]=='l') look(a);if(op[0]=='e') empty(a);}}
}
運行示例
add 1
add 2
add 3
add 4
pop
pop
look
The stack is:1 2
add 5
empty
The stack is empty now.
add 6
look
The stack is:6
棧的選擇題
棧雖然編程中用的不是特別多,但是在CSP的第一輪考試中經(jīng)常出現(xiàn),我們來看一看。?
1.有6個元素,按照6、5、4、3、2、1的順序入棧S,請問下列哪個出棧順序是非法的?
A.5? 4? 3? 6? 1? 2
B.4? 5? 3? 1? 2? 6
C.3? 4? 6? 5? 2? 1
D.2? 3? 4? 1? 5? 6
題目來源:2022 CSP-J 選擇第二題
解析:因為6比5先入棧,所以出棧時6應該在5后面,故選C。當然你也可以模擬一下。
2.對于入棧順序為a,b,c,d,e的序列,下列( )不是合法的出棧序列。
A.a,b,c,d,e
B.e,d,c,b,a
C.b,a,c,d,e
D.c,d,a,e,b
題目來源:2021 CSP-J 選擇題第五題
解析:因為a比b先入棧,所以出棧時a應該在b后面,故選D。當然你也可以模擬一下。
A.進棧一個,出棧一個
B.全部進棧,全部出棧
C.a進棧,b進棧,b出棧,a出棧,剩下的進棧一個,出棧一個。
D.無法完成
3.下圖中所使用的數(shù)據(jù)結(jié)構(gòu)是?
A、棧
B、隊列
C、二叉樹
D、哈希表
棧的性質(zhì)是:后進先出,故選A。
隊列(Queue)
圖文解釋
隊列顧名思義就是排隊買票,先買票的人總是先出來,最后買票的人最后出來。
如上圖,1號游客最先排隊,所以他第一個買票也是第一個出來的,這就是隊列的重要性質(zhì):
先進先出,后進后出(FIFO:First?in first out)
隊列的基本用法
在C++中,已經(jīng)有為我們寫好的隊列了,我們只需直接使用即可。
首先需要定義一個隊列:
queue<變量類型> q;
這個變量類型可以是int,double,long long,struct......?
下面是隊列的幾個基本用法:
q.pop() //彈出隊首元素
q.push(item) //把元素item插入到隊尾
q.empty() //如果隊列為空返回True,否則返回False
q.full() //如果隊列已滿返回True,否則返回False
q.front() //調(diào)用隊首元素
q.size() //返回隊列中元素的數(shù)量
完整代碼?
#include<bits/stdc++.h>
using namespace std;
int main()
{queue<int> q;q.push(1);q.push(2);q.push(3);q.pop();cout<<q.front()<<endl;q.pop();cout<<q.size()<<endl;q.pop();if(q.empty()) cout<<"The queue is empty."<<endl;return 0;
}
運行結(jié)果?
2
1
The queue is empty.
隊列的好處?
等我們后面學到BFS時,會用到很多有關(guān)于隊列的知識。
結(jié)尾?
本篇文章我們學習了棧和隊列,圖片為純手繪無參考,制作不易,還請各位大佬三連支持一下!