C++ Stack

2025 年 8 月 29 日 | 阅读 9 分钟

在 C++ 中，栈是一种线性数据结构，它遵循“后进先出”（LIFO）的原则进行操作。这意味着最后添加的元素最先被移除，而最先添加的元素最后被移除。在 C++ 中，STL 提供了一个栈容器适配器，可以高效地执行 LIFO 操作。它包含所有标准功能，如 push、pop、size、top、empty 等。

栈中的元素不能通过索引访问。由于元素是从顶部添加和移除的，我们只能访问栈顶的元素。

语法

它具有以下语法：

在这个语法中，

T：参数指定了容器适配器将要持有的元素的类型。
Container： 参数指定了用于存储栈元素的内部容器对象。

C++ 栈示例

让我们通过一个例子来说明 C++ STL 中的栈。

示例

#include <iostream>     
#include <stack>        //using the stack container from STL

using namespace std;    // Using standard namespace

int main() {            // Main function
    stack<int> st;      // Declare a integer stack

    // Push elements into the stack (LIFO order)
    st.push(15);  
    st.push(20);
    st.push(25);

    // Display the top element of the stack
    cout << "Top element of the list: " << st.top() << endl; 

    // Pop the top element from the stack
    st.pop();

    // Display the new top element
    cout << "After pop, top element: " << st.top() << endl;

    // Display the size of the stack
    cout << "Size of Stack: " << st.size() << endl;

    // Check if the stack is empty
    cout << "Is stack empty? " << (st.empty() ? "Yes" : "No") << endl;

    return 0;
}

编译并运行

输出

Top element of the list: 25
After pop, top element: 20
Size of Stack: 2
Is stack empty? No

说明

在此示例中，我们演示了 STL 栈容器的基本操作。我们将三个整数压入栈中，并使用 top() 访问最后插入的元素 (25)，然后使用 pop() 将其移除。之后，程序显示更新后的栈顶元素，检查栈的大小，并验证栈是否为空。

C++ 栈的基本操作

以下是可以对栈执行的基本操作：

插入元素

在 C++ 栈中，我们可以使用 push() 方法轻松地将新元素插入到栈顶。不可能将元素插入到栈中的其他位置。

语法

它具有以下语法：

C++ 插入元素示例

让我们通过一个例子来说明如何在 C++ 栈中插入元素。

示例

#include <iostream>
#include <stack>

using namespace std;   //using standard namespace
int main() {    //main function
    std::stack<std::string> myStack;
    myStack.push("Apple");
    myStack.push("Banana");
    myStack.push("Cherry");
    while (!myStack.empty()) {
        std::cout << myStack.top() << " ";
        myStack.pop();
    }
    return 0;
}

编译并运行

输出

Cherry Banana Apple

说明

在此示例中，我们初始化一个字符串栈，并添加“Apple”、“Banana”和“Cherry”。之后，它打印并弹出栈顶的每个元素，直到栈为空。输出将是 Cherry Banana Apple，这展示了栈的后进先出特性。

访问元素

在 C++ 栈中，我们只能使用 top() 方法访问栈顶元素。我们无法访问栈中的任何中间元素。

语法

它具有以下语法：

C++ 访问元素示例

让我们通过一个例子来说明如何在 C++ 栈中访问元素。

示例

#include <iostream>
#include <stack>

using namespace std;   //using standard namespace
int main() {    //Main Function
    stack<int> myStack;
    myStack.push(10);
    myStack.push(20);
    myStack.push(30);
    cout << "Top element: " << myStack.top() <<endl;  
    return 0;
}

编译并运行

输出

Top element: 30

说明

在此示例中，我们包含所有必需的头文件，并声明一个名为 myStack 的栈来存储整数。值 10、20 和 30 按此顺序压入栈中。由于栈是 LIFO（后进先出），压入的最高元素将是 30。调用 top() 函数以检索此顶部元素而不将其移除，并将其打印到控制台，显示为 Top element: 30。

删除元素

在一次操作中，只能使用 pop() 方法移除栈的最后一个元素。如果要移除任何其他元素，则需要先移除在该元素之后添加的所有元素。

语法

它具有以下语法：

C++ 删除元素示例

让我们通过一个例子来演示如何在 C++ 栈中删除元素。

示例

#include <iostream>
#include <stack>

using namespace std;  //using standard namespace
int main() {    //main function
    stack<int> myStack;
    myStack.push(100);
    myStack.push(200);
    myStack.push(300);
    cout << "Top Element Before Deletion: " << myStack.top() <<endl;
    myStack.pop(); 
    cout << "Top Element After Deletion: " << myStack.top() <<endl;
    return 0;
}

编译并运行

输出

Top Element Before Deletion: 300
Top Element After Deletion: 200

说明

在此示例中，我们将 100、200 和 300 放入栈中。之后，它使用 pop() 弹出（移除）栈顶元素 300，并打印新的栈顶元素 200。

伪遍历

由于栈中除了栈顶元素之外的任何元素都无法访问，因此无法对其进行遍历。但是，我们可以对其进行复制，访问栈顶元素并移除它。通过这样做直到复制的栈变空，我们可以有效地遍历而不改变原始栈。

语法

它具有以下语法：

stack<int> temp = st;
while (!temp.empty()) {
    cout << temp.top() << " ";
    temp.pop();
}

C++ 伪遍历示例

让我们通过一个例子来说明 C++ 栈中的伪遍历。

示例

#include <iostream>
#include <stack>

using namespace std;   //using standard namespace
int main() {   //main function
    stack<int> st;
    st.push(35);
    st.push(19);
    st.push(46);
    st.push(23);
    stack<int> temp(st);
    while(!temp.empty()) {
        cout << temp.top() << " ";
        temp.pop();
    }
    return 0;
}

编译并运行

输出

23 46 19 35

说明

在此示例中，我们声明一个栈并将四个整数压入栈中。之后，它将 st 复制到 temp 以保持原始栈不变。最后，它使用 while 循环弹出并打印 temp 中的每个栈顶元素，得到输出：23 46 19 35，这是栈从顶到底的内容。

检查栈是否为空

在 C++ 栈中，我们使用 empty() 方法来测试栈是否为空。empty() 方法返回

1（true）- 如果栈为空
0（false）- 当栈不为空时

语法

它具有以下语法：

检查 C++ 栈是否为空的示例

让我们通过一个例子来说明如何在 C++ 栈中检查栈是否为空。

示例

#include <iostream>
#include <stack>

using namespace std;   //using standard namespace
int main() {   //main function
    stack<int> st;
    if (st.empty()) {
        cout << "Stack is empty." << endl;
    } else {
        cout << "Stack is not empty." << endl;
    }
    st.push(10);  
    if (st.empty()) {
        cout << "Stack is empty." << endl;
    } else {
        cout << "Stack is not empty." << endl;
    }
    return 0;
}

编译并运行

输出

Stack is empty.
Stack is not empty.

说明

在此示例中，我们初始化一个空栈并通过 empty() 检查它是否为空，并打印一条消息。之后，它将 10 压入栈中，并再次检查。开始时，它打印“Stack is empty。”，压入后，它打印“Stack is not empty.”。

示例：一个简单的程序，展示基本栈函数的使用

让我们通过另一个例子来说明 C++ 栈中的基本栈函数。

示例

#include <iostream>  
#include <stack>  
using namespace std;   //using standard  namespace
void newstack(stack <int> ss)  
{  
    stack <int> sg = ss;  
    while (!sg.empty())  
    {  
        cout << '\t' << sg.top();  
        sg.pop();  
    }  
    cout << '\n';  
}  
int main ()    //main function
{  
    stack <int> newst;  
    newst.push(55);  
    newst.push(44);  
    newst.push(33);  
    newst.push(22);  
    newst.push(11);  
  
    cout << "The stack newst is : ";  
    newstack(newst);  
    cout << "\n newst.size() : " << newst.size();  
    cout << "\n newst.top() : " << newst.top();  
    cout << "\n newst.pop() : ";  
    newst.pop();  
    newstack(newst);   
    return 0;  
}  

编译并运行

输出

The stack newst is : 11 22 33 44 55
newst.size() : 5
newst.top() : 11
newst.pop() : 22 33 44 55

说明

在此示例中，我们创建一个 newstack() 函数来显示栈而不改变原始栈。在 main() 函数中，它将五个整数插入到 newest 中，打印其内容、大小和栈顶元素，然后弹出栈顶元素并打印新的栈。输出显示栈从底部到顶部：11 22 33 44 55，弹出后：22 33 44 55。

时间复杂度

下表列出了栈操作的时间复杂度

操作	时间复杂度
插入元素 (push)	O(1)
删除元素 (pop)	O(1)
访问栈顶元素 (peek)	O(1)
遍历栈	O(n)

成员类型

下面是栈成员类型及其简要描述的列表。

成员类型	描述
value_type	指定元素类型。
container_type	指定底层容器类型。
size_type	它指定元素的大小范围。

函数

借助函数，可以在编程领域中操作对象或变量。栈提供了大量可以嵌入到程序中的函数。以下是其中一个列表

函数	描述
(构造函数)	该函数用于构造栈容器。
empty	该函数用于测试栈是否为空。如果栈为空，则函数返回 true，否则返回 false。
大小	该函数返回栈容器的大小，这是存储在栈中的元素数量的度量。
top	该函数用于访问栈顶元素。该元素起着非常重要的作用，因为所有插入和删除操作都在栈顶元素上执行。
push	该函数用于在栈顶插入新元素。
pop	该函数用于删除元素，栈中的元素从顶部删除。
emplace	该函数用于在当前栈顶元素上方插入新元素。
swap	该函数用于交换引用中两个容器的内容。
关系运算符	非成员函数指定了栈所需的关系运算符。
uses allocator<stack>	顾名思义，非成员函数为栈使用分配器。

结论

总之，C++ 栈是一种基于后进先出 (LIFO) 原则工作的多功能数据结构。通过使用 std::stack 容器适配器，元素只能在顶部添加或移除。

Push()、pop()、top()、empty() 和 size() 是基本栈操作。尽管未提供直接遍历，但通过复制进行伪遍历可用于显示元素。栈在递归算法、表达式求值和回溯问题中非常有用，因为它们提供了受控访问。

C++ 栈选择题

1) 栈的底层原理是什么？

先进先出 (FIFO)
先进后出 (FILO)
后进先出 (LIFO)
随机访问

答案： c) LIFO (Last In First Out)

2) 以下哪个函数用于将元素添加到栈顶？

insert()
push()
add()
top()

答案： b) push()

3) top() 函数在栈中会返回什么？

底部元素
所有元素
中间元素
栈顶元素

答案： d) Element at the top

4) 以下哪个函数移除栈顶元素？

remove()
delete()
pop()
extract()

答案： c) pop()

5) empty() 函数做什么？

检查栈是否为空
检查栈是否已满
删除所有元素
返回栈顶元素

答案： a) Checks if the stack is empty

下一主题C++ Set

C++ Stack

语法

C++ 栈示例

示例

C++ 栈的基本操作

插入元素

示例

访问元素

示例

删除元素

示例

伪遍历

示例

检查栈是否为空

示例

示例：一个简单的程序，展示基本栈函数的使用

示例

成员类型

函数

结论

C++ 栈选择题

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ Stack

语法

C++ 栈示例

示例

C++ 栈的基本操作

插入元素

示例

访问元素

示例

删除元素

示例

伪遍历

示例

检查栈是否为空

示例

示例：一个简单的程序，展示基本栈函数的使用

示例

成员类型

函数

结论

C++ 栈选择题

相关帖子