精华内容
下载资源
问答
  • deque和stack容器

    2016-10-08 20:41:00
    deque和stack容器 一、deque容器 双端数组,可以在头部和尾部插入弹出元素 deque容器与上章节类似 在其基础上增加了push_back()、push_front()、pop_back()、pop_front()函数 push_back() //在容器尾部添加...

    deque和stack容器

     

    一、             deque容器

           双端数组,可以在头部尾部插入弹出元素

    deque容器与上章节类似

    在其基础上增加了push_back()、push_front()、pop_back()、pop_front()函数

    push_back()               //在容器尾部添加一个数据

    push_front()              //在容器头部插入一个数据

    pop_back()                 //删除容器最后一个数据

    pop_front()                //删除容器第一个数据

    代码走起

    使用stl提供的vector,引用头文件       #include "deque"

    代码示例

    #include <iostream>

    using namespace std;

    #include "deque"

    void DequeTest()

    {

    deque<int> d1;

    d1.push_back(1);              //在尾部插入数据 1

    d1.push_back(3);              //在尾部插入数据 3

    d1.push_back(5);              //在尾部插入数据 5

    d1.push_front(-11);          //在头部插入数据 -11

    d1.push_front(-33)           //在头部插入数据 -33

    d1.push_front(-55)           //在头部插入数据 -55

    cout << "头部元素:" << d1.front() << endl;                    //头部元素:-55

    cout << "尾部元素:" << d1.back() << endl;                    //尾部元素:5

    //①迭代输出deque

    for( deque<int>::iterator it = d1.begin() ; it != d1.end() ; it++ )

    {

             cout << *it << "       ";

    }

    d1.pop_front();                  //弹出(删除)头部元素

    d1.pop_back();                   //弹出(删除)尾部元素

    //②迭代输出deque

    for( deque<int>::iterator it = d1.begin() ; it != d1.end() ; it++ )

    {

             cout << *it << "       ";

    }

    }

    查找某个值在数组(deque)中的下标值

    接上面代码

    //查找3 在数组(deque)中的下标值

    deque<int>::iterator it = find( d1.begin() , d1.end() , 3);                   //返回迭代器的位置:it

    if ( it != d1.end() )

    {

             cout << "值3的下标是" << distance(d1.begin() , it ) << endl;                 // distance函数找到下标

    }

    else

    {

             cout << "没有找到" << endl;

    }

    注:需添加头文件 algorithm.h

    二、             stack

    简介

    stack是堆栈容器,是一种“先进后出”的容器

    stack是简单的装饰deque容器而成的另外一种容器

    引用头文件 <inlcude "stack>

    代码走起

    #include <iostream>

    using namespace std;

    #include "stack"

    void StackTest()

    {

    stack<int> s;

    //入栈 0 1 2 3 4 5 6 7 8 9

    for( int i = 0 ; i < 10 ; i++ )

    {

             s.push( i + 1);

    }

    cout << "栈的大小" << s.size() << endl;

    //出栈

    while ( !s.empty() )

    {

    int nTmp = s.Top();                 //获取栈顶元素

    cout << nTmp << "       ";               //输出值:10 9 8 7 6 5 4 3 2 1 0  先入后出

    s.pop();                  //弹出栈顶元素

    }

    }

     

    注:stack栈中可以放类、类指针等

    转载于:https://www.cnblogs.com/zzhua/p/5940061.html

    展开全文
  • Queue、Deque和Stack

    2017-07-24 19:34:11
    Deque stack2 = new ArrayDeque(); stack2.push("1"); stack2.push("2"); stack2.push("3"); while (stack2.peek() != null){  System.out.println(stack2.pop()); } **************************...

    Queue队列接口

    public interface Queue<E> extends Collection<E

    在尾部添加元素 (add, offer):

    add(e) 会在长度不够时抛出异常:IllegalStateException;  

    offer(e) 只返回false


    删除头部元素 (remove, poll),返回头部元素,并且从队列中删除

    remove() 会在没元素时抛出异常:NoSuchElementException;  

    poll() 返回null; 


    查看头部元素 (element, peek),返回头部元素,但不改变队列

    element()会在没元素时抛出异常:NoSuchElementException; 

    peek() 返回null;

    //代码实现队列
    //列用Queue实现队列(LinkedList)
    Queue queue = new LinkedList();
    queue.offer("1");
    queue.offer("2");
    queue.offer("3");
    while (queue.peek() != null){
        System.out.println(queue.poll());
    }
    //利用Queue实现队列(ArrayDeque)
    Queue queue2 = new ArrayDeque();
    queue2.offer("1");
    queue2.offer("2");
    queue2.offer("3");
    while (queue2.peek() != null){
        System.out.println(queue2.poll());
    }

    ************************************************************************************

    Deque双端队列接口

    Deque接口是Queue接口的子接口,它代表一个双端队列,该队列允许从两端来操作队列中的元素。Deque不仅可以当成双端队列使用,而且可以当成栈来使用。

    public interface Deque<E> extends Queue<E


    插入方法:

    addFirst(e)

    addLast(e)

    offerFirst(e)

    offerLast(e)

    删除方法:

    removeFirst()

    removeLast()

    pollFirst()

    pollLast()

    查看元素

    getFirst()

    getLast()

    peekFirst()

    peekLast()

    removeFirstOccurrence(e):删除第一个出现的指定元素

    removeLastOccurrence(e):删除最后出现的指定元素

    //利用Deque双端队列实现(LinkedList)
    Deque deque = new LinkedList();
    deque.offerLast("1");
    deque.offerLast("2");
    deque.offerLast("3");
    while (deque.peekFirst() != null){
        System.out.println(deque.pollFirst());
    }
    //利用Deque双端队列实现(ArrayDeque)
    Deque deque2 = new ArrayDeque();
    deque2.offerLast("1");
    deque2.offerLast("2");
    deque2.offerLast("3");
    while (deque2.peekFirst() != null){
        System.out.println(deque2.pollFirst());
    }

    ************************************************************************************

    Stack(通过Deque实现)

    push(e):push表示入栈,在头部添加元素,栈的空间可能是有限的,如果栈满了,push会抛出异常IllegalStateException。

    pop():pop表示出栈,返回头部元素,并且从栈中删除,如果栈为空,会抛出异常NoSuchElementException。

    peek():peek查看栈头部元素,不修改栈,如果栈为空,返回null。


    //利用Deque实现栈(LinkedList)
    Deque stack = new LinkedList();
    stack.push("1");
    stack.push("2");
    stack.push("3");
    while (stack.peek() != null){
        System.out.println(stack.pop());
    }
    //利用Deque实现栈(ArrayDeque)
    Deque stack2 = new ArrayDeque();
    stack2.push("1");
    stack2.push("2");
    stack2.push("3");
    while (stack2.peek() != null){
        System.out.println(stack2.pop());
    }

    ************************************************************************************

    展开全文
  • [STL]deque和stack、queue

    2014-01-09 21:39:00
    怎么说呢,deque是一种双向开口的连续线性空间,至少逻辑上看上去是这样。然而事实上却没有那么简单,准确来说deque其实是一种分段连续空间,因此其实现以及各种操作比vector复杂的多。 一.deque的中控器 deque...

          怎么说呢,deque是一种双向开口的连续线性空间,至少逻辑上看上去是这样。然而事实上却没有那么简单,准确来说deque其实是一种分段连续空间,因此其实现以及各种操作比vector复杂的多。

     

    一.deque的中控器

          deque是有一段一段的定量连续空间构成,采用一块所谓的map(当然不是map容器)作为主控。map是一小块连续空间,其中每一个元素都是一个指针,指向另一段连续性空间(缓冲区)。缓冲区才是deque的储存空间主体。我们可以指定缓冲区大小,默认值0表示使用512字节缓冲区。deque设计结构如下图所示:

     

    二.deque的数据结构

          deque除了维护map的指针外,也要维护startfinish两个迭代器,分别指向第一缓冲区的第一个元素和最后缓冲区的最后一个元素(的下一个位置)。此外,它还要记录当前map的大小,因为当map结点不够的时候,需要另外配置一个更大的map,计算其大小需要知道当前map的大小(源码为:new_map_size=map_size+max(map_size,nodes_to_add)+2;)。deque数据结构如下:

    class deque
    {
    public:
    	typedef T value_type;
    	typedef valude_type *pointer;
    	typedef size_f size_type;
    public: //迭代器
    	typedef __deque_iterator<T,T&,T*,BufSiz> iterator;
    protected: //元素的指针的指针
    	typedef pointer *map_pointer;
    protected: 
    	iterator start; 
    	iterator finish;
    	map_pointer map;
    	size_type map_size; //map中指针个数
    ...
    };
    

     

    三.deque的成员函数

          考虑到deque的特殊结构,所以实现deque的各种操作都相当琐碎复杂。最关键的就是判断是否已经处于缓冲区边缘,如果是,一旦前进或后退就必须跳跃至下一个或上一个缓冲区。还有一个重要问题就是当map前端或尾端备用空间不足时就要重新配置新map(配置更大的,拷贝原来的,释放原来的),下面的push_back()和push_front()等函数都需要先判断。下面分别解释deque的各个成员函数。

    • push_back():当最后缓冲区有两个(含)以上的空间,直接在缓冲区增加新元素;当最后缓冲区只剩一个备用空间时,push_back()调用push_back_aux(),先配置一个新的缓冲区,然后再在那个仅剩的备用空间定义新元素,并更改finish的状态,令其指向新结点。
    • push_front():当第一缓冲区有备用空间时,直接在备用空间增加新元素;当第一缓冲区无备用空间时,调用push_front_aux()配置新结点(缓冲区),增加新元素,并改变start状态。
    • pop_back():当最后缓冲区有一个(含)以上元素,就将finish向前移一位并将最后那个元素析构掉;当最后缓冲区没有任何元素,就调用push_pop_aux()将这个缓冲区释放。解释一下:第一种情况finish指向最后缓冲区的first位置,第二种情况finish指向最后第二个缓冲区的last位置。
    • pop_front():第一缓冲区有两个(含)以上元素,将第一个元素析构,将start后移;否则,将这个缓冲区释放,start指向下一个缓冲区第一个元素。
    • clear():deque的最初状态(即无任何元素时)保有一个缓冲区,因此clear()之后也一样要保留一个缓冲区,finish=start。
    • erase():先判断清除空间前后元素个数,移动较少一端
    • insert():若在最前端,即push_front(),最后端类似;判断插入点前后元素个数,移动较少的一端

     

    四.配接器stack和queue

          stack是一种先进后出(FILO)的数据结构,它只有一个出口。deque是双向开口的数据结构,所以SGI STL便以deque作为缺省情况下的stack底部结构,封闭其头端开口。stack没有迭代器,所以除了顶部元素,无法存取其它元素,即不能遍历stack。

          stack的成员函数都是针对其顶部元素进行操作:push(),pop(),top()。

          queue是一种先进先出(FIFO)的数据结构,它有两个出口。queue也是以deque作为底部结构,封闭其底端的出口和前端的入口。queue,只有顶端(两端)的元素能被外部使用,所以queue也没有迭代器,不提供遍历功能。

          queue的成员函数有:front(),back(),push(),pop()。

          可以看到stack和queue的成员函数以及特性都是针对其数据结构来的,所以深入理解其内部结构,不易与deque众多的成员函数混淆。当然stack和queue也可以list为底层结构实现。

     

    参考:《STL源码剖析》

    转载于:https://www.cnblogs.com/Rosanna/p/3512635.html

    展开全文
  • deque> #include<stack> #include"car.h" #include<QString> extern map<QString,int> mp; extern deque<car> park; extern deque<car> path; extern stack<car> ...
  • Java集合—Deque & Stack

    2020-11-18 17:06:26
    原文地址:Java中的Deque和Stack的内部原理区别 关于Deque 和 Stack,如果没有对API有很仔细的研究,单纯从使用上来说,很难仔细发现他们中间的区别,虽然他们有很大不同。而实际在Java Doc里是建议用Deque替代...

    原文作者:惊帆的BLOG

    原文地址:Java中的Deque和Stack的内部原理区别

    关于Deque 和 Stack,如果没有对API有很仔细的研究,单纯从使用上来说,很难仔细发现他们中间的区别,虽然他们有很大不同。而实际在Java Doc里是建议用Deque替代Stack接口完成栈的功能,我们仔细看下Java Doc里对Stack是这样描述的:

    A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class. For example:Deque<Integer> stack = new ArrayDeque<Integer>();

    而对Deque是这样描述的:

    Deques can also be used as LIFO (Last-In-First-Out) stacks. This interface should be used in preference to the legacy Stack class. When a deque is used as a stack, elements are pushed and popped from the beginning of the deque.

    也就是让我们不要再使用Stack接口去完成栈的功能,而是使用Deque,并且提供了相关例子。那么为什么会这样建议呢?首先,我们可以发现Deque是继承自Queue,而Stack是继承自Vector,这就比较奇怪了。Vector是由数组实现的集合类,他包含了大量集合处理的方法。而Stack之所以继承Vector,是为了复用Vector中的方法,来实现进栈(push)、出栈(pop)等操作。这里就是Stack设计不好的地方,既然只是为了实现栈,不用链表来单独实现,而是为了复用简单的方法而迫使它继承Vector,Stack和Vector本来是毫无关系的。这使得Stack在基于数组实现上效率受影响,另外因为继承Vector类,Stack可以复用Vector大量方法,这使得Stack在设计上不严谨,例如Vector中的:

    public void add(int index, E element) {
        insertElementAt(element, index);
    }

    可以在指定位置添加元素,这与Stack 的设计理念相冲突(栈只能在栈顶添加或删除元素)。所以Java后来修正了这个不良好的设计,提出了用Deque代替Stack的建议。

    Deuqe

    Java中的Deuqe,即“double ended queue”的缩写,是Java中的双端队列集合类型,它集成自Deque,完全具备普通队列FIFO的功能,同时它也具备了Stack的LIFO功能,并且保留了push和pop函数,所以使用起来应该是一点障碍都没有。Deque可以由ArrayDeuqe或者LinkedList实现,它们两者使用的区别以及优劣也就是数组和链表的区别。

    ArrayDeque

    ArrayDeque是Deque接口的一种具体实现,是依赖于可变数组来实现的。ArrayDeque 没有容量限制,可根据需求自动进行扩容。ArrayDeque可以作为栈来使用,效率要高于 Stack。ArrayDeque也可以作为队列来使用,效率相较于基于双向链表的LinkedList也要更好一些。注意:ArrayDeque不支持为null的元素。

    LinkedList

    LinkedList与ArrayList一样实现List接口,只是ArrayList是List接口的大小可变数组的实现,LinkedList是List 接口链表的实现。基于链表实现的方式使得 LinkedList 在插入和删除时更优于ArrayList。LinkedList实现所有可选的列表操作,并允许所有的元素包括null。除了实现List接口外,LinkedList类还为在列表的开头及结尾 get、remove 和 insert 元素提供了统一的命名方法。这些操作允许将链接列表用作堆栈、队列或双端队列。此类实现 Deque 接口,为 add、poll 提供先进先出队列操作,以及其他堆栈和双端队列操作。所有操作都是按照双重链接列表的需要执行的。在列表中编索引的操作将从开头或结尾遍历列表(从靠近指定索引的一端)。同时,与 ArrayList 一样此实现不是同步的。因此Java里面是建议使用Deque替换Stack的。

    展开全文
  • Deque实现Stack

    2021-02-07 17:46:59
    Stack只有入栈出栈的操作: 把元素压栈:push(E); 把栈顶的元素“弹出”:pop(E); 取栈顶元素但不弹出:peek(E)。 在Java中,我们用Deque可以实现Stack的功能: 把元素压栈:push(E)/addFirst(E); 把栈顶的...
  • 需要引入头文件 deque push_front push_back pop_front pop_back clear C++队列Queue类成员函数如下: back()返回最后一个元素 empty()如果队列空则返回真 front()返回第一个元素 pop()删除第一个元素 push()在末尾...
  • Deque是Queue的子接口,我们知道Queue是一种队列形式,而Deque则是双向队列,它支持从两个端点方向检索插入元素,因此Deque既可以支持LIFO形式也可以支持LOFI形式.Deque接口是一种比Stack和Vector更为丰富的抽象数据...
  • deque和vector的最大差异在于: deque运行常量时间内催起头段进行元素的插入和移除操作 deque没有所谓容量的观念,因为它是动态地以分段连续空间组合而成,随时可以增加一段新的空间并链接起来。 理解deque的关键...
  • STL--dequestack、queue

    千次阅读 多人点赞 2021-04-30 21:50:33
    双开口的含义是:可以在头尾两端进行插入删除操作,且时间复杂度为O(1),与vector比较,头插效率高,不必搬动数据;与list相比,空间利用比较高。 deque并不是真正连续的空间,而是由一段段连续的小空间拼接而成...
  • deque和vector的最大差异,一在于deque允许于常数时间对头端进行插入和删除操作,二在于deque没有所谓容量(capacity)观念,换句话说,像vector那样“因旧空间不足而重新配置一块更大空间,然后复制元素,再释放...
  • 1)deque是“double-ended queue”的缩写,vector一样都是STL的容器,deque是双端数组,而vector是单端的。 2)deque在接口上vector非常相似,在许多操作的地方可以直接替换。 3)deque可以随机存取元素(支持索引...
  • 数组[],可理解为Java提供的原生态容器类型,在时间空间上,肯定会有其独特的优势。List,Set,Map,Table,Java提供的标准容器类,提供了大量便利的方法,以及内部机制的优化处理。从时间的角度,cpu运行时间;从...
  • deque得底层并不是连续空间,但通过deque iterator中得函数重载模拟出了连续空间得效果。 stack queue直接内置一个deque来实现对应功能。 list也可以作为stack queue的容器,
  • STL源码剖析——deque的实现原理使用方法详解 STL源码剖析】第四章 序列式容器 之 deque底层实现 这个有点厉害,不过没看完。。STL中的deque及源码实现 std::deque 核心为内存管理,对不连续的缓冲区的管理。 .....
  • 文章目录string容器string容器的基本概念构造函数赋值操作字符串拼接string查找替换字符串比较字符串存取string的插入删除string子串vector...赋值操作大小操作插入删除数据存取deque 容器排序stack 容器基本...
  • 0deque容器 双向开口的连续线性空间,可以在队首和尾部进行快速的插入...deque和vector的区别: deque没有容量的概念,它是动态的以分段连续空间组合而成的,随时可以增加一段新的空间 并链接起来,像vector那样...
  • deque概述 双向开口的连续线性空间,可以在头尾两端分别做插入删除。
  • deque是“double-ended queue”的缩写,vector一样都是STL的容器,deque是双端的,而vector是单端的。 deque在接口上vector非常相似,在许多操作的地方可以直接替换。 deque可以随机存取元素(支持索引值直接...
  • 我们知道,Queue是队列,只能一头进,另一头出。 如果把条件放松一下,允许两头都进,...我们来比较一下Queue和Deque出队入队的方法: Queue Deque 添加元素到队尾 add(E e) / offer(E e) addLast.
  • queue、dequestack、 list用法区别简介

    千次阅读 2018-02-09 21:18:21
    Map中可以将KeyValue单独抽取出来,其中KeySet()方法可以将所有的keys抽取正一个Set。而Values()方法可以将map中所有的values抽取成一个集合。 Set 不包含重复元素的集合,set中最多包含一个n...
  • STL学习总结(2)一、deque容器初始化赋值 大小操作deque容器插入删除二、stack容器三、queue容器 一、deque容器 双端数组 特性总结: 双端插入删除元素效率较高。 指定位置插入也会导致数据元素移动,降低效率...
  • 所谓序列式容器、其中的元素都可序,但未必有序。STL提供了vector,list,deque,stack,queue,priority-queue...其中stack和queue由于只是将deque改头换面,技术上被归类为一种配接器(adapter),以下总结了序列式容器。
  • Java 双向队列Deque Stack

    千次阅读 2019-03-07 14:42:37
    //定义Deque Deque&lt;Integer&gt; Q=new ArrayDeque&lt;Integer&gt;(); //向尾部插入元素 Q.addLast(x); //向头部插入元素 Q.addFirst(x); //遍历Deque Iterator it=Q.iterator(); while(it....
  • 支持高效的随机访问在尾端插入/删除操作,但其他位置的插入/删除操作效率低下;相当于一个数组,但是与数组的区别为:内存空间的扩展。vector的初始化操作 int main(){ vector<int> v1; ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,313
精华内容 525
关键字:

deque和stack