前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >数据结构之队列建议收藏

数据结构之队列建议收藏

作者头像
全栈程序员站长
发布2022-07-14 20:02:35
1740
发布2022-07-14 20:02:35
举报

大家好,又见面了,我是全栈君

队列(Queue),是一种线性存储结构。它有以下几个特点: (01) 队列中数据是按照”先进先出(FIFO, First-In-First-Out)”方式进出队列的。 (02) 队列只允许在”队首”进行删除操作,而在”队尾”进行插入操作。

一 C++标准库queue

(1)成员函数

成员函数

说明

时间复杂度

size()

返回队列大小

O(1)

push()

在末尾加入一个元素

O(1)

pop()

删除第一个元素

O(1)

front()

返回第一个元素

O(1)

end()

返回最后一个元素

O(1)

empty

队列为空返回真

O(1)

(2)示例

代码语言:javascript
复制
#include <iostream>
#include <queue>
using namespace std;

/**
 * C++ : STL中的队列(queue)的演示程序。
 *
 * @author skywang
 * @date 2013/11/07
 */
int main ()
{
    int tmp=0;
    queue<int> iqueue;

    // 将10, 20, 30 依次加入队列的末尾
    iqueue.push(10);
    iqueue.push(20);
    iqueue.push(30);

    // 删除队列开头的元素
    iqueue.pop();

    // 将“队列开头的元素”赋值给tmp,不删除该元素.
    tmp = iqueue.front();
    cout<<"tmp="<<tmp<<endl;

    // 将40加入到队列的末尾
    iqueue.push(40);

    cout << "empty()=" << iqueue.empty() <<endl;
    cout << "size()=" << iqueue.size() <<endl;
    while (!iqueue.empty()) 
    {
        tmp = iqueue.front();
        cout<<tmp<<endl;
        iqueue.pop();  
    }

    return 0;
}

二 C++实现队列

代码语言:javascript
复制
#ifndef ARRAY_QUEUE_HXX
#define ARRAY_QUEUE_HXX

#include <iostream>
using namespace std;

template<class T> class ArrayQueue{
    public:
        ArrayQueue();
        ~ArrayQueue();

        void add(T t);
        T front();
        T pop();
        int size();
        int is_empty();

    private:
        T *arr;
        int count;
};

// 创建“队列”,默认大小是12
template<class T>
ArrayQueue<T>::ArrayQueue() 
{
    arr = new T[12];
    if (!arr) 
    {
        cout<<"arr malloc error!"<<endl;
    }
}

// 销毁“队列”
template<class T>
ArrayQueue<T>::~ArrayQueue() 
{
    if (arr) 
    {
        delete[] arr;
        arr = NULL;
    }
}

// 将val添加到队列的末尾
template<class T>
void ArrayQueue<T>::add(T t) 
{
    arr[count++] = t;
}


// 返回“队列开头元素”
template<class T>
T ArrayQueue<T>::front() 
{
    return arr[0];
}

// 返回并删除“队列末尾的元素”
template<class T>
T ArrayQueue<T>::pop() 
{
    int i = 0;;
    T ret = arr[0];

    count--;
    while (i++<count)
        arr[i-1] = arr[i];

    return ret;
}

// 返回“队列”的大小
template<class T>
int ArrayQueue<T>::size() 
{
    return count;
}

// 返回“队列”是否为空
template<class T>
int ArrayQueue<T>::is_empty()
{
    return count==0;
}

#endif

发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/120155.html原文链接:https://javaforall.cn

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2021年12月,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一 C++标准库queue
    • (1)成员函数
      • (2)示例
      • 二 C++实现队列
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档