C++实现双栈模拟队列 |21xrx.com

C++实现双栈模拟队列

2023-07-13 17:35:00 深夜i -- --

C++ 双栈模拟队列

双栈模拟队列是一种常见的数据结构。通过两个栈的相互协作，可以实现队列的基本操作，如入队、出队、队列大小、队列是否为空等操作。本文将介绍如何使用C++语言来实现双栈模拟队列。

首先，我们需要定义两个栈，用于实现队列的基本操作。其中一个栈用于存储元素，另一个栈用于辅助操作。我们可以定义两个栈的类，其中包括对栈的基本操作，如入栈、出栈、栈顶元素等。具体的实现如下：


template<typename T>
class Stack {
public:
  void push(T x) {
    _data.push_back(x);
  }
  void pop() {
    _data.pop_back();
  }
  T top() {
    return _data.back();
  }
  bool empty() {
    return _data.empty();
  }
  int size() {
    return _data.size();
  }
private:
  vector<T> _data;
};

接下来，我们需要定义一个Queue类，用于实现队列的基本操作。在这个Queue类中，我们定义了两个Stack类的成员变量，一个用于存储元素，一个用于辅助操作。具体的实现如下：


template<typename T>
class Queue {
public:
  void push(T x) {
    _in_stack.push(x);
  }
  void pop() {
    if (empty())
      throw "Queue is empty!";
    
    if (_out_stack.empty()) {
      while (!_in_stack.empty()) {
        _out_stack.push(_in_stack.top());
        _in_stack.pop();
      }
    }
    _out_stack.pop();
  }
  int size() {
    return _in_stack.size() + _out_stack.size();
  }
  bool empty() {
    return size() == 0;
  }
private:
  Stack<T> _in_stack;
  Stack<T> _out_stack;
};

在以上代码中，push操作将元素添加到_in_stack中，而pop操作则将元素从_out_stack中弹出。如果_out_stack为空，则从_in_stack中取出元素，并逐个添加到_out_stack中。如此反复，直到_out_stack的栈顶元素为要弹出的元素。

总结来说，双栈模拟队列实现起来并不难，只需要注意两个栈的使用方法即可。通过这种数据结构，我们能够很方便地实现队列的基本操作，为实际应用提供便利。

上一篇: idea打包java可执行jar包

下一篇: 计算机二级C++考试之常见考点解析

评论区

()

相似文章