您的位置:

c++ Stack详解

一、c++ Stack类

Stack是一个后进先出(LIFO)的数据结构,c++ STL中的stack类也是基于此设计。c++ stack类可以存储同一数据类型的元素,其主要操作有入栈(push())和出栈(pop())。

#include <stack>
using namespace std;

int main() {
   stack<int> stack1; // 声明一个存储int类型的stack
   stack1.push(1); // 入栈
   stack1.push(2);
   stack1.push(3);
   cout << "栈顶元素: " << stack1.top() << endl; // 输出栈顶元素
   stack1.pop(); // 出栈
   cout << "栈大小: " << stack1.size() << endl;
   return 0;
}

运行结果:

栈顶元素: 3

栈大小: 2

二、c++ Stack实现

c++ stack类通常是通过deque(双端队列)来实现的,也可以使用vector、list等STL容器来实现。

template <class T, class Container = deque <T> >
class stack {
public:
   explicit stack(const Container& ctnr = Container()); // 构造函数
   bool empty() const; // 判断栈是否为空
   size_t size() const; // 返回栈的大小
   T& top(); // 返回栈顶元素的引用
   const T& top() const; // 返回栈顶元素的值
   void push(const T& val); // 入栈
   void pop(); // 出栈
   Container& get_container(); // 返回容器
};

三、c++ Stack函数

除了push()和pop()之外,c++ Stack类还提供了其他一些有用的函数,例如empty()、size()、top()等。

empty(): 判断栈是否为空

size(): 返回栈的大小

top(): 返回栈顶元素的引用

push(): 入栈

pop(): 出栈

四、c++ Stack计算器

我们可以使用c++ stack类实现一个简单的计算器。例如输入字符串"3 4 +",计算3+4的值。

#include <iostream>
#include <stack>
#include <string>
using namespace std;

int main() {
   stack<int> stack1;
   string str = "3 4 +";
   int len = str.length();
   for (int i = 0; i < len; i++) {
      if (str[i] == ' ') {
         continue;
      }
      else if (isdigit(str[i])) { // 数字入栈
         int num = 0;
         while (i < len && isdigit(str[i])) {
            num = num * 10 + (str[i] - '0');
            i++;
         }
         i--;
         stack1.push(num);
      }
      else { // 运算符出栈
         int tmp1 = stack1.top();
         stack1.pop();
         int tmp2 = stack1.top();
         stack1.pop();
         switch (str[i]) {
            case '+': stack1.push(tmp2 + tmp1); break;
            case '-': stack1.push(tmp2 - tmp1); break;
            case '*': stack1.push(tmp2 * tmp1); break;
            case '/': stack1.push(tmp2 / tmp1); break;
         }
      }
   }
   cout << stack1.top() << endl;
   return 0;
}

运行结果:

7

五、c++ Stack用法

c++ Stack类在实际开发中用途很广泛,例如可以用来解决括号匹配问题、中缀表达式转后缀表达式、逆波兰表达式求值等问题。

六、c++ Stack弹出

c++ Stack类中的pop()函数会将栈顶元素弹出,但并不返回其值,如果需要获取其值,可以使用top()函数先获取其值再弹出。

七、c++ Stack头文件

c++ stack类的头文件是<stack>

八、c++ Stack出错

由于c++ Stack类是基于STL容器实现的,所以在使用时需要注意容器的大小、类型等问题。如果将不同类型的元素存储在同一个stack中,可能会引起类型错误。

九、c++ Stack不是容器

需要注意的是,c++ Stack类不是STL容器,它只是基于STL容器实现的一种数据结构。

十、c++ Stack知识点选取

选取的c++ Stack知识点包括类的定义、实现方式、常用函数、实际用途、出错等问题。