双端队列

抽象数据类型

双端队列(deque,全名double-ended queue)是一种具有队列性质的抽象数据类型。双端队列中的元素可以从两端弹出,插入和删除操作限定在队列的两邊进行。

操作

双端队列可以在队列任意一端入队出队。此外,经常还会有一个查看(Peek)操作,返回该端的数据而不将其出队。

操作的名称依语言的不同而不同;主流实现包括:

操作 常见名称 Ada C++ Java Perl PHP Python Ruby JavaScript
尾部插入 inject, snoc Append push_back offerLast push array_push append push push
头部插入 push, cons Prepend push_front offerFirst unshift array_unshift appendleft unshift unshift
尾部删除 eject Delete_Last pop_back pollLast pop array_pop pop pop pop
头部删除 pop Delete_First pop_front pollFirst shift array_shift popleft shift shift
查看尾部 Last_Element back peekLast $array[-1] end <obj>[-1] last <obj>[<obj>.length - 1]
查看头部 First_Element front peekFirst $array[0] reset <obj>[0] first <obj>[0]

外部链接