用双端队列实现双端栈的底层实现，附有例子~-阿里云开发者社区

用双端队列实现双端栈的底层实现，附有例子~

2023-06-15 72

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 用双端队列实现双端栈的底层实现，附有例子~

#include<iostream>
#include <deque>
using namespace std;
enum stackNumber
{
  one, two
};
template<typename T>
class dualStack
{
public:
  dualStack();
  void push(const T & item, stackNumber n );
  void pop(stackNumber n);
  const T & top(stackNumber n) const;
  bool empty(stackNumber n) const;
  int size(stackNumber n) const;
private:
  deque<T> dualStackElements;
  int count1, count2;
};
template<typename T>
dualStack<T>::dualStack(){ count1 = 0; count2 = 0; dualStackElements.push_front(NULL); }
template<typename T>
void dualStack<T>::push(const T & item, stackNumber n)
{
  if (n == one)
  {
    dualStackElements.push_front(item);
    count1++;
  }
  if (n == two)
  {
    dualStackElements.push_back(item);
    count2++;
  }
}
template<typename T>
void dualStack<T>::pop(stackNumber n)
{
  if (n == one)
  {
    if (count1 == 0)
    {
      cout << "栈已空\n";
      return;
    }
    dualStackElements.pop_front();
    count1--;
  }
  if (n == two)
  {
    if (count2 == 0)
    {
      cout << "栈已空\n";
      return;
    }
    dualStackElements.pop_back();
    count2--;
  }
}
template<typename T>
const T & dualStack<T>::top(stackNumber n) const
{
  const T temp = NULL;
  if (n == one)
  {
    if (this->empty(one))
    {
      cout << "栈已空";
      return temp;
    }
    return dualStackElements.front();
  }
  if (n == two)
  {
    if (this->empty(two))
    {
      cout << "栈已空";
      return temp;
    }
  return dualStackElements.back();
  }
}
template<typename T>
bool dualStack<T>::empty(stackNumber n) const
{
  if (n == one)
    return dualStackElements.front()==NULL;
  if (n == two)
    return dualStackElements.back()==NULL;
}
template<typename T>
int dualStack<T>::size(stackNumber n) const
{
  if (n == one)
    return count1;
  if (n == two)
    return count2;
}

//以下测试main

#include"dualstk.h"
#include<ctime>
#include<stdlib.h>
using namespace std;
int main()
{
    dualStack<int> stk;
    int i = 1;
    int num;
    srand(unsigned int(time(0)));
    cout << "随机产生的从0~99的数字20个：" << endl;
    for (; i <= 20; i++)
    {
        num = rand() % 100;
        cout << num << " ";
        if (num % 2)
        {
            stk.push(num, one);
            continue;
        }
        stk.push(num, two);
    }
    cout << endl;
    system("pause");
    while (!stk.empty(one))
    {
        cout << stk.top(one) << " ";
        stk.pop(one);
    }
    cout << endl;
    while (!stk.empty(two))
    {
        cout << stk.top(two) << " ";
        stk.pop(two);
    }
    cout << endl;
    cout << stk.top(one);
    cout << endl;
    system("pause");
    return 0;
}

</pre><pre name="code" class="cpp">//其实都很简单，并没有使用双端队列的队列的性质，从两端看成两个栈，进行的操作。

//初始化时，push了NULL作为empty的标志。

</pre><pre name="code" class="cpp">//缺点：在top函数中，由于返回类型必须是const T & ,必须有返回值，而NULL的返回值对于Int就是0，肯定会被输出，甚为讨厌，原本想返回new T()，但是返回值类型对不//上，请大家指教如何消灭这个0，或者如何返回垃圾值！

</pre><pre name="code" class="cpp">

//以下是实现的另一个版本，差别就在构造是并不添加NULL，是否empty仅用count1,count2是否为0作为判断，不知道

//仅仅修改了构造函数以及top函数

#include<iostream>
#include <deque>
using namespace std;
enum stackNumber
{
<span style="white-space:pre">  </span>one, two
};
template<typename T>
class dualStack
{
public:
<span style="white-space:pre">  </span>dualStack();
<span style="white-space:pre">  </span>void push(const T & item, stackNumber n );
<span style="white-space:pre">  </span>void pop(stackNumber n);
<span style="white-space:pre">  </span>const T & top(stackNumber n) const;
<span style="white-space:pre">  </span>bool empty(stackNumber n) const;
<span style="white-space:pre">  </span>int size(stackNumber n) const;
private:
<span style="white-space:pre">  </span>deque<T> dualStackElements;
<span style="white-space:pre">  </span>int count1, count2;
};
template<typename T>
dualStack<T>::dualStack(){ count1 = 0; count2 = 0;  }
template<typename T>
void dualStack<T>::push(const T & item, stackNumber n)
{
<span style="white-space:pre">  </span>if (n == one)
<span style="white-space:pre">  </span>{
<span style="white-space:pre">    </span>dualStackElements.push_front(item);
<span style="white-space:pre">    </span>count1++;
<span style="white-space:pre">  </span>}
<span style="white-space:pre">  </span>if (n == two)
<span style="white-space:pre">  </span>{
<span style="white-space:pre">    </span>dualStackElements.push_back(item);
<span style="white-space:pre">    </span>count2++;
<span style="white-space:pre">  </span>}
}
template<typename T>
void dualStack<T>::pop(stackNumber n)
{
<span style="white-space:pre">  </span>if (n == one)
<span style="white-space:pre">  </span>{
<span style="white-space:pre">    </span>if (count1 == 0)
<span style="white-space:pre">    </span>{
<span style="white-space:pre">      </span>cout << "栈已空\n";
<span style="white-space:pre">      </span>return;
<span style="white-space:pre">    </span>}
<span style="white-space:pre">    </span>dualStackElements.pop_front();
<span style="white-space:pre">    </span>count1--;
<span style="white-space:pre">  </span>}
<span style="white-space:pre">  </span>if (n == two)
<span style="white-space:pre">  </span>{
<span style="white-space:pre">    </span>if (count2 == 0)
<span style="white-space:pre">    </span>{
<span style="white-space:pre">      </span>cout << "栈已空\n";
<span style="white-space:pre">      </span>return;
<span style="white-space:pre">    </span>}
<span style="white-space:pre">    </span>dualStackElements.pop_back();
<span style="white-space:pre">    </span>count2--;
<span style="white-space:pre">  </span>}
}
template<typename T>
const T & dualStack<T>::top(stackNumber n) const
{
<span style="white-space:pre">  </span>const T temp = NULL;
<span style="white-space:pre">  </span>if (n == one)
<span style="white-space:pre">  </span>{
<span style="white-space:pre">    </span>if (this->empty(one))
<span style="white-space:pre">    </span>{
<span style="white-space:pre">      </span>cout << "栈已空";
<span style="white-space:pre">      </span>return temp;
<span style="white-space:pre">    </span>}
<span style="white-space:pre">    </span>return dualStackElements.front();
<span style="white-space:pre">  </span>}
<span style="white-space:pre">  </span>if (n == two)
<span style="white-space:pre">  </span>{
<span style="white-space:pre">    </span>if (this->empty(two))
<span style="white-space:pre">    </span>{
<span style="white-space:pre">      </span>cout << "栈已空";
<span style="white-space:pre">      </span>return temp;
<span style="white-space:pre">    </span>}
<span style="white-space:pre">  </span>return dualStackElements.back();
<span style="white-space:pre">    </span>
<span style="white-space:pre">  </span>}
}
template<typename T>
bool dualStack<T>::empty(stackNumber n) const
{
<span style="white-space:pre">  </span>if (n == one)
<span style="white-space:pre">    </span>return count1==0;
<span style="white-space:pre">  </span>if (n == two)
<span style="white-space:pre">    </span>return count2==0;
}
template<typename T>
int dualStack<T>::size(stackNumber n) const
{
<span style="white-space:pre">  </span>if (n == one)
<span style="white-space:pre">    </span>return count1;
<span style="white-space:pre">  </span>if (n == two)
<span style="white-space:pre">    </span>return count2;
}<span style="font-family:Arial, Helvetica, sans-serif;"><span style="white-space: normal;">
</span></span>

用双端队列实现双端栈的底层实现，附有例子~

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

用双端队列实现双端栈的底层实现，附有例子~

热门文章

最新文章

相关课程

相关电子书