对应视频：23考研408数据结构代码题参考模板（栈和队列C++STL）

栈和队列（C++STL）

栈

定义一个栈类型的变量

可以认为C++它已经为我们写好了一个名字为stack的结构体，但是这个结构体有一点特殊，不像我们平常自己写的直接 结构体名 变量名; 这样定义，我们需要在结构体名后面加一个尖括号，尖括号里面要写这个栈中要存放的元素的类型。

stack<int> st; //定义一个存放int类型元素的栈 
1

这里的类型可以根据自己的需要，需要在栈中存放什么类型就写什么类型，这有点类似于定义数组的时候前面写的类型。如果我要在栈中存放float类型，尖括号里就写float；如果是要存放char类型，尖括号里就写char。

元素入栈

元素入栈使用的是push()函数，参数为需要入栈的元素，但是这个函数又有点特殊，我们可以把它当做是写在结构体里的，所以我们可以把它当做结构体里的一个成员，采用类似于访问成员变量的方法去调用它。

st.push(1); //将元素1入栈 
st.push(2); //将元素2入栈 
1
2

获取栈顶元素

获取栈顶元素使用的是top()函数，该函数会将栈顶元素返回，同样我们需要使用类似与访问成员变量的方法去调用它。

int top_value=st.top();//获取栈顶元素
1

元素出栈

使用pop()函数，该函数会将栈顶元素出栈，不会将栈顶元素返回，可能与有些同学习惯的出栈的时候返回出栈元素有点不同（java中就是元素出栈的时候返回出栈元素），所以获取栈顶元素并将其弹出栈需要写两句代码。

st.pop();//栈顶元素出栈 
1

获取栈顶元素并将其出栈

int top_value=st.top();//获取栈顶元素; 
st.pop();//栈顶元素出栈 
1
2

获取栈中元素个数

使用size()函数

int len=st.size();//获取栈中元素个数 
1

判断栈是否为空

使用empty()函数，栈为空时返回true，非空是返回false

st.empty();
1

代码示例

int main(){
	
	stack<int> st; //定义一个存放int类型元素的栈 

	st.push(1); //将元素1入栈 
	st.push(2); //将元素2入栈 
	
	int len=st.size();//获取栈中元素个数 
	cout<<"栈中元素个数："<<len<<endl; //两个元素 
	
	int top_value=st.top();//获取栈顶元素; 
	st.pop();//栈顶元素出栈 
	cout<<"栈顶元素："<<top_value<<endl; //栈顶元素2 
	
	len=st.size();//获取栈中元素个数 
	cout<<"栈中元素个数："<<len<<endl; //一个元素 
	
	cout<<"栈是否为空："<<st.empty()<<endl; //非空 
	
	st.pop();
	
	cout<<"栈是否为空："<<st.empty()<<endl;  //空 

	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

输出

栈中元素个数：2
栈顶元素：2
栈中元素个数：1
栈是否为空：0
栈是否为空：1
1
2
3
4
5

队列

队列的用法基本与栈相同。

定义一个队列类型的变量

队列对应的结构体为queue，同栈一样需要在尖括号中指明队列中需要存放的元素类型。

queue<int> q; //定义一个存放int类型元素的队列 
1

元素入队

同样，队列中也使用的也是push()函数，并且push函数也在结构体中。

q.push(1); //将元素1入队 
q.push(2); //将元素2入堆
1
2

获取队头元素

队列里获取队头元素用的是front()，注意和栈那里区分

int front_value=q.front();//获取队头元素; 
1

元素出队

q.pop();//队头元素出队
1

同栈一样，出队时不会返回出队的元素

所以要获取队头元素并将其出队要写两句话

int front_value=q.front();//获取队头元素; 
q.pop();//队头元素出队 
1
2

获取队列中元素个数

int len=q.size();//获取栈中元素个数 
1

判断队列是否为空

q.empty();//队列为空时返回true，非空是返回false
1

代码示例

int main(){
	
	queue<int> q; //定义一个存放int类型元素的队列 

	q.push(1); //将元素1入队 
	q.push(2); //将元素2入队 
	
	
	int len=q.size();//获取队列中元素个数 
	cout<<"队列中元素个数："<<len<<endl; //两个元素 
	
	int front_value=q.front();//获取队头元素; 
	q.pop();//队头元素出队 
	cout<<"队头元素："<<front_value<<endl; //队头元素1 
	
	len=q.size();//获取队列中元素个数 
	cout<<"队列中元素个数："<<len<<endl; //一个元素 
	
	cout<<"队列是否为空："<<q.empty()<<endl; //非空 
	
	q.pop();
	
	cout<<"队列是否为空："<<q.empty()<<endl;  //空 

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

输出

队列中元素个数：2
队头元素：1
队列中元素个数：1
队列是否为空：0
队列是否为空：1
1
2
3
4
5