C++ STL 中的 Stack（附示例）

什么是 std::stack？

Stack（栈）是一种基于 LIFO（后进先出）技术运行的数据结构。std::stack 允许元素只能从一端添加和移除。

std::stack 类是一个容器适配器。容器对象保存相似数据类型的元素。您可以从各种序列容器创建栈。如果不提供容器，则默认使用 deque 容器。容器适配器不支持迭代器，因此不能用于操作数据。

Stack 语法

要创建栈，我们必须在代码中包含 <stack> 头文件。然后我们使用此语法定义 std::stack。

template <class Type, class Container = deque<Type> > class stack;

Type – 是 std::stack 中包含的元素类型。可以是任何有效的 C++ 类型，甚至是用户定义的类型。
Container – 是底层容器对象的类型。

成员类型

以下是 stack 的成员类型：

value_type - 第一个模板参数 T。它表示元素类型。
container_type - 第二个模板参数 Container。它表示底层容器类型。
size_type - 无符号整型。

Stack 中的操作

C++ 的 stack 支持以下基本操作：

push – 将一个项添加到栈中。
pop – 从栈中移除一个项。
peek – 在不移除的情况下返回栈顶的项。
isFull – 检查栈是否已满。
isEmpty – 检查栈是否为空。

Stack 实现

步骤 1) 最初我们有一个空栈。空栈的栈顶设置为 -1。

步骤 2) 接下来，我们已将元素 5 推入栈中。栈顶将指向元素 5。

步骤 3) 接下来，我们已将元素 50 推入栈中。栈顶移动并指向元素 50。

步骤 4) 然后我们执行了 pop 操作，从栈中移除了栈顶元素。元素 50 已从栈中弹出。现在栈顶指向元素 5。

push() 和 pop()

stack::push() 函数将新项添加到栈顶。插入后栈的大小增加 1。该函数采用此语法：

stack.push(value)

value 是要插入到栈中的项。

stack::pop() 函数移除栈顶元素。这是栈中最新的项。移除后栈的大小减 1。以下是函数语法：

stack.pop()

该函数不接受任何参数。

示例 1

#include <iostream> 
#include <stack> 
using namespace std;
int main() {
	stack<int> st;
	st.push(10);
	st.push(20);
	st.push(30);
	st.push(40);
	
         st.pop();
	st.pop();

	while (!st.empty()) {
		cout << ' ' << st.top();
		st.pop();
	}
}

输出

这是代码的屏幕截图：

代码解释

包含 iostream 头文件到我们的代码中以使用其函数。
在代码中包含 stack 头文件以使用其函数。
包含 std 命名空间到我们的代码中以使用其类而无需调用其名称。
调用 main() 函数。程序逻辑应添加到此函数中。
创建一个栈 st 来存储整数值。
使用 push() 函数将值 10 插入到栈中。
使用 push() 函数将值 20 插入到栈中。
使用 push() 函数将值 30 插入到栈中。
使用 push() 函数将值 40 插入到栈中。
使用 pop() 函数从栈中移除栈顶元素，即 40。栈顶元素现在变为 30。
使用 pop() 函数从栈中移除栈顶元素，即 30。栈顶元素现在变为 20。
使用 while 循环和 empty() 函数检查栈是否不为空。! 是 NOT（非）运算符。
将栈的当前内容打印到控制台。
在栈上调用 pop() 函数。
while 循环体结束。
main() 函数主体的结尾。

empty(), size(), top()

Stack 具有内置函数，您可以使用它们来操作 stack 及其值。这些包括：

empty() – 检查 stack 是否为空。
size() – 返回 stack 的大小，即 stack 中的元素数量。
top() – 访问 stack 顶部的元素。

示例 2

#include <iostream> 
#include <stack>  
using namespace std;
void createStack(stack <int> mystack)
{
	stack <int> ms = mystack;
	while (!ms.empty())
	{
		cout << '\t' << ms.top();
		ms.pop();
	}
	cout << '\n';
}
int main()
{
	stack <int> st;
	st.push(32);
	st.push(21);
	st.push(39);
	st.push(89);
	st.push(25);

	cout << "The stack st is: ";
	createStack(st);
	cout << "\n st.size() : " << st.size();
	cout << "\n st.top() : " << st.top();
	cout << "\n st.pop() : ";
	st.pop();
	createStack(st);
	return 0;
}

输出

这是代码的屏幕截图：

代码解释

在代码中包含 iostream 头文件以使用其函数。
在代码中包含 stack 头文件以使用其函数。
在程序中包含 std 命名空间，以便在不调用它的情况下使用其类。
创建 createStack 函数，我们可以使用它来创建 mystack。该栈将保存一组整数。
createStack 函数体开始。
创建 mystack 数据类型的一个实例，并将其命名为 ms。
使用 while 循环和 empty() 函数检查栈是否为空。
while 循环体开始。
使用 top() 函数获取栈顶存储的元素。 \t 字符将创建一个新标签。
使用 pop() 函数删除栈顶的元素。
while 循环体结束。
在控制台上打印一个空行。
createStack 函数体结束。
调用 main() 函数。程序逻辑应添加到 main() 函数体中。
函数 main() 的主体开始。
创建一个 stack 对象 st。
使用 push() 函数将元素 32 插入到栈中。
使用 push() 函数将元素 21 插入到栈中。
使用 push() 函数将元素 39 插入到栈中。
使用 push() 函数将元素 89 插入到栈中。
使用 push() 函数将元素 25 插入到栈中。
在控制台打印一些文本。
调用 createStack 函数来执行上述栈的插入操作。
将栈的大小以及其他文本打印到控制台。
将栈顶的元素打印到控制台。
在控制台打印一些文本。
删除栈顶的元素。然后它将返回栈中剩余的元素。
调用 createStack 函数来执行上述操作。
程序在成功完成后应返回值。
main() 函数主体的结束。

emplace() 和 swap()

以下是其他内置的 stack 函数：

emplace() – 构造然后将新元素插入到栈顶。
swap() – 交换 stack 的内容与另一个 stack 的内容。

示例 3

#include <iostream>    
#include <stack>
#include <cstdlib>
using namespace std;
int main() {
	stack<int> st1;
	stack<int> st2;

	st1.emplace(12);
	st1.emplace(19);

	st2.emplace(20);
	st2.emplace(23);

	st1.swap(st2);

	cout << "st1 = ";
	while (!st1.empty()) {
		cout << st1.top() << " ";
		st1.pop();
	}

	cout << endl << "st2 = ";
	while (!st2.empty()) {
		cout << st2.top() << " ";
		st2.pop();
	}
}

输出

这是代码的屏幕截图：

代码解释

包含 iostream 头文件到我们的代码中以使用其函数。
在代码中包含 stack 头文件以使用其函数。
在代码中包含 cstdlib 头文件以使用其函数。
包含 std 命名空间到我们的代码中以使用其类而无需调用其名称。
调用 main() 函数。程序逻辑将添加到此函数的主体中。
声明一个名为 st1 的 stack 来存储整数值。
声明一个名为 st2 的 stack 来存储整数值。
使用 emplace() 函数将整数 12 插入到名为 st1 的栈中。
使用 emplace() 函数将整数 19 插入到名为 st1 的栈中。
使用 emplace() 函数将整数 20 插入到名为 st2 的栈中。
使用 emplace() 函数将整数 23 插入到名为 st2 的栈中。
使用 swap() 函数交换两个栈 st1 和 st2 的内容。栈 st1 的内容应移动到栈 st2。栈 st2 的内容应移动到栈 st1。
在控制台打印一些文本。
使用 while 语句和 empty() 函数检查栈 st1 是否不为空。
将栈 st1 的内容打印到控制台。打印到控制台时，" " 会在 stack 元素之间添加空格。
对栈 st1 执行 pop() 函数以移除栈顶元素。
while 语句体结束。
在控制台上打印一些文本。endl 是 C++ 中表示行结束的关键字。它将光标移到下一行，以便从那里开始打印。
使用 while 语句和 empty() 函数检查栈 st2 是否不为空。
将栈 st2 的内容打印到控制台。打印到控制台时，" " 会在 stack 元素之间添加空格。
对栈 st2 执行 pop() 函数以移除栈顶元素。
while 语句体结束。
main() 函数体结束。

STL 中的 Stack

STL（标准模板库）提供了提供常见 C++ 数据结构的模板类。因此，也可以在 STL 中实现 stack。我们只需将此库包含在代码中即可使用它来定义 stack。

stack<T> st;

上述语法声明了一个名为 st 的 stack，用于存储 T 类型的数据元素。

示例4

#include <iostream>      
#include <stack>
#include <cstdlib>
using namespace std;
int main() {
	stack<int> st;
	st.push(12);
	st.push(19);
	st.push(20);
	cout << st.top();   
	cout << st.size();  
}

输出

这是代码的屏幕截图：

代码解释

包含 iostream 头文件到我们的代码中以使用其函数。
在代码中包含 stack 头文件以使用其函数。
在代码中包含 cstdlib 头文件以使用其函数。
包含 std 命名空间到我们的代码中以使用其类而无需调用其名称。
调用 main() 函数。程序逻辑应添加到此函数的主体中。
声明一个名为 st 的 stack 来存储整数数据。
将元素 12 添加到栈中。
将元素 19 添加到栈中。
将元素 20 添加到栈中。
将栈顶的元素打印到控制台。
将栈的大小打印到控制台。
函数 main() 的主体结束。

摘要

Stack 是一种基于 LIFO（后进先出）技术运行的数据结构。
std::stack 只允许从一端添加和移除项。
std::stack 类是一个容器适配器，保存相似数据类型的项。
可以从各种序列容器创建 stack。
如果不提供容器，则默认使用 deque 容器。
push() 函数用于向 stack 中插入项。
pop() 函数用于从 stack 中移除栈顶项。
empty() 函数用于检查 stack 是否为空。

什么是 std::stack？

Stack 语法

成员类型

Stack 中的操作

Stack 实现

push() 和 pop()

示例 1

empty(), size(), top()

相关文章

示例 2

emplace() 和 swap()

示例 3

STL 中的 Stack

示例4

摘要

订阅新闻通讯