Lecture
Abstract data type (ADT) — is a mathematical model for data types, where a data type is defined by its behavior (semantics) from the point of view of the user of the data, namely in terms of the possible values, the possible operations on data of this type, and the behavior of those operations.
Formally, an ADT can be defined as a set of objects, defined by a list of components (operations applicable to these objects, and their properties). The entire internal structure of such a type is hidden from the software developer — this is the essence of abstraction. An abstract data type defines a set of functions, independent of the specific implementation of the type, for operating on its values. Concrete implementations of an ADT are called data structures.
In programming, abstract data types are usually represented as interfaces, which hide the corresponding implementations of the types. Programmers work with abstract data types exclusively through their interfaces, since the implementation may change in the future. This approach corresponds to the principle of encapsulation in object-oriented programming. The strong point of this technique is precisely the hiding of the implementation. Since only the interface is published externally, as long as the data structure supports this interface, all programs that work with the given data structure through the abstract data type will keep working. Developers of data structures try, without changing the external interface and the semantics of the functions, to gradually refine the implementations, improving the algorithms in terms of speed, reliability, and memory used.
The difference between abstract data types and the data structures that implement abstract types can be explained with the following example. The abstract data type list can be implemented using an array or a linked list, using various methods of dynamic memory allocation. However, each implementation defines the same set of functions, which must work identically (in terms of result, not speed) for all implementations.
Abstract data types make it possible to achieve modularity of software products and to have several alternative interchangeable implementations of a single module.
In computer science, an abstract data type ( ADT ) is a mathematical model for data types. An abstract data type is defined by its behavior ( semantics ) from the point of view of the user of the data, in particular from the point of view of the possible values, the possible operations on data of this type, and the behavior of those operations. This mathematical model differs from data structures, which are concrete representations of data and represent the developer's point of view rather than the user's.
Formally, an ADT can be defined as «a class of objects whose logical behavior is defined by a set of values and a set of operations»; this is the analogue of an algebraic structure in mathematics. What is meant by «behavior» depends on the author, with two main types of formal behavior specifications being axiomatic (algebraic) specification and abstract model; These correspond to axiomatic semantics and operational semantics as an abstract machine, respectively. Some authors also include computational complexity («cost»), both in terms of time (for computational operations) and space (for representing values). In practice, many common data types are not ADTs, since the abstraction is not perfect, and users must be aware of issues such as arithmetic overflow, which are related to the representation. For example, integers are often stored as fixed-width values (32-bit or 64-bit binary numbers) and thus experience integer overflow if the maximum value is exceeded.
ADTs represent a theoretical concept in the field of computer science, used in the design and analysis of algorithms, data structures, and software systems, and they do not correspond to specific features of computer languages — mainstream computer languages do not directly support formally defined ADTs. Nevertheless, various language features correspond to certain aspects of ADTs, and they are easily confused with actual ADTs; these include abstract types, opaque data types, protocols, and design by contract. ADTs were first proposed by Barbara Liskov and Stephen N. Zilles in 1974, as part of the development of the CLU language.
For example, integers are an ADT defined as the values ..., -2, -1, 0, 1, 2, ... together with the operations of addition, subtraction, multiplication, and division, along with greater than, less than, etc., which behave in accordance with familiar mathematics (with care taken for integer division), regardless of how the integers are represented by the computer. [a] Explicitly, «behavior» includes satisfying various axioms (associativity and commutativity of addition, etc.) and preconditions for operations (cannot divide by zero). Typically, integers are represented in the data structure as binary numbers, most often as two's complement, but it could be binary-coded decimal or ones' complement, but the user abstracts away from the specific choice of representation and can simply use the data as data types.
An ADT consists not only of operations, but also of the values of the underlying data and constraints on the operations. The «interface» usually refers only to the operations and, possibly, to some constraints on the operations, especially preconditions and postconditions, but not to other constraints, such as relations between operations.
Examples of ADTs
Some common ADTs that have proven useful in a wide range of applications:
Each of these ADTs can be defined in many ways and variants, not necessarily equivalent. For example, an abstract stack may or may not have a countoperation, which reports how many elements have been pushed but not yet popped. This choice matters not only to clients, but also to the implementation.
Abstract graphical data type
An extension of the ADT for computer graphics was proposed in 1979: the abstract graphical data type (AGDT). It was introduced by Nadia Magnenat Thalmann and Daniel Thalmann. AGDTs provide the advantages of ADTs together with facilities for the structured construction of graphical objects.
For example, an abstract stack, which is a «first in, first out» structure, can be defined by three operations: push, which inserts a data item into the stack; pop, which removes a data item from it; and peek or top, which accesses the data item at the top of the stack without removing it. An abstract queue, which is a «first in, first served» structure, will also have three operations: enqueue, which inserts a data item into the queue; dequeue, which removes the first data item from it; as well as front, which accesses and serves the first data item in the queue. There would be no way to differentiate these two data types if a mathematical constraint were not introduced which, for a stack, states that every pop always returns the most recently pushed element that has not yet been removed. When analyzing the efficiency of algorithms that use stacks, it can also be specified that all operations take the same amount of time regardless of how many data items have been placed on the stack, and that the stack uses a constant amount of memory per element.
Abstract data types are purely theoretical objects, used (among other things) to simplify the description of abstract algorithms, to classify and evaluate data structures, and also to formally describe the type systems of programming languages. However, an ADT can be implemented by concrete data types or data structures in many ways and in many programming languages; or described in a formal specification language. ADTs are often implemented as modules: the module's interface declares procedures that correspond to the operations of the ADT, sometimes with comments that describe the constraints. This information is hidden. This strategy makes it possible to change the module's implementation without disrupting client programs.
The term abstract data type can also be regarded as a generalized approach to a number of algebraic structures, such as lattices, groups, and rings. The notion of abstract data types is related to the concept of data abstraction, important in object-oriented programming and in design by contract software development methodologies.
The data structures we will look at in this lesson are united by the fact that they are built on top of arrays to efficiently solve a certain class of problems. In C++, the stack, queue, and heap data structures can be implemented on the basis of the container classes vector and deque. We got acquainted with vector earlier, now it is time to get acquainted with deque.
Deque, double-ended queue (from English deque — double ended queue) — a data structure representing a list of elements, in which new elements are added and existing ones are removed from both ends of the array. This allows many problems to be solved directly with a deque, abstracting to the needed data structure.
The deque container is very similar to vector. deque is also a sequential random-access container, and therefore supports indexing ([], at()), the methods front() and back(), as well as most other methods of the vector class. Deque has similar iterators, including reverse ones. But, unlike vector, growing a deque is more efficient, since memory reallocation does not occur (elements are not moved to a new region in case the current one overflows). Deque is a more complex data structure, its elements are not always located in one area of memory. If a vector can be compared to a C array, then a deque can be represented as a set of several C arrays (one or more), used as a single object.
The main difference of deque from (like vector) is that it is open at both ends. Inserting elements at the beginning and at the end of a deque is very fast. But traversing a deque with iterators will be slower than traversing a vector. Any insertion or removal that is not at the beginning or not at the end of the deque will invalidate both the begin and end iterators (including pointers and references to the remaining elements). If the insertion is made at the beginning or at the end of the array, only the iterators will be invalidated, while references and pointers will remain valid.
For the deque container, no methods are defined for working with the capacity, such as capacity() and reserve(), but the method shrink_to_fit() can be used. This is because, when the size of the deque is reduced, its capacity does not decrease. This method does not necessarily perform the operation of reducing capacity() to size().
Let's solve the following problem using a deque.
Problem 1. Given an array ar and numbers m and n, defining positions of elements in the array ar (m < n). Find the minimum element on this segment. Solve this problem using a deque.
Based on a deque, one can model the stack and queue data structures. For this, C++ uses container adapters. The template class of the stack container adapter is a wrapper over an underlying container and provides only a certain set of functions characteristic of a stack.
Stack is a data structure in which elements are added and removed at the top of the stack. The array of elements is organized according to the LIFO (English last in — first out, «last came — first left») principle. Such a structure can be represented as a stack of plates (or books): access to the second (top) plate can only be obtained after the first plate has been taken.
The stack adapter is built (by default) on the deque container.
The following methods are defined for stack:
In addition to these methods, all comparison operations and the assignment operation are supported.
Let us consider one of the problems that can easily be solved using a stack.
Problem 2. In postfix notation of an arithmetic expression, the operation is written after its two operands. For example, the sum of two numbers A and B is written as A B +. The notation B C + D * denotes (B + C) * D, and the notation A B C + D * + means A + (B + C) * D. The advantage of postfix notation is that it does not require parentheses or additional operator-precedence conventions to be read.
Given an expression in postfix notation, containing numbers, the operations +, –, *. Compute the value of the expression written in postfix form (also called reverse Polish notation). Numbers and symbols must be separated by a single space.
Input/output
Enter a string representing an arithmetic expression: 5 5 4 + 10 * + 95
Queue — is a data structure in which an element can be added only to the end of the queue, and retrieval — only from the front of the queue, with the retrieved element being removed from the queue. The array of elements is organized according to the FIFO (English First In — First Out, «first came — first left») principle.
To implement this data structure, C++ uses the queue adapter. The queue adapter is built (by default) on the deque container.
The following methods are defined for queue:
In addition to these methods, all comparison operations and the assignment operation are supported.
The queue has found its application in the algorithms of the so-called breadth-first traversal of a tree (or graph) (English breadth-first search, BFS). Without going deep into graph theory, let us look at an example of such a problem based on a state exam (EGE) problem.
Problem 3. Vasya, solving state exam (EGE) format problems, came across a problem about a performer:
«The performer Calculator has two commands:
34Executing the first of them, the Calculator adds 3 to the number on the screen, and executing the second, multiplies it by 4».
Further, the problem required obtaining the number 57 from the number 3 in no more than 6 commands. However, Vasya became interested in how, for arbitrary numbers a and b, one could construct the shortest program to obtain the number b from the number a. Write a program that, given numbers a and b, computes the smallest number of Calculator commands needed to obtain the number b from a. The total number of commands must not exceed 10.
Heap (other names: binary heap, pyramid, sorting tree) — is a data structure represented as a tree. A classical heap has no restriction on the number of children, but in practice there are always two. Therefore such a heap is called a binary heap. It satisfies the heap property: if B is a child node of node A, then key A ≥ key B. It follows from this that the element with the largest key is always the root node of the heap, which is why such heaps are sometimes called max-heaps (maximum heaps).
For a binary heap tree, three conditions must hold:
To implement a heap, any sequential container or C array can be used. The root element — is A , and the children of element A[i] — are A[2*i+1] and A[2*i+2].
Then the indices, in the form of a tree, can be represented as follows:
A heap is the most efficient implementation of the abstract data type called a priority queue (priority queue). A priority queue is used in programs that involve finding the maximum (or minimum) element in some array of data (for example, the most active users of a social network). But this is not its only application. With a priority queue one can organize a task scheduler, search for optimal paths, predict events, and many other tasks.
algorithm library (see here).priority_queue (along with queue and stack) is a container adapter. The priority queue is, by default, built on the vector container (this can be changed, as with other adapters). priority_queue prevents accidental invalidation of the heap. The elements of the queue are automatically sorted in descending order (max-heap). The sort direction can be changed using a comparator.
For priority_queue (header - queue) the following methods are defined:
A heap can be used to perform a heap sort. It is performed by inserting all elements of the sequence into a heap and then extracting all elements of the heap in order starting from the largest value. Let us consider two variants. The first variant is based on using priority_queue. The downside of this variant is output (or another operation) that removes elements.
priority_queue in C++ implements a max-heap. In it, as already stated, elements are ordered from largest to smallest. To change the sort direction, in addition to the element type, the template parameter of the constructor is passed two more optional elements: the type of the underlying container, and a comparator that reverses the sort direction (see line 18 in program 9.6.4; the comparator is a built-in comparison function or a functor — greater).
array, because the latter does not support the insert operation.The second variant is based on using the generic algorithms library.
After the sort is performed, the array loses the heap property.
Let us solve the following problem.
Problem 4. N players (N >= 3) take part in the game. In each round, the users take turns rolling a die. The results are summed for each round, and the number of rounds is unlimited. At the end of the game, the three participants with the highest results are identified. The outright winner is the player who is the first to score more than 20 points.
Possible output
Enter the number of players: 6 Player #2 Score => 24 Player #5 Score => 23 Player #6 Score => 18
An abstract data type is defined as a mathematical model of the data objects that make up the data type, as well as of the functions that operate on these objects. There are no standard conventions for defining them. A broad division can be made between «imperative» and «functional» styles of definitions.
In the philosophy of imperative programming languages, an abstract data structure is understood as a mutable entity, meaning that it can be in different states at different times. Some operations can change the state of the ADT; consequently, the order in which operations are evaluated matters, and the same operation on the same objects can have different consequences if it is performed at different times — just like the instructions of a computer or the commands and procedures of an imperative language. To emphasize this view, it is customary to say that operations are performed or applied, rather than evaluated, The imperative style is often used when describing abstract algorithms. (See «The Art of Computer Programming» by Donald Knuth for more details)
Abstract variable
Imperative-style definitions of ADTs often depend on the concept of abstract variable, which can be regarded as the simplest non-trivial ADT. An abstract variable V is a mutable entity that admits two operations:
with the constraint that
As in many other programming languages, the operation store( V , x ) is often written as V ← x (or some similar notation), and fetch( V ) is implied whenever the variable V is used in a context where a value is required. Thus, for example, V ← V + 1 is usually understood as shorthand for store( V , fetch( V ) + 1).
This definition implicitly assumes that storing a value in a variable U has no effect on the state of a separate variable V . To make this assumption explicit, one can add the constraint
More generally, ADT definitions often assume that any operation that changes the state of one instance of an ADT does not affect the state of any other instance (including other instances of the same ADT) — unless the axioms of the ADT imply that the two instances are linked (aliased) in this sense. For example, when extending the definition of abstract variables to include abstract records, an operation that selects a field from a record variable R should yield a variable V , which is an alias to that part of R .
The definition of an abstract variable V may also restrict the stored values x to members of a specific set X , called the range or type of V . As in programming languages, such restrictions can simplify the description and analysis of algorithms and improve their readability.
Note that this definition says nothing about the result of evaluating fetch( V ) when V is uninitialized , that is, before any store operation has been performed on V . An algorithm that does this is usually considered invalid, because its effect is undefined. (Nevertheless, there are some important algorithms whose efficiency heavily relies on the assumption that such a fetch is legal, and returns some arbitrary value in the variable's range.)
Instance creation
Some algorithms need to create new instances of certain ADTs (for example, new variables or new stacks). To describe such algorithms, the ADT definition usually includes a create() operation, which yields an instance of the ADT, usually with axioms equivalent to
This axiom can be strengthened to also exclude partial aliasing with other instances. On the other hand, this axiom still allows implementations of create() to yield a previously created instance that has become inaccessible to the program.
Example: abstract stack (mandatory)
As another example, an abstract definition of a stack in an imperative style may specify that the state of the stack S can only be changed by the operations
with the restriction that
Since the assignment V ← x by definition cannot change the state of S , this condition implies that V ← pop( S ) restores S to the state it was in before push( S , x ). From this condition and the properties of abstract variables it follows, for example, that the sequence
{ push( S , x ); push( S , y ); U ← pop( S ); push( S , Z ); V ← pop( S ); W ← pop( S )}
where x , y and z are any values, and U , V , W are pairwise distinct variables, is equivalent to
{ U ← y ; V ← z ; W ← x }
Here it is implicitly assumed that operations on an instance of the stack do not change the state of any other instance of the ADT, including other stacks; that is,
The abstract definition of a stack usually also includes a Boolean-valued function empty( S ) and a create() operation, which returns an instance of the stack, with axioms equivalent to
Single-instance style
Sometimes an ADT is defined as if only one instance of it existed during the execution of the algorithm, and all operations were applied to this instance, which is not explicitly recorded. For example, the abstract stack above can be defined with the operations push( x ) and pop(), which operate on the one existing stack. Definitions of ADTs in this style can easily be rewritten to allow several coexisting instances of the ADT, by adding an explicit instance parameter (like S in the previous example) to each operation that uses or modifies the implicit instance.
On the other hand, some ADTs cannot be meaningfully defined without allowing for several instances. This is the case when a single operation takes two different instances of the ADT as parameters. For example, consider augmenting the definition of the abstract stack with a compare( S , T ) operation, which checks whether the stacks S and T contain the same elements in the same order.
Another way to define an ADT, closer to the spirit of functional programming, is to treat each state of the structure as a separate entity. In this view, any operation that modifies the ADT is modeled as a mathematical function that takes the old state as an argument and returns the new state as part of the result. Unlike imperative operations, these functions have no side effects. Consequently, the order in which they are evaluated does not matter, and the same operation applied to the same arguments (including the same input states) will always return the same results (and output states).
In the functional representation, in particular, there is no way (or need) to define an «abstract variable» with the semantics of imperative variables (namely, with fetch and store operations). Instead of storing values in variables, they are passed as arguments to functions.
Example: abstract stack (functional)
For example, a complete functional-style definition of an abstract stack may use three operations:
A functional-style definition has no need for a create operation. Indeed, there is no notion of a «stack instance». Stack states can be regarded as potential states of a single stack structure, and two stack states that contain the same values in the same order are considered identical states. This representation actually reflects the behavior of some concrete implementations, such as linked lists with hash-minuses.
Instead of create(), a functional-style definition of an abstract stack may assume the existence of a special stack state, the empty stack , denoted by a special symbol such as Λ or "()"; or define a bottom() operation, which takes no arguments and returns this special stack state. Note that the axioms imply that
A functional-style stack definition does not require an empty predicate: instead, one can check whether the stack is empty by checking whether it equals Λ.
Note that these axioms do not define the effect of top( s ) or pop( s ) unless s is a stack state returned by a push. Since a push leaves the stack non-empty, these two operations are undefined (hence invalid) when s = Λ. On the other hand, the axioms (and the absence of side effects) imply that push( s , x ) = push( t , y ) if and only if x = y and s = t .
As in some other branches of mathematics, it is also customary to assume that the only stack states are those whose existence can be proved from the axioms in a finite number of steps. In the abstract stack example above, this rule means that every stack is a finite sequence of values, which becomes the empty stack (Λ) after a finite number of pops. By themselves, the above axioms do not exclude the existence of infinite stacks (which can be popped forever, each time obtaining a different state) or circular stacks (which return to the same state after a finite number of pops). In particular, they do not exclude states s such that pop( s ) = s or push( s ,x ) = s for some x . However, since it is impossible to obtain such stack states using the given operations, they are assumed «not to exist».
Besides behavior in terms of axioms, the algorithmic complexity of ADT operations can also be included in their definition. Alexander Stepanov, the designer of the C++ Standard Template Library, included complexity guarantees in the STL specification, stating:
The reason for introducing the notion of abstract data types was the use of interchangeable software modules. You cannot have interchangeable modules unless those modules have similar complexity behavior. If I replace one module with another module having the same functional behavior but different complexity trade-offs, the user of that code will be unpleasantly surprised. I could tell him whatever I like about data abstraction, and he still would not want to use the code. Complexity guarantees must be part of the interface.
- Alexander Stepanov
Abstraction gives the promise that any implementation of an ADT has certain properties and capabilities; knowing this is all that is required to use an ADT object. The user does not need any technical knowledge of how the implementation works in order to use the ADT. Thus the implementation can be complex, but in actual use it will be wrapped in a simple interface.
Code that uses an ADT object will not need to be edited if the implementation of the ADT changes. Since any changes to the implementation must still conform to the interface, and since code that uses the ADT object can refer only to the properties and capabilities specified in the interface, changes can be made to the implementation without requiring any changes to the code where the ADT is used.
Different implementations of an ADT that have all the same properties and capabilities are equivalent and can be somewhat interchangeable in code that uses the ADT. This gives great flexibility when using ADT objects in various situations. For example, different implementations of an ADT may be more efficient in different situations; they can be used in the situation where they are preferable, which improves overall efficiency.
Some operations that are often specified for an ADT (possibly under other names)
In imperative-style ADT definitions one can often find
The free operation is usually not relevant or meaningful, since ADTs are theoretical entities that do not «use memory». Nevertheless, this may be necessary when one needs to analyze the storage used by an algorithm that uses an ADT. In this case additional axioms are needed, which define how much memory each instance of the ADT uses, depending on its state, and how much of it is returned to the free pool.
Further information: opaque data type
Implementing an ADT means providing a single procedure or function for each abstract operation. Instances of the ADT are represented by some concrete data structure, which these procedures manipulate in accordance with the ADT's specifications.
Usually there are many ways to implement the same ADT, using several different concrete data structures. Thus, for example, an abstract stack can be implemented using a linked list or an array.
So that clients do not depend on the implementation, an ADT is often packaged as an opaque data type in one or more modules, whose interface contains only the signature (the number and types of the parameters and results) of the operations. The implementation of the module, namely the bodies of the procedures and the concrete data structure, can be hidden from most clients of the module. This allows the implementation to be changed without affecting the clients. If the implementation is exposed, it is known as a transparent data type.
When implementing an ADT, each instance (in imperative-style definitions) or each state (in functional-style definitions) is usually represented by some kind of handle.
Modern object-oriented languages, such as C ++ and Java , support a form of abstract data types. When a class is used as a type, it is an abstract type that refers to a hidden representation. In this model an ADT is usually implemented as a class , and each instance of the ADT is usually an object of that class. The module's interface usually declares constructors as ordinary procedures, and most of the other ADT operations as methods of that class. However, this approach does not easily encapsulate several representation variants found in an ADT. It can also undermine the extensibility of object-oriented programs. In a purely object-oriented program that uses interfaces as types, types relate to behavior rather than to representations.
As an example, here is an implementation of the abstract stack above in the C programming language.
Imperative-style interface
An imperative-style interface might be:
typedef struct stack_Rep stack_Rep ; // type: representation of a stack instance (opaque record) typedef stack_Rep * stack_T ; // type: handle of a stack instance (opaque pointer) typedef void * stack_Item ; // type: value stored in a stack instance (arbitrary address) stack_T stack_create ( void ); // creates a new empty stack instance void stack_push ( stack_T s , stack_Item x ); // adds an item to the top of the stack stack_Item stack_pop ( stack_T s ); // removes the top item from the stack and returns it bool stack_empty ( stack_T s ); // checks whether the stack is empty
This interface could be used as follows:
#include // includes the stack interface
stack_T s = stack_create (); // creates a new empty stack instance
int x = 17 ;
stack_push ( s , & x ); // adds the address of x to the top of the stack
void * y = stack_pop ( s ); // removes the address of x from the stack and returns it,
if ( stack_empty ( s )) { } // does something if the stack is empty
This interface can be implemented in many ways. The implementation may be arbitrarily inefficient, since the formal definition of the ADT above does not specify how much space the stack may use, or how much time each operation should take. It is also not specified whether the state s of the stack continues to exist after calling x ← pop( s ).
In practice, a formal definition should specify that the space is proportional to the number of items pushed and not yet retrieved; and that each of the above operations should complete in a constant amount of time, regardless of that number. To meet these additional specifications, an implementation might use a linked list or an array (with dynamic resizing) together with two integers (the number of elements and the size of the array).
Functional-style interface
Functional-style ADT definitions are better suited to functional programming languages, and vice versa. Nevertheless, it is possible to provide a functional-style interface even in an imperative language such as C. For example:
typedef struct stack_Rep stack_Rep ; // type: representation of a stack state (opaque record) typedef stack_Rep * stack_T ; // type: handle of a stack state (opaque pointer) typedef void * stack_Item ; // type: value of a stack state (arbitrary address) stack_T stack_empty ( void ); // returns the empty stack state stack_T stack_push ( stack_T s , stack_Item x ); // adds an item to the top of a stack state and returns the resulting stack state stack_T stack_pop ( stack_T s ); // removes the top item from a stack state and returns the resulting stack state stack_Item stack_top ( stack_T s ); // returns the top item of a stack state
Many modern programming languages, such as C ++ and Java, come with standard libraries that implement several common ADTs, such as those listed above.
The specification of some programming languages is deliberately vague about the representation of certain built-in data types, defining only the operations that can be performed on them. Consequently, these types can be regarded as «built-in ADTs». Examples are arrays in many scripting languages, such as Awk , Lua and Perl , which can be regarded as an implementation of an abstract list.
| Characteristic | Queue | Stack | Linked List | Array | Deque | Heap |
|---|---|---|---|---|---|---|
|
Principle of operation
|
FIFO (first in — first out) | LIFO (last in — first out) | Elements linked by pointers | Indices are fixed | Access to both ends | A tree where the parent >= (max heap) or <= (min heap) its children |
|
Adding elements
|
To the end (enqueue) | To the end (push) | To the beginning or end | At any position | To the beginning or end | To the root (with balancing) |
|
Removing elements
|
From the beginning (dequeue) | From the end (pop) | At any position (requires traversal) | At any position (but requires shifting) | From the beginning and end | From the root (with swapping) |
|
Element access
|
Only the first (head) | Only the last (top) | Sequential (via links) | Direct access by index | To the beginning and end | Only the root (the largest or smallest element) |
|
Running time (average)
|
O(1) (add/remove) | O(1) (add/remove) | O(1) (add to beginning/end) | O(1) (access), O(n) (insertion/deletion) | O(1) (operations at the ends) | O(log n) (add, remove, access to root) |
| Where it is used | Background tasks, thread management, BFS algorithms | Recursion, undo actions (Ctrl+Z) | Dynamic structures, graph traversal | Static structures, fast access | Buffers, parsers, data processing | Priority queue, Dijkstra's and Huffman's algorithms, storing classes |
 |
 |
 |
 |
 |
 |
Comments