Перейти к содержимому

В чем разница между queue и deque и stack

  • автор:

2313. Java Core — Stack, Queue and Deque Queue, Stack, Queue, and Heap

Java Stack extends Vector class with the following five operations only.

  • boolean empty(): Tests if this stack is empty.
  • E peek(): Looks at the object at the top of this stack without removing it from the stack.
  • E pop() : Removes the object at the top of this stack and returns that object as the value of this function.
  • E push(E item) : Pushes an item onto the top of this stack.
  • int search(Object o) : Returns the 1-based position where an object is on this stack.

1.2 Deque Interface and LinkedList Class

Deque interface supports adding and removing elements from both ends of the queue. If we only use the push and pop methods, it behaves just like a stack.

2. Queue

2.1 Java Queue Categories

Bounded Queues are queues which are bounded by capacity that means we need to provide the max size of the queue at the time of creation. For example ArrayBlockingQueue.

  • Bounded Queues
  • Unbounded Queues

All Queues which implement BlockingQueue interface are BlockingQueues and rest are Non-Blocking Queues.

  • Blocking Queues
  • Non-Blocking Queues

2.2 Constructing Queue

2.3 Common Operations

Java Queue supports all operations supported by Collection interface and some more operations. It supports almost all operations in two forms.

Data Structures Part 2: Stack, Queue, and Deque ADTs

Cameron Fisher

In Data Structures Part 1, we focused on Concrete Data Types. We discussed Arrays, Singly Linked Lists, Doubly Linked Lists, and Circular Linked Lists. Please read Part 1 for context before starting with Part 2.

Stack ADT

A Stack is a linear data structure that stores arbitrary objects. Stack operations are performed based on the Last In First Out (LIFO) principle. Data is inserted at the top (last node) and removed at the top (last node) of the stack. A Stack can be implemented using either an Array or a Singly Linked List as the underlying data structure.

History and applications of a Stack

The name “Stack” was derived from the metaphor of a stack of plates in a spring-loaded plate dispenser. A plate dispenser’s operations involve pushing and popping plates on the stack.

The Stack data structure is used by text editors for the undo or redo operations, string reversal, and web browsers for page-visited history. A Stack can also be used indirectly as an auxiliary data structure when writing algorithms or as a component of other data structures.

Operations

A Stack supports the following two main methods:

push(e): Insert element e, to be the top of the stack.

pop(): Removes the topmost element from the stack, or null if the stack is empty.

A Stack supports the following three auxiliary methods:

size(): Returns the number of elements in the stack.

isEmpty: Returns a Boolean value indicating if the stack is empty or not.

top(): Returns the topmost element in the stack or null if the stack is empty.

Performance and memory usage

A Stack can be implemented using either an Array or a Singly Linked List CDTs.

Array-Based: An ArrayStack is easy to implement and efficient. Each operation runs in time O(1). The memory usage is O(n), where n represents the number of elements. The drawbacks of this implementation are the capacity of the stack needs to be set at compile-time and cannot be changed, and if we try to push a new element onto an already full stack it will throw an exception.

Singly Linked List: Singly Linked List Stack aims to solve the problem identified in the ArrayStack implementation. By using a Singly Linked List under the hood, the capacity of the Stack is dynamic. The top of the will be set to the head of the Singly Linked List since we can insert (push(e)) and delete (pop()) in constant time O(1) at the head. For the size() and isEmpty() methods to run in constant time we can keep track of the number of elements in an instance variable. Therefore, a Stack backed by a Singly Linked List is the most efficient implementation since all operations run in O(1) and memory usage is O(n).

Kotlin Implementation

Queue ADT

A Queue is a linear data structure that stores arbitrary objects. Queue operations are performed based on the First In First Out (FIFO) principle. Data is inserted at the tail (last node) and removed at the head (first node) of the queue. A Queue can be implemented using either an Array or a Singly Linked List as the underlying data structure.

History and Applications of a Queue

The name “Queue” is derived from a line of people waiting to purchase a movie ticket at the Movie Theatre. The first customer in the queue will be removed from the front of the queue. New customers will join the queue from the back (rear).

The Queue data structure is used to access shared resources (printer), message queues, and process scheduling. A Queue can also be used indirectly as an auxiliary data structure when writing algorithms or as a component of other data structures.

Operations

A Queue supports the following operations:

enqueue(e): Inserts the element e at the rear of the queue.

dequeue(): Removes and returns the element at the front of the queue, and returns null if the queue is empty.

front(): Returns the element at the front of the queue, and returns null if the queue is empty.

size(): Returns the number of elements in the queue.

isEmpty(): Returns a Boolean value that indicates whether the queue is empty.

Performance and memory usage

A Queue can be implemented using either an Array, Array-List, or a Singly Linked List CDTs.

Array-Based: To avoid the dequeue() operation from taking O(n) time to run, where n represents the number of elements needed to shift forward, we need to define two variables f and r which have the following meaning.

f: refers to the index of the first element in the Queue, which is next to be dequeued unless the Queue is empty (f = r=0). Initially set to 0. When an element is dequeued we need to increment the f index to the next element in the Queue.

r: refers to the index of the next available cell in the Queue. Initially set to 0. When a new element is enqueued we need to increment the r index to the next available cell in the Queue.

By using the f and r variables we are able to implement the front(), enqueue(e), and dequeue() methods in constant time, O(1). This implementation has two drawbacks. The first drawback is that if we repeatedly enqueue and dequeue element N until f =r=N. If were then to enqueue once more, an IndexOutOfBounds error would be thrown. The second drawback is we have to specify the maximum size of the Queue.

The memory usage in a normal Array-Based Queue is O(n), where n represents the number of elements.

Circular Queue (Array-Based): The Circular Queue implementation aims to solve the first problem identified in the normal Array-Based Queue implementation. To implement a Circular Queue the modulo (%) operator is used, to wrap indices around the end of the Array, (f + 1) % N or (r + 1) % N. Each method in a Circular Queue runs in constant time, O(1).

The memory usage in a Circular Queue is O(n), where n represents the number of elements. Since this implementation also uses an Array under the hood, the second drawback identified in the Array-Based implementation still exists here.

Singly Linked List: The Singly Linked List implementation aims to solve the drawbacks identified in the previous two implementations. By using a Singly Linked List under the hood, each Queue operation runs in time O(1) and we don’t have to specify the maximum size of the Queue. This benefit comes at the expense of increasing the amount of space used as new elements are added to the Queue. The memory usage is O(n), where n represents the number of elements.

To implement a Queue using a Singly Linked List we need to maintain references to both head and tail nodes in the list. In this way, we can remove from the head and add new nodes at the tail efficiently.

Deque ADT

A Deque, also known as a double-ended queue, is a data structure that supports insertion and deletion operations at both the front and back of the queue. A Deque is usually pronounced as “deck” to avoid confusion with the dequeue method of a Queue ADT.

History and Applications of a Queue

A Deque can be used to implement a waitlist feature in a Restaurant application. The restaurant usher might remove the first customer from the queue to find that there are no tables available. Thus, the usher will reinsert the customer at the front of the queue. The customer at the end of the queue might feel that the queue is too long and leave the restaurant.

We can also think of its application in a web browser's history, where the most recently visited sites are added to the front of the deque and the sites at the back of the deque are removed after N minutes.

Operations

A Deque supports the following operations:

addFirst(e): Inserts a new element e at the front of the deque.

addLast(e): Inserts a new element e at the back of the deque.

removeFirst(): Removes and returns the first element of the deque. Returns null if the deque is empty.

removeLast(): Removes and returns the last element of the deque. Returns null if the deque is empty.

first(): Returns the first element of the deque. Returns null if the deque is empty.

last(): Returns the last element of the deque. Returns null if the deque is empty.

size(): Returns the number of elements in the deque.

isEmpty(): Returns a boolean value indicating whether or not the deque is empty.

Performance and memory usage

A Deque ADT using a Doubly Linked List under the hood, does not have a predefined size. Thus, the space used by a list with n elements is O(n). All Deque operations run in constant time, O(1).

Kotlin Implementation

Conclusion

In Data Structures Part 3: List Abstractions, we’ll discuss Array-List ADT, Position & Positional List ADT, and Iterators.

Stacks, Queues and Deques Data Structure Guide

Stacks and queues are linear data structures that only usually support push, pop, and peek operations, with no random access. Items must be traversed sequentially.

  • Stack: An ordered collection of items where new items are added and existing items removed from the same end (top). (LIFO: Last in, first out)
  • Queue: An ordered collection of items where new items are added to the rear, and existing items removed from the front. (FIFO: First-in first-out.)

This guide walks you through everything you need to know about the stack, queue, and deque data structures, with clear, commented code samples.

Properties of a Stack

  • Items that are closer to the base of the stack have been there the longest
  • Think of as a stack of plates
  • Can only add and remove to top of stack
  • LIFO (Last in, first out)
  • Can build with either arrays or linked lists
  • Cache locality can make arrays faster for search
  • If not dynamic array, could be more expensive to grow it
  • e.g. Browser history back and forward buttons

Properties of a Queue

  • Items that are closer to the front of the queue have been there the longest
  • FIFO (First in, first out)
  • Usually don’t lookup in a queue
  • Best implemented with a linked list. Faster to remove items without shift
  • e.g. Printer queue of documents to be printed, or a queue of people

Big O Time Complexity

Stacks

  • lookup: O(n)
  • pop: O(1)
  • push: O(1)
  • peek: O(1)

Queues

  • lookup: O(n)
  • enqueue: O(1)
  • dequeue: O(1)
  • peek: O(1)

Pros and Cons of Stacks

Pros:

  • Fast Operations
  • Fast Peek
  • Ordered

Cons:

  • Slow Lookup

Pros and Cons of Queues

Queues share the same pros and cons as stacks.

Create a Stack in Python

Create a Queue in Python

What is a Deque?

A deque is a double-ended queue, where items can be added and removed from the left or right.

Python includes deques as part of its collections module:

from collections import deque

It’s also possible to create our own deque class using a list.

Create a Deque in Python

Stack and Queue Problems

Problem 1:

Implement a queue using two stacks. (Leetcode: 232)

Solution 1:

About Daniel Andrews

Passionate about all things data and cloud. Specializing in Python, AWS and DevOps, with a Masters degree in Data Science from City University, London, and a BSc in Computer Science.

c++ deque vs queue vs stack

Queue and Stack are a structures widely mentioned. However, in C++, for queue you can do it in two ways:

but for stack you can only do it like this

My question is, what’s the difference between queue and deque, why two structures proposed? For stack, any other structure could be included?

TheArchitect's user avatar

9 Answers 9

Moron/Aryabhatta is correct, but a little more detail may be helpful.

Queue and stack are higher level containers than deque, vector, or list. By this, I mean that you can build a queue or stack out of the lower level containers.

Will build a stack of ints using a deque as the underlying container and a queue of doubles using a list as the underlying container.

You can think of s as a restricted deque and q as a restricted list.

All that is necessary is that the lower level container implements the methods needed by the higher level container. These are back() , push_back() , and pop_back() for stack and front() , back() , push_back() , and pop_front() for queue.

See stack and queue for more detail.

With respect to the deque, it is much more than a queue where you can insert at both ends. In particular, it has the random access operator[] . This makes it more like a vector, but a vector where you can insert and delete at the beginning with push_front() and pop_front() .

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *