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

隐藏技能之双端队列

时间：2022-10-30 17:34:22浏览次数：39  
标签：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......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99