首页 > 其他分享 >隐藏技能之双端队列

隐藏技能之双端队列

时间:2022-10-30 17:34:22浏览次数:40  
标签:return 队列 双端 back elem MaxSize front array 技能

//双端队列,两边
using namespace std;
typedef char ElemType;
#include <time.h>
#include <stdlib.h>
#include <iostream> 
#define MaxSize 30
class DequeType{
    public:
          int front;
          int back;
          int size;
          ElemType array[MaxSize];
    public:/*构造函数,初始化成员变量*/
        DequeType (){
              front=back=size=0;
          }
          bool isEmpty(){//判断是否为空 
              if(0==size){
                  return true;
             }else {
                  return false;
             }
          }
          bool isFull(){//判断是否满 
             if(MaxSize==size){
                 return true;
            }else{
                 return false;
            }
          }
          bool push_back(ElemType elem){//从后端插入 
             if(isFull()){
                  return false;
                  }
              array[back]=elem;
              back=(back+1)%MaxSize;//循环 
              size++;
              return true;
          }
          bool pop_front(ElemType& elem){//从前端输出 
              if(isEmpty()){
                  return false;
            } 
              elem=array[front];
              front=(front+1)%MaxSize;
              size--;
              return true;
          }
          bool push_front(ElemType elem){//从前端输入 
             if(isFull()){
                 return false;
            } 
              front=(front-1+MaxSize)%MaxSize;//循环队列 
              array[front]=elem;
              size++;
              return true;
          }

          bool pop_back(ElemType& elem){//从后端输出 
              if(isEmpty()){
                  return false;
            } 
              back=(back-1+MaxSize)%MaxSize;
              elem=array[back];
              size--;
              return true;
          }
          
          bool get_front(ElemType & elem){//从前端取数 
              if(isEmpty()){
                  return false; 
              } 
              elem=array[front];
              return true;
          }
          bool get_back(ElemType& elem){//从后端取数 
              if(isEmpty()){
                  return false; 
            } 
             elem=array[(back-1+MaxSize)%MaxSize];
              return true;
          }

          int length(){//求队列长度 
              return size;
          }
          void traverse(){//全部输出 
            if(isEmpty()){
                cout<<"is empty"<<endl;
                return ;
            }
            int temp=front;
            while(temp!=back){
                cout<<array[temp]<<" ";
                temp=(temp+1)%MaxSize;
            }
            cout<<endl<<"traverse is over!"<<endl;
          }
};
int main(){
    DequeType queue;
    srand(time(0));//取随即数字 
    ElemType elem;
    int flag;
    for(int i=0;i<10;i++){
//        elem=rand()%26+'a';
//        flag=rand()%2;
        cin>>elem>>flag;
        //若flag非0,则push elem从前端
        //若flag==0,则push elem 从后端 
        if(flag){
            queue.push_front(elem);
            cout<<"push "<<elem<<" from front"<<endl;
        }else {
            queue.push_back(elem);
            cout<<"push "<<elem<<" from back"<<endl;
        }
    }
         cout<<"--------traverse start---------"<<endl;
          queue.traverse();
        cout << "Hello world!" << endl;
    return 0;
}

//三)双端队列基本操作:
// (3.1)init:初始化
// front=back=size=0;
// (3.2)push_back:尾进
// (先赋值,然后++)array[back]=elem;back=(back+1)%MaxSize;
// ( 注:初始化back=0.所以back第一次填数刚好填的是array[0] )
//
// (3.3)push_front:头进
// (先--,再赋值)front=(front-1+MaxSize)%MaxSize; array[front]=elem;
// (注: 初始化front=0,所以front第一次填数刚好填的是array[MaxSize-1] )
//
// (3.4)pop_back:尾出
// (先--,再赋值)back=(back-1+MaxSize)%MaxSize;elem=array[back];
//
// (3.5)pop_front:头出
// (先赋值,再++) elem=array[front];front=(front+1)%MaxSize;
//
// (3.6)get_front:取头(与pop_front类似,只不过front不变化)
// elem=array[front];
//
// (3.7)get_back:取尾 (与pop_back类似,只不过back不变化)
// elem=array[(back-1+MaxSize)%MaxSize];
//
//
// (3.8)length:长度
// return size或者(back-front+MaxSize)%MaxSize;
//
// (3.9)isEmpty:判空
// size==0或者front==back;
//
// (3.10)isFull:判满
// size==MaxSize或者(back+1)%MaxSize==front;
//
// (3.11)traverse:从头到尾遍历:
// while(front!=back){
// cout<<array[front]<<endl;
// front=(front+1)%MaxSize;
// }

然后我就拿着这个去做了hdu的1702

然后,一天过去了,写出来了下面这个,一只wa,还没找出原因,先贴在这儿改日再战

 

//双端队列,两边#include <iostream>
using namespace std;
typedef int ElemType;
#include <time.h>
#include <stdlib.h>
#include <iostream> 
#define MaxSize 30
class DequeType{
    public:
          int front;
          int back;
          int size;
          ElemType array[MaxSize];
    public:/*构造函数,初始化成员变量*/
        DequeType (){
              front=back=size=0;
          }
          bool isEmpty(){//判断是否为空 
              if(0==size){
                  return true;
             }else {
                  return false;
             }
          }
          bool isFull(){//判断是否满 
             if(MaxSize==size){
                 return true;
            }else{
                 return false;
            }
          }
          bool pop_front(ElemType& elem){//从前端删除 
              if(isEmpty()){
                  return false;
            } 
              elem=array[front];
              front=(front+1)%MaxSize;
              size--;
              return true;
          }
          bool push_front(ElemType elem){//从前端输入 
             if(isFull()){
                 return false;
            } 
              front=(front-1+MaxSize)%MaxSize;//循环队列 
              array[front]=elem;
              size++;
              return true;
          }

          bool pop_back(ElemType& elem){//从后端删除 
              if(isEmpty()){
                  return false;
            } 
              back=(back-1+MaxSize)%MaxSize;
              elem=array[back];
              size--;
              return true;
          }
          
          bool get_front(ElemType & elem){//从前端取数 
              if(isEmpty()){
                  return false; 
              } 
              elem=array[front];
              return true;
          }
          bool get_back(ElemType& elem){//从后端取数 
              if(isEmpty()){
                  return false; 
            } 
             elem=array[(back-1+MaxSize)%MaxSize];
              return true;
          }

          int length(){//求队列长度 
              return size;
          }
};
int main(){
    DequeType queue;
    ElemType elem;
    int ca,n,e;
    char s[10],m[5];
    cin>>ca;
    int flag=10;
    while(ca--){
        cin>>n;
        flag=10;
        for(int i=1;i<=4;i++){
            cin>>s[i];
        }
        if(s[3]=='L'){
            flag=1;//先进后出,即头进头出 
        }
        else if(s[3]=='F'){
            flag=0;//先进先出,即头进尾出 
        }
        for(int i=0;i<n;i++){
            scanf("%s",&m);
            if(m[0]=='I'){
                cin>>elem; 
                queue.push_front(elem);
            }else{
                if(flag){
                    if(queue.get_front(e)){
                        cout<<e<<endl;
                    }else{
                        cout<<"None"<<endl;
                    }    
                    queue.pop_front(e);
                }else{
                    if(queue.get_back(e)){
                        cout<<e<<endl;
                    }else{
                        cout<<"None"<<endl;
                    }
                    queue.pop_back(e);
                }
            }               
        }
    }
    return 0;
}

转变思路,决定用队列跟栈一起搞

 

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<stack>
using namespace std;
int main(){
    int n,m,k;
     char s[5],ss[5]; 
    cin>>n;
    while(n--){
           cin>>m;
        cin>>s;
        if(s[2]=='F'){//队列
              queue<int>mm;
            for(int i=0;i<m;i++){
                   cin>>ss;
                if(ss[0]=='I'){
                    cin>>k;
                    mm.push(k);
                }else{
                      if(mm.empty()){
                          cout<<"None"<<endl;
                    }else{
                           cout<<mm.front()<<endl;
                        mm.pop();
                    }
                }
              }
        }else{//栈
          stack<int>mmm;
              for(int i=0;i<m;i++){
                cin>>ss;
                if(ss[0]=='I'){
                    cin>>k;
                    mmm.push(k);
                }else{
                      if(mmm.empty()){
                          cout<<"None"<<endl;
                    }else{
                         cout<<mmm.top()<<endl;
                          mmm.pop();
                    }
                }
              }
        }
    }
  return 0;
}

 

标签:return,队列,双端,back,elem,MaxSize,front,array,技能
From: https://www.cnblogs.com/killjoyskr/p/16841746.html

相关文章

  • MQ 消息队列
    1、MQMQ(MessageQueue)消息队列,FIFO数据结构。角色:生产者:产生数据(消息)并放入队列。存储信息:即消息的队列。消费者:两种获取信息的方式拉:到指定队列拉取消息。......
  • Go 容器之队列的几种实现方式
    1队列的概念队列是有序集合,遵循FIFO(Firstinfirstout,即先进先出)排队方法的容器。添加操作发生在队列的尾部,移除操作则发生在头部。新元素从尾部进入队列,然后一直向前移......
  • 数据结构之环形队列
    概述队列是一种具有先进先出(FIFO)的数据类型,可以使用多种数据结构来实现队列:数组和链表。简单队列的应用场景比较有限,于是那些牛人们就发明一些复杂的队列:环形队列双端队列优......
  • 使用数据结构中的队列解决舞伴搭配问题
    ​ (一)问题描述某班有m个女生,n个男生(m不等于n,男女生人数和不能小于20),现要举办一个舞会,男女生分别编号坐在舞池两边的椅子上等待。每曲开始时,依次从男生和女生中各出一......
  • 数据结构 栈 / 队列(第9天)
    20.有效的括号判断输入的括号是否有效。左右括号··能闭合,顺序合适。思路:用栈实现。遇到左括号就保存在栈中,遇到右括号则需要从栈中弹出一个括号,与之配对。classSolutio......
  • Git新技能-stash操作
    最近开发的工期非常紧迫,一直在忙各种杂七杂八的事情,负责人都还没有创建好测试环境,所以代码也不能部署。可是项目经理催促开发进度又催得很急,新的开发需求必须在指定的......
  • 【BZOJ4504】K个串(优先队列,可持久化线段树)
    Description兔子们在玩k个串的游戏。首先,它们拿出了一个长度为n的数字序列,选出其中的一个连续子串,然后统计其子串中所有数字之和(注意这里重复出现的数字只被统计一次)。......
  • Java-五种线程池,四种拒绝策略,三类阻塞队列
    Java-五种线程池,四种拒绝策略,三类阻塞队列(常用)三类阻塞队列:   //1有界队列   workQueue=newArrayBlockingQueue<>(5);//基于数组的先进先出(FIFO)队列,支持公......
  • java-并发集合-阻塞队列 LinkedBlockingQueue 演示
    java-并发集合-阻塞队列LinkedBlockingQueue演示packageme.grass.demo.concuronte;importjava.util.Date;importjava.util.concurrent.CountDow......
  • java-并发集合-并发队列 ConcurrentLinkedQueue 演示
    java-并发集合-并发队列ConcurrentLinkedQueue演示目标:模拟5个线程同时并发读取“并发队列”,并使用CountDownLatch类协助计算消费耗时。pack......