Introduction

Theoretical Foundation

Relation to Data Abstraction

History

Definition

An Abstract Data Type (ADT) is like a mathematical concept, similar to an algebraic structure. Think of it as having three main parts: a domain, a set of operations, and rules that these operations must follow. The domain, even though it's usually not explicitly defined, stands for the free object over the set of ADT operations.

Formally, an Abstract Data Type (ADT) mirrors an algebraic structure in mathematics. It comprises a domain, a set of operations, and a set of constraints governing these operations.

The domain, often implicitly defined, represents the free object over the set of ADT operations. The ADT interface mainly refers to the domain and operations, with some constraints like pre-conditions and post-conditions, but not relations between operations. Two primary styles of formal specifications for behavior are axiomatic semantics and operational semantics.

Axiomatic Semantics: Functional Harmony

In the world of functional programming, each state of an abstract data structure stands alone, like a distinct mathematical entity. Operations act as mathematical functions devoid of side effects. The order of evaluation is inconsequential, and the same operation with the same arguments consistently yields the same results. Constraints are expressed as axioms or algebraic laws.

Operational Semantics: The Dance of Mutability

In imperative programming, an abstract data structure is mutable, subject to the passage of time. Operations alter the state of the ADT over time, where the order of evaluation matters. The same operation on the same entities might produce different outcomes at different times. Think of it as the unfolding of instructions or commands in an imperative language. Constraints are often conveyed in prose, woven into the narrative of state changes.

Despite not being part of the interface, constraints play a crucial role in defining the ADT. For instance, a stack and a queue share similar add and remove interfaces, but constraints distinguish last-in-first-out from first-in-first-out behavior. These constraints go beyond equations, encompassing logical formulas.

Importance of Constraints

Auxiliary Operations for Abstract Data Types (ADTs)

While conventional presentations of Abstract Data Types (ADTs) often focus on fundamental operations, a thorough understanding requires delving into auxiliary operations that enhance the versatility of ADTs.

Key Auxiliary Operations:

• create(): Initiates a new instance within the ADT;
• compare(s, t): Assesses the equivalence of states between two instances;
• hash(s): Computes a standard hash function based on the instance's state;
• print(s) or show(s): Generates a human-readable representation of the instance's state.

Additional Operations in Imperative-style ADT Definitions:

• initialize(s): Prepares a newly created instance s for subsequent operations or resets it to an "initial state";
• copy(s, t): Aligns the state of instance s with that of instance t;
• clone(t): Executes s ← create(), copy(s, t), and returns s;
• free(s) or destroy(s): Reclaims memory and other resources utilized by s.

The free operation, while seemingly irrelevant to ADTs as theoretical constructs without inherent memory usage, gains significance when analyzing the storage impact of algorithms using the ADT. In such cases, additional axioms become imperative to specify the memory footprint of each ADT instance relative to its state and to articulate the amount of memory returned to the pool by the free operation.

Presentations of ADTs are often focused on key operations. Thorough presentations specify auxiliary operations that enhance the versatility of ADTs:

Restricted Types

ADT definitions may restrict stored values to a specific set X called the range of those variables. For example, an abstract variable may be constrained to store only integers. These restrictions simplify algorithm descriptions and improve readability.

Aliasing

In the operational style, handling multiple instances and potential modifications across instances is unclear. Some ADT definitions assume a single instance, simplifying operations. However, ADTs can be extended to admit multiple instances with explicit parameters in each operation. Aliasing axioms ensure distinctness of instances and may exclude partial aliasing with other instances.

Multiple Instance Style

This style assumes that only one instance exists during the execution of the algorithm, and operations are applied to that instance. For example, a stack may have operations push(x) and pop() , operating on the only existing stack. This style can be extended to admit multiple coexisting instances by adding an explicit instance parameter to each operation.

Aliasing Axiom

The aliasing axiom asserts that the result of create() is distinct from any instance already in use by the algorithm. Implementations may reuse memory, allowing create() to yield a previously created instance. Defining such an instance as "reused" is challenging in the ADT formalism.

Generalized Aliasing Axiom

This strengthened axiom may exclude partial aliasing with other instances, assuming complete disjointness. For instance, operations on a field F of a record variable R involve F , distinct from but also part of R . A partial aliasing axiom would state that changing a field of one record variable does not affect any other records.

Abstract Data Types: Bridging Theory and Implementation

Abstract data types (ADTs) serve as theoretical constructs in computer science, streamlining the description of abstract algorithms, facilitating the classification and evaluation of data structures, and providing a formal description of programming language type systems. While ADTs exist in theory, they find practical implementation.

Practical implementation involves representing each ADT instance or state with a concrete data type or structure. For every abstract operation, a corresponding procedure or function is implemented, satisfying the ADT's specifications and axioms up to a defined standard. In practice, implementations are not perfect, and users must be aware of issues arising from representation and implemented procedures.

Example: Integers as an ADT

Consider integers specified as an ADT, defined by values like 0 and 1 and operations such as addition, subtraction, multiplication, division (with care for division by zero), and comparison. These operations adhere to familiar mathematical axioms. However, in a computer, integers are commonly represented as fixed-width 32-bit or 64-bit binary numbers, introducing concerns like arithmetic overflow.

Despite these representation challenges, users often ignore these intricacies for practical purposes and treat the implementation as if it were the abstract data type.

Flexibility in Implementation

Multiple implementations are possible for the same ADT, utilizing various concrete data structures. For instance, an abstract stack can be implemented using a linked list or an array. Different implementations with the same properties are considered semantically equivalent, offering interchangeability in code usage. This flexibility provides abstraction and encapsulation, allowing for increased efficiency in different scenarios.

Code written to interact with an ADT according to its interface remains robust, even with changes to the underlying implementation. This showcases the power of abstraction in creating adaptable and maintainable code.

Encapsulation through Opaque Data Types

To prevent clients from depending on the implementation details, ADTs are often packaged as opaque data types or handles within modules. The interface exposes only the signature of operations, concealing the concrete implementation. This encapsulation enables changes to the implementation without affecting clients. Exposing the implementation is termed a transparent data type.

Modern object-oriented languages like C++ and Java support ADTs through classes. An ADT is typically implemented as a class, with instances as objects of that class. The module's interface declares constructors as ordinary procedures and most other ADT operations as methods of that class. While this aligns with object-oriented principles, it may struggle to encapsulate multiple representational variants within an ADT and can potentially undermine the extensibility of object-oriented programs.

Built-in ADTs in Programming Languages

Some programming languages intentionally leave the representation of built-in data types vague, defining only permissible operations. These types can be viewed as "built-in ADTs." Examples include arrays in scripting languages like Awk, Lua, and Perl, which can be regarded as implementations of the abstract list.

Formal Specification and Axiomatic Definitions

In formal specification languages, ADTs can be defined axiomatically, allowing manipulation of ADT values within the language. The OBJ family of programming languages, for instance, allows defining equations for specification and rewriting to execute them. While convenient, automatic implementations defined in this manner may not always match the efficiency of dedicated implementations.

Collections in Computer Programming

Linear Collections

Lists

Stacks

Queues

Priority Queues

Double-ended Queues

Double-ended Priority Queues

Associative Collections

Sets

Multisets

Associative Arrays

Graphs

Trees

Abstract Concept vs. Implementation

Introduction to list

Implementation Structures

Operations

• Constructor for creating an empty list.
• Operation for testing whether a list is empty.
• Operation for prepending an entity to a list.
• Operation for appending an entity to a list.
• Operation for determining the first component (or the "head") of a list.
• Operation for referring to the list consisting of all components of a list except for its first (the "tail").
• Operation for accessing the element at a given index.

Implementations

Programming Language Support

Applications

• Storing a list of elements with dynamic expansion and contraction.
• Easier implementation than sets in computing.
• Forming the basis for other abstract data types, including queues, stacks, and their variations.

Abstract Definition

The abstract list type L with elements of some type E (a monomorphic list) is defined by the following functions:

• nil: () → L
• cons: E × L → L
• first: L → E
• rest: L → L

with the axioms:

• first(cons(e, l)) = e
• rest(cons(e, l)) = l

for any element e and any list l. It is implicit that:

• cons(e, l) ≠ l
• cons(e, l) ≠ e
• cons(e1, l1) = cons(e2, l2) if e₁ = e₂ and l₁ = l₂

Note that first(nil()) and rest(nil()) are not defined.

These axioms are equivalent to those of the abstract stack data type.

In type theory, the above definition is more simply regarded as an inductive type defined in terms of constructors: nil and cons. In algebraic terms, this can be represented as the transformation \(1 + E \times L \rightarrow L\). first and rest are then obtained by pattern matching on the cons constructor and separately handling the nil case.

The List Monad

The list type forms a monad with the following functions (using \(E^{*}\) rather than \(L\) to represent monomorphic lists with elements of type \(E\)):

• return: A → A^{*} = a → cons(a, nil)
• bind: A^{*} → (A → B^{*}) → B^{*} = l → f →
  nil if l = nil
append(f(a), bind(l', f)) if l = cons(a, l')

where append is defined as:

Alternatively, the monad may be defined in terms of operations return, fmap, and join, with:

• fmap: (A → B) → (A^{*} → B^{*}) = f → l →
  nil if l = nil
cons(f(a), fmap(f, l')) if l = cons(a, l')
• join: {A^{*}}^{*} → A^{*} = l →
  nil if l = nil
append(a, join(l')) if l = cons(a, l')

Note that fmap, join, append, and bind are well-defined, as they're applied to progressively deeper arguments at each recursive call.

The list type is an additive monad, with nil as the monadic zero and append as the monadic sum.

Lists form a monoid under the append operation. The identity element of the monoid is the empty list, nil. In fact, this is the free monoid over the set of list elements.

Advanced Operations

Programming Language Support

Applications

Abstract Definition and Monadic Structure

why list

Tuples in Mathematics and Computer Science

Definition and Notation

Properties

Definitions and Etymology

Tuples as Functions

Tuples as Sets of Ordered Pairs

Tuples as Nested Ordered Pairs

Tuples as Nested Sets

Conclusion

n-Tuples of m-Sets

In the realm of discrete mathematics, specifically within combinatorics and finite probability theory, n-tuples emerge as pivotal entities in diverse counting scenarios. Conceptually, they are treated as meticulously ordered lists of length n. When the elements of these n-tuples are drawn from a set of m elements, they are denoted as arrangements with repetition, permutations of a multiset, or, in some non-English literature, variations with repetition. The cardinality of the set of n-tuples derived from an m-set is represented as $m^n$, a direct consequence of the combinatorial rule of product. If $S$ stands as a finite set with a cardinality of m, then this cardinality aligns with that of the n-fold Cartesian power $S \times S \times \ldots \times S$. Tuples, in this context, serve as elements of this product set.

Type Theory

In the domain of type theory, widely employed in programming languages, a tuple is intricately linked with a product type. This association not only stipulates the length of the tuple but also explicitly specifies the underlying types of each component. Formally, given a tuple $(x_1, x_2, \ldots, x_n)$, its type is articulated as $x_1 : \mathsf{T}_1 \times x_2 : \mathsf{T}_2 \times \ldots \times x_n : \mathsf{T}_n$. The projections function as term constructors, where $\pi_1(x) : \mathsf{T}_1$, $\pi_2(x) : \mathsf{T}_2$, and so forth.

The notion of a tuple with labeled elements, as employed in the relational model, aligns with a record type in type theory. Both tuple and record types can be systematically defined as natural extensions of the simply typed lambda calculus.

The interplay between the concept of a tuple in type theory and set theory is evident. Considering the natural model of type theory, using Scott brackets for semantic interpretation, the model comprises sets $S_1, S_2, \ldots, S_n$ such that $[\![\mathsf{T}_1]\!] = S_1, [\![\mathsf{T}_2]\!] = S_2, \ldots, [\![\mathsf{T}_n]\!] = S_n$. The interpretation of basic terms aligns accordingly, with $[\![x_1]\!] \in [\![\mathsf{T}_1]\!]$, $[\![x_2]\!] \in [\![\mathsf{T}_2]\!]$, and so on.

The n-tuple in type theory seamlessly corresponds to its counterpart in set theory. Notably, the unit type in type theory aligns with the 0-tuple in set theory.

Advanced Topics in Tuples and Type Theory

Higher-Order Tuples

Tuple Spaces in Quantum Computing

Tuple Calculus in Database Theory

Dependent Types and Tuple-Dependent Functions

Tuple Fusion in Multilinear Algebra

Conclusion

assosiative array

• Insert or Put: Adding a new (key, value) pair to the collection, overwriting any existing mapping. The arguments for this operation are the key and the value.
• Remove or Delete: Eliminating a (key, value) pair from the collection, dissociating a given key from its value. The argument for this operation is the key.
• Lookup, Find, or Get: Locating the value bound to a given key. The argument for this operation is the key, and the value is returned. If no value is found, some lookup functions raise an exception, while others return a default value.

The associative array is realized using a structure that supports efficient key-based retrieval. In this implementation, a combination of arrays and linked lists is employed. Each key-value pair is stored in a node, and these nodes are organized into buckets based on a hash function applied to the keys. This enables quick access to the desired pair.

Operations

Insertion

When inserting a new key-value pair, the hash function determines the appropriate bucket. If the bucket is empty, a new node is created for the pair. If the bucket already contains nodes, a linked list is traversed to ensure no existing key matches the new one. If a match is found, the value is updated; otherwise, a new node is appended to the linked list.

Retrieval

Retrieving a value associated with a key involves hashing the key to locate the corresponding bucket. If the bucket is non-empty, the linked list within is searched for the specified key. If found, the associated value is returned; otherwise, an indication of absence is returned.

Deletion

Deleting a key-value pair entails locating the bucket using the hash function. If the bucket is not empty, the linked list is traversed to find and remove the specified key-value pair. If the key is not present, the data structure remains unchanged.

Collision Handling

Collisions, where distinct keys hash to the same bucket, are managed by employing a linked list for each bucket. This allows multiple key-value pairs to coexist within the same bucket, providing a mechanism to handle collisions gracefully.

Mathematical Representation

The mathematical representation involves defining the hash function and the data structure operations formally. Let $H(k)$ be the hash function for key $k$, mapping it to a bucket index. The insertion operation can be expressed as:

The retrieval and deletion operations follow a similar structure, involving the computation of the hash index and subsequent actions based on the state of the corresponding bucket.

Multimaps: Advanced Concepts in Associative Arrays

Set Operations in Computer Science

In computer science, a set is an abstract data type designed to store unique values without any specified order. It serves as a computational implementation of the mathematical concept of a finite set. Unlike many other collection types, which focus on retrieving specific elements, sets primarily facilitate membership tests, determining whether a given value belongs to the set.

Type Theory

In type theory, sets are often equated with their indicator function or characteristic function. A set of values of type $A$ may be denoted by $2^A$ or $\mathcal{P}(A)$. Subtypes and subsets may be modeled by refinement types, and quotient sets may be replaced by setoids. The characteristic function $F$ of a set $S$ is defined as:

In theory, many other abstract data structures can be viewed as set structures with additional operations and/or additional axioms imposed on the standard operations. For example, an abstract heap can be viewed as a set structure with a $\text{min}(S)$ operation that returns the element of smallest value.

Core Set-Theoretical Operations

1. union($S, T$): Returns the union of sets $S$ and $T$.
2. intersection($S, T$): Returns the intersection of sets $S$ and $T$.
3. difference($S, T$): Returns the difference of sets $S$ and $T$.
4. subset($S, T$): A predicate that tests whether the set $S$ is a subset of set $T$.

Static Sets

1. is_element_of($x, S$): Checks whether the value $x$ is in the set $S$.
2. is_empty($S$): Checks whether the set $S$ is empty.
3. size($S$) or cardinality($S$): Returns the number of elements in $S$.
4. iterate($S$): Returns a function that returns one more value of $S$ at each call, in some arbitrary order.
5. enumerate($S$): Returns a list containing the elements of $S$ in some arbitrary order.
6. build($x_1, x_2, \ldots, x_n$): Creates a set structure with values $x_1, x_2, \ldots, x_n$.
7. create_from($collection$): Creates a new set structure containing all the elements of the given collection or all the elements returned by the given iterator.

Dynamic Sets

Dynamic set structures typically add:

1. create(): Creates a new, initially empty set structure.
2. create_with_capacity($n$): Creates a new set structure, initially empty but capable of holding up to $n$ elements.
3. add($S, x$): Adds the element $x$ to $S$, if it is not present already.
4. remove($S, x$): Removes the element $x$ from $S$, if it is present.
5. capacity($S$): Returns the maximum number of values that $S$ can hold.

Additional Operations

There are many other operations that can (in principle) be defined in terms of the above, such as:

1. pop($S$): Returns an arbitrary element of $S$, deleting it from $S$.
2. pick($S$): Returns an arbitrary element of $S$. Functionally, the mutator pop can be interpreted as the pair of selectors (pick, rest), where rest returns the set consisting of all elements except for the arbitrary element. Can be interpreted in terms of iterate.
3. map($F, S$): Returns the set of distinct values resulting from applying function $F$ to each element of $S$.
4. filter($P, S$): Returns the subset containing all elements of $S$ that satisfy a given predicate $P$.
5. fold($A_0, F, S$): Returns the value $A|S|$ after applying $A_{i+1} := F(A_i, e)$ for each element $e$ of $S$, for some binary operation $F$. $F$ must be associative and commutative for this to be well-defined.
6. clear($S$): Delete all elements of $S$.
7. equal($S1', S2'$): Checks whether the two given sets are equal (i.e., contain all and only the same elements).
8. hash($S$): Returns a hash value for the static set $S$ such that if equal($S1, S2$) then hash($S1$) = hash($S2$).

Other Operations

Other operations can be defined for sets with elements of a special type:

1. sum($S$): Returns the sum of all elements of $S$ for some definition of "sum". For example, over integers or reals, it may be defined as fold($0, add, S$).
2. collapse($S$): Given a set of sets, return the union. For example, collapse({{1}, {2, 3}}) == {1, 2, 3}. May be considered a kind of sum.
3. flatten($S$): Given a set consisting of sets and atomic elements (elements that are not sets), returns a set whose elements are the atomic elements of the original top-level set or elements of the sets it contains. In other words, remove a level of nesting – like collapse, but allow atoms. This can be done a single time or recursively flattening to obtain a set of only atomic elements. For example, flatten({1, {2, 3}}) == {1, 2, 3}.
4. nearest($S, x$): Returns the element of $S$ that is closest in value to $x$ (by some metric).
5. min($S$), max($S$): Returns the minimum/maximum element of $S$.

Multiset

A multiset, also known as a bag, is a generalization of the concept of a set, allowing for the presence of duplicate values. There are two interpretations: treating equal values as identical and counting them, or considering equal values as equivalent but distinct items. In computer science, objects can be deemed equal under one equivalence relation and distinct under another.

Formally, a multiset can be interpreted as a function from the input domain to non-negative integers, extending the concept of a set with its indicator function. Multisets can be implemented using hash tables or trees, each with different performance characteristics.

The set of all bags over type T is denoted as bag T. Some implementations store distinct equal objects separately, while others collapse them and maintain a count of their multiplicity.

• C++'s Standard Template Library supports both sorted and unsorted multisets.

In situations without a dedicated multiset data structure, one can use a regular set with an overridden equality predicate or an associative array mapping values to their integer multiplicities. However, the latter cannot distinguish between equal elements.

Typical Operations

• contains(B, x): checks whether the element x is present (at least once) in the bag B.
• is_sub_bag(B₁, B₂): checks whether each element in the bag B₁ occurs in B₂ no more often than it occurs in B₁.
• count(B, x): returns the number of times that the element x occurs in the bag B.
• scaled_by(B, n): given a natural number n, returns a bag that contains the same elements as the bag B, except that every element occurring m times in B occurs n \times m times in the resulting bag.
• union(B₁, B₂): returns a bag containing values that occur in either the bag B₁ or the bag B₂.

The Abstract Data Type: Stack

The concept of a stack in computer science is a fundamental abstraction that plays a pivotal role in various algorithms and data structures. Let us delve into the intricacies of this abstract data type, exploring its underlying principles, operations, and applications.

A stack is defined as an ordered collection of elements where the primary operations are Push and Pop. The Push operation adds an element to the collection, while the Pop operation removes the most recently added element. Additionally, a Peek operation allows us to observe the top element without modifying the stack.

Mathematically, a stack adheres to the Last-In-First-Out (LIFO) principle, where the last element added is the first to be removed. This ordering principle is analogous to a stack of physical objects, such as plates, where items are placed and retrieved from the top.

Let's formalize the operations:

Push Operation:

If S is a stack and x is an element to be pushed onto S , the Push operation can be defined as:

where S' is the updated stack after the push operation.

Pop Operation:

If S is a non-empty stack, the Pop operation can be expressed as:

where x is the element removed, and S' is the updated stack.

Peek Operation:

The Peek operation returns the top element without modifying the stack:

The Underlying Structure of a Stack

Now, let's consider the underlying structure of a stack. A stack is inherently a linear data structure with two ends: the top, where push and pop operations occur, and the fixed bottom. This structure aligns with the implementation of a stack using a singly linked list or a pointer to the top element. The fixed bottom ensures the stability of the stack's structure.

Moreover, a stack can be designed with a bounded capacity. In cases of a full stack where there is insufficient space for another element, a stack overflow occurs, representing a crucial aspect of stack management.

Beyond its abstract definition, a stack finds practical application in algorithms like depth-first search, where the LIFO nature of a stack facilitates an elegant and efficient exploration of paths in a graph.

In conclusion, the stack, with its well-defined operations and mathematical foundation, stands as a cornerstone in computer science, enabling elegant solutions in various algorithmic contexts. The formalization provided here, accompanied by precise mathematical expressions, aligns with the preference for a scholarly and detailed exploration of the topic.

Additional Stack Operations and Implementations

In many implementations, a stack encompasses operations beyond the essential "push" and "pop." An example is the "top of stack" or "peek" operation, which observes the top element without removing it. Although this can be decomposed into a "pop" followed by a "push" to return the same data, it is considered non-essential. Executing "stack top" or "pop" on an empty stack leads to an underflow condition. Additionally, implementations often include a check for an empty stack and an operation returning its size.

Software Stacks

Array Implementation

A stack can be implemented using an array, allowing only "pop" and "push" operations. Below is a detailed pseudocode for this implementation:

        
            structure stack:
                maxsize : integer
                top : integer
                items : array of item
            
            Procedure initialize(stk : stack, size : integer)
                stk.items = new array of size items, initially empty
                stk.maxsize = size
                stk.top = 0
            
            
            Procedure push(stk : stack, x : item)
                If (stk.top = stk.maxsize)
                    report overflow error
                Else
                    stk.items[stk.top] = x
                    stk.top = stk.top + 1
                EndIf
            
            
            Procedure pop(stk : stack)
                If (stk.top = 0)
                    report underflow error
                Else
                    stk.top = stk.top - 1
                    r = stk.items[stk.top]
                    return r
                EndIf
            
        

Linked List Implementation

An alternative is implementing stacks using a singly linked list. The stack is represented as a pointer to the "head" of the list, possibly with a counter for the size:

        
            structure frame:
                data : item
                next : frame or nil
            
            structure stack:
                head : frame or nil
                size : integer
            
            Procedure initialize(stk : stack)
                stk.head = nil
                stk.size = 0
            
            
            Procedure push(stk : stack, x : item)
                newhead = new frame
                newhead.data = x
                newhead.next = stk.head
                stk.head = newhead
                stk.size = stk.size + 1
            
            
            Procedure pop(stk : stack)
                If (stk.head = nil)
                    report underflow error
                Else
                    r = stk.head.data
                    stk.head = stk.head.next
                    stk.size = stk.size - 1
                    return r
                EndIf
            
        

Essential Stack Operations

Push Operation

The core operation of a stack, Push, involves adding an element to the collection. Mathematically, if \(S\) is a stack and \(x\) is an element, the push operation can be expressed as:

where \(S'\) is the updated stack after the push operation.

To formalize the push operation, we introduce the following pseudocode:

        
            Procedure Push(S : stack, x : item)
                If \(S.\text{top} = S.\text{maxsize}\)
                    report overflow error
                Else
                    \(S.\text{items}[S.\text{top}] \gets x\)
                    \(S.\text{top} \gets S.\text{top} + 1\)
                EndIf
            EndProcedure
        
    

The time complexity of the push operation is \(O(1)\), assuming constant-time arithmetic operations.

Pop Operation

The Pop operation removes the most recently added element from the stack. If \(S\) is a non-empty stack, the pop operation can be expressed as:

where \(x\) is the element removed, and \(S'\) is the updated stack.

The formalization of the pop operation is presented through the following pseudocode:

        
            Procedure Pop(S : stack)
                If \(S.\text{top} = 0\)
                    report underflow error
                Else
                    \(S.\text{top} \gets S.\text{top} - 1\)
                    \(r \gets S.\text{items}[S.\text{top}]\)
                    return \(r\)
                EndIf
            EndProcedure
        
    

Similar to the push operation, the time complexity of the pop operation is \(O(1)\) under the assumption of constant-time arithmetic operations.

Peek Operation

The Peek operation allows observing the top element without modifying the stack. Mathematically, for a stack \(S\), the peek operation is expressed as:

The implementation of the peek operation is straightforward:

        
            Function Peek(S : stack)
                return \(S.\text{items}[S.\text{top} - 1]\)
            EndFunction
        
    

The time complexity of the peek operation is \(O(1)\), as it involves simple array access.

Stack Pointer and Memory Management

Stack Growth and Memory Limits

Additional Stack Operations

Duplicate Operation

Peek Operation

Swap or Exchange Operation

Rotate Operation

Memory Representation of Stacks

Push and Pop Operations

Stack in Main Memory

Stack in Registers or Dedicated Memory

Register Windows and Specialized Architectures

Conclusion

Expression Evaluation and Syntax Parsing

Backtracking

Compile-Time Memory Management

Algorithms Utilizing Stacks

Graham Scan

SMAWK Algorithm

All Nearest Smaller Values

Nearest-Neighbor Chain Algorithm

Security Considerations in Stack Usage

Shared Stack for Data and Procedure Calls

Stack Smashing Attacks

Buffer Overflow and Compiler Practices

Queues in Computer Science

Queue Operations

Linear Data Structure and Implementations

Queue Services and Applications

Queue Implementation Strategies

Queues in Programming Languages

Purely Functional Implementation of Queues

Amortized Queue

Real-time Queue

Priority Queue in Computer Science

Conceptual Distinction from Heaps

Basic Operations

• is\_empty: Check whether the queue has no elements.
• insert\_with\_priority: Add an element to the queue with an associated priority.
• pull\_highest\_priority\_element: Remove and return the element with the highest priority. Also known as pop\_element(Off), get\_maximum\_element, or get\_front(most)\_element.

Advanced Operations

Relation to Stacks and Queues

Usual Implementation of Priority Queues

Specialized Heaps

• Bucket Queue: Suitable when insert, find-min, and extract-min operations are required. Utilizes an array of $C$ linked lists with a pointer top. Inserting an item with key $k$ appends it to the $k$-th list, and updates top in constant time. Extract-min deletes and returns an item from the list with index top, incrementing top if needed, taking $O(C)$ time in the worst case. Useful for sorting graph vertices by their degree.
• van Emde Boas Tree: Supports various operations in $O(\log \log C)$ time, including minimum, maximum, insert, delete, search, extract-min, extract-max, predecessor, and successor. However, it incurs a space cost of about $O(2^{m/2})$ for small queues, where $m$ is the number of bits in the priority value. Space can be reduced with hashing.
• Fusion Tree: Proposed by Fredman and Willard, it achieves $O(1)$ time for the minimum operation and $O(\frac{\log n}{\log \log C})$ time for insert and extract-min operations. Practicality is limited due to high constant factors in execution times.
• Caching for Peek Operations: For applications with frequent peek operations, caching the highest-priority element after each insertion and removal can reduce peek time complexity to $O(1)$ in all tree and heap implementations. The constant cost for insertion is minimal, and for deletion, the additional "peek" cost does not significantly impact overall time complexity.

Monotone Priority Queues

Applications of Priority Queues

Bandwidth Management

Discrete Event Simulation

Dijkstra's Algorithm

Huffman Coding

Best-First Search Algorithms

ROAM Triangulation Algorithm

Prim's Algorithm for Minimum Spanning Tree

Parallel Priority Queue

Concurrent Parallel Access in Priority Queues

Implementation with Skip List on CRCW PRAM Model

• insert(e): Create a new node with key and priority, determine the number of levels, and perform a search to find the insertion position. Update pointers to incorporate the new node at each level.
• extract-min: Traverse the skip list until a node with an unset delete mark is found. Set the delete mark for that node and update pointers of parent nodes.

K-Element Operations

Distributed Memory Implementation

Double-Ended Queue (Deque) in Computer Science

Naming Conventions

Distinctions and Sub-Types

• An input-restricted deque allows deletion from both ends but insertion at one end only.
• An output-restricted deque permits insertion at both ends but deletion from one end only.

Implementations

Dynamic Array Approach (Array Deques)

Purely Functional Implementation

Complexity

Applications

• Managing browsing history: Deques can store the browsing history, adding new websites to the end and removing the oldest entries when the history becomes too large.
• Work stealing algorithm: Used in parallel programming for task scheduling across multiple processors.

Efficient Representation of Adjacency Sets

Graphs in Computer Science

Operations

• adjacent(G, x, y)
Tests whether there is an edge from vertex x to vertex y.
• neighbors(G, x)
Lists all vertices y such that there is an edge from vertex x to vertex y.
• add\_vertex(G, x)
Adds vertex x if it is not already present.
• remove\_vertex(G, x)
Removes vertex x if it exists.
• add\_edge(G, x, y, z)
Adds the edge z from vertex x to vertex y if it is not already present.
• remove\_edge(G, x, y)
Removes the edge from vertex x to vertex y if it exists.
• get\_vertex\_value(G, x)
Returns the value associated with vertex x.
• set\_vertex\_value(G, x, v)
Sets the value associated with vertex x to v.

• get\_edge\_value(G, x, y)
Returns the value associated with the edge (x, y).
• set\_edge\_value(G, x, y, v)
Sets the value associated with the edge (x, y) to v.

Common Data Structures for Graph Representation

Adjacency List

Adjacency Matrix

Incidence Matrix

Parallel Representations

Shared Memory

Distributed Memory

• 1D Partitioning: Each processor receives n/p vertices and corresponding outgoing edges. This can be visualized as a row-wise or column-wise decomposition of the adjacency matrix, requiring an All-to-All communication step and \mathcal{O}(m) message buffer sizes.
• 2D Partitioning: Processors are aligned in a p_r \times p_c rectangle, each getting a submatrix of the adjacency matrix. This results in a checkerboard pattern, limiting communication partners for each PE to p_r + p_c - 1 out of p = p_r \times p_c possible ones.

Compressed Representations

        
          ```js
function calculateStackAddresses(n, Poo, P0) {
  let nPrime = Math.ceil((n / 2) * 2) / 2;

  let BASE = [];
  let TOP = [];
  let OLDTOP = [];

  for (let i = 1; i <= nPrime; i++) {
    let baseOdd = Math.floor((i - 1) * (Poo - P0) / nPrime) + P0;
    BASE[2 * i - 1] = baseOdd;
    TOP[2 * i - 1] = baseOdd;
    OLDTOP[2 * i - 1] = baseOdd;

    let baseEven = Math.floor(i * (Poo - P0) / nPrime) + P0 + 1;
    BASE[2 * i] = baseEven;
    TOP[2 * i] = baseEven;
    OLDTOP[2 * i] = baseEven;
  }

  return { BASE, TOP, OLDTOP };
}

// Example usage:
const n = 8;
const Poo = 100;
const P0 = 10;

const { BASE, TOP, OLDTOP } = calculateStackAddresses(n, Poo, P0);

console.log("BASE:", BASE);
console.log("TOP:", TOP);
console.log("OLDTOP:", OLDTOP);


function push(stackIndex, item, BASE, TOP, CONTENTS) {
    if (stackIndex % 2 !== 0) {
        TOP[stackIndex]++;
        if (TOP[stackIndex] > TOP[stackIndex + 1]) {
            overflow(stackIndex);
            return;
        }
    } else {
        TOP[stackIndex]--;
        if (TOP[stackIndex] < TOP[stackIndex - 1]) {
            overflow(stackIndex);
            return;
        }
    }

    CONTENTS[TOP[stackIndex]] = item;
}

function pop(stackIndex, BASE, TOP, CONTENTS) {
  if (TOP[stackIndex] =BASE[stackIndex] ) {
    underflow(stackIndex);
  } else {
    let item = CONTENTS[TOP[stackIndex]];

    if (stackIndex % 2 !== 0) {
      TOP[stackIndex] = TOP[stackIndex] - 1;
    } else {
      TOP[stackIndex] = TOP[stackIndex] + 1;
    }

    return item;
  }
}

function underflow(stackIndex) {
  console.log(`Underflow in stack ${stackIndex}`);
  // Handle underflow as needed
}

// Example usage:
const BASE = [/* Populate with base addresses for each stack */];
const TOP = [/* Populate with top addresses for each stack */];
const CONTENTS = [/* Populate with initial contents of each stack */];

const stackIndex = 1; // Replace with the desired stack index

const poppedItem = pop(stackIndex, BASE, TOP, CONTENTS);
console.log("Popped Item:", poppedItem);


function Overflow(i) {
  let Sum = Poo - P0; // Sum equal to the total amount of memory space left
  let Inc = 0; // Inc equal to the total amount of increases in stack size since the last allocation
  let D = [];
  for (let j = 1; j <= n; j++) {
    if (j % 2 !== 0) {
      Sum = Sum- TOP[j] - BASE[j];
      if (TOP[j] > OLDTOP[j]) {
         D[j] = TOP[j] - OLDTOP[j];
        Inc = Inc+ D[j];
      } else {
         D[j] = 0;
      }
    } else {
      Sum = Sum - TOP[j] - BASE[j];
      if (TOP[j] < OLDTOP[j]) {
         D[j] = OLDTOP[j] - TOP[j];
        Inc = Inc+ D[j];
      } else {
         D[j] = 0;
      }
    }
  }

  if (Sum < 0) {
    Systemfail();
  }

  let Ave = a * Math.floor(Sum/nprime);
  let Weight = b*Math.floor(Sum/Inc);

  let NEWBASE = [];
  NEWBASE[1] = BASE[1];
  NEWBASE[2 * nprime] = BASE[2 * nprime];
  let sigma = 0;

  for (let j = 1; j <= nprime - 1; j++) {
    let r = sigma + D[j - 1] * Weight + Ave;
    NEWBASE[2 * j] = NEWBASE[2 * j - 1] + (TOP[2 * j - 1] - BASE[2 * j - 1]) + r - floor(sigma) + (TOP[2 * j] - BASE[2 * j]) + 1;
    NEWBASE[2 * j + 1] = NEWBASE[2 * j] - 1;
    sigma = r;
  }

  if (i % 2 !== 0) {
    TOP[i] = TOP[i] - 1;
  } else {
    TOP[i] = TOP[i] + 1;
  }

  Repack();

  if (i % 2 !== 0) {
    TOP[i] = TOP[1] + 1;
  } else {
    TOP[i] = TOP[i] - 1;
  }

  for (let j = 1; j <= n; j++) {
    OLDTOP[j] = TOP[j];
  }
}

function Repack() {
  let j = 1;
  while (j <= n) {
    if (NEWBASE[j] < BASE[j]) {
      let delta = BASE[j] - NEWBASE[j];
      if (j % 2 !== 0) {
        for (let p = BASE[j] + 1; p <= TOP[j]; p++) {
          CONTENTS[p - delta] = CONTENTS[p];
        }
      } else {
        for (let p = TOP[j]; p >= BASE[j] - 1; p--) {
          CONTENTS[p - delta] = CONTENTS[p];
        }
      }
      BASE[j] = NEWBASE[j];
      TOP[j] = TOP[j] - delta;
    }
    j++;
  }

  while (j !== 1) {
    if (NEWBASE[j] > BASE[j]) {
      let delta = NEWBASE[j] - BASE[j];
      if (j % 2 !== 0) {
        for (let p = TOP[j]; p >= BASE[j] + 1; p--) {
          CONTENTS[p + delta] = CONTENTS[p];
        }
      } else {
        for (let p = BASE[j] - 1; p >= TOP[j]; p--) {
          CONTENTS[p + delta] = CONTENTS[p];
        }
      }
      BASE[j] = NEWBASE[j];
      TOP[j] = TOP[j] + delta;
    }
    j--;
  }
}

function Systemfail() {
  console.log("System failure due to lack of available space.");
}

// Example usage:
const n = 8;
const Poo = 100;
const P0 = 10;
const a = 1; // Replace with the actual value of 'a'

const BASE = []; // Populate with base addresses for each stack
const TOP = []; // Populate with top addresses for each stack
const CONTENTS = []; // Populate with initial contents of each stack
const OLDTOP = []; // Populate with old top addresses for each stack

const stackIndex = 1; // Replace with the desired stack index
Overflow(stackIndex);
```