目錄

前言

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é)尾?

本篇文章我們學習了棧和隊列，圖片為純手繪無參考，制作不易，還請各位大佬三連支持一下！