双端队列

首页新闻小组威客人才下载博客代码贴在线编程论坛

作者在 2008-10-28 17:08:38 发布以下内容

双端队列（JAVA）
双端队列就是一个两端都是结尾的队列。队列的每一瑞都可以插入数据项和移除数据项。这些方法可以叫作insertLeft()和insertRight()，以及removeLeft()和removeRight()。如果严格禁止调用insertLeft()和removeLeft()方法（或禁用右段的操作），双端队列功能就和栈一样。禁止调用insertLeft()和removeRight()（或相反的另一对方法），它的功能就和队列一样了。双端队列与栈或队列相比，是一种多用途的数据结构，在容器类库中有时会用双端队列来提供栈和队列两种功能。

数据结构 | 阅读 9605 次

文章评论，共1条

vfdff(作者)

2008-10-28 17:13

STL学习之——vector和deque 
http://blog.chinaunix.net/u1/51602/showart_1138909.html 
 
依据标准模板库（STL）-由惠普公司提供。 
基于ANSI/ISO标准C++，在windows平台（C++ Builder\Visual C++）和Unix平台（G++）测试通过。 
 
vector（向量）：是一个灵巧的数组，自动调整大小，并提供方法在任意位置插入和删除元素，而且向量是模板化的，将int类型元素插入int类型向量的方法和将string类型元素插入string类型向量的方法是完全相同的。有了向量之后可能再也不想用数组了。 
向量比数组使用起来方便的多，向量是一个有限序列（连续存储）特色如下： 
 
给出序列中任何项的下标，可以在常数时间内完成访问或修改该下标对应的项。 
在向量尾部插入元素平均只需要常数时间，其中worstTime(n)是O(n)，n代表序列中项的数量。 
对序列尾部进行的删除操作，worstTime(n)是常数。 
任意的插入和删除，worstTime(n)和averageTime(n)都是是O(n) 
实例： 
    vector<string>words; 
    string word; 
    for (int i = 0; i < 5; i++) 
    { 
        cin >> word; 
        words.push_back (word); 
    } // reading in words 
    words.erase (words.begin()); 
    words.pop_back(); 
    for (unsigned i = 0; i < words.size(); i++) 
        cout << words [i] << endl; 
 
deque（双端队列）：队列（double end queue双端队列）和向量很相似，但是实现细节上有较大的差别。 
双端队列是一个有限序列，特色如下： 
 
给出序列中任何项的下标，可以在常数时间内完成访问或修改该下标对应的项（与向量相同）。 
平均情况下，在序列头或尾部插入只耗费常数时间，但是worstTime(n)是O(n)，n代表序列中项的数量。（与向量不同，向量在头部插入代价比较大） 
对序列尾部进行的插入和删除操作，worstTime(n)是常数。 
任意的插入和删除，worstTime(n)和averageTime(n)都是是O(n) 
由此可见，双端队列对象可以在他自身的首尾快速的插入和删除，而向量对象只有在尾部才能快速的插入和删除。deque类比vector类多了两个方法： 
//在双端队列的开头插入一个x的拷贝，averageTime(n)是常数，worstTime(n)是O(n) 
void push_front(const T& x); 
//删除双端队列开头的项,worstTime(n)是常数 
void pop_front(); 
实例： 
    deque<string>words; 
    string word; 
    for (int i = 0; i < 5; i++) 
    { 
        cin >> word; 
        words.push_back (word); 
    } // for 
    words.pop_front( ); 
    words.pop_back( ); 
    for (unsigned i = 0; i < words.size(); i++) 
        cout << words [i] << endl; 
总结： 
除非大多数操作都位于或者接近容器的开头，否则向量是比双端队列快的。向量比数组功能强大的多。向量自动调整大小，当超出当前容量时候就创建一个双倍大小的数组，并把向量copy到这个大的数组里。更大的优势在于插入和删除。

赞回复

vfdff的博客

vfdff

浏览1970471次