Welcome to dylanserver.xyz

Data Structures and Algorithms


Stacks
  • Last in First out
  • Only top item is accessible
  • Undo, recursion, matching brackets
  • Push(add to top), Pop(get top), peek(see top), (is)empty, (is)full
  • ADT
  • Fixed bottom
  • Pointer value for top
  • Big O
  • Pop O(1) Push O(1) Peek O(1)
Queue
  • Last in last out
  • Only front item accessible
  • Enqueue(add back), Dequeue(take front), (see)first,(is)empty,(is)full
  • Big O
  • En O(1) De(static head) O(n) De(Dynamic head) O(1)

    • Assessment

    • 25% CBT (5 short, 20 multi)
    • 75% Exam
    • Weekly formative quizzes on moodle

    Data Structure
    • Collection of elements
    • et of associations or relationships

    Abstract data type
    • Input and output data and query object
    • Do not care what happens inside
    • Cannot directly access the data inside
    • Uses getters and setters

    ADT vs DS
    • High level decodeion vs concrete decodeion
    • Focus on what is can do vs focus on how it manages it
    • Independent implementation vs dependant implementation

    Linear
    • Unique predecessor and unique successor
    • Lists, queues stacks

    Hierarchical
    • Unique predecessor and many successors
    • Trees

    Graphs
    • Many predecessors and many successors
    • Mesh, web, network

    Set structure
    • No order hence no predecessors and no successors
    • Group of people

    Choosing DS
    • Analyse the problem
    • Determine the basic operations
    • Pick the data structure

    Stacks and Queues

    Data Structures:

    A programatic way of storing data so that it can be used efficently by the program

    Abastract Data Type:

    A Mathmatical model for a data types (Stack, Queue, Graph) (An Application that uses an ADT is not concerned how the data is stored, and the abstract data type is not concerned how the application uses it.)
    Stacks
    Like an array, but data that is sent to the array gets added to the end, and you can only acess the last element in the array (first in, last out) Works like a pile of dirty dishes, most recent gets cleaned first.
    Queue
    Like an array, but data that is sent to the array gets added to the end, and you can only acess the first element in the array (first in, first out) This works like a queue in normal life (eg, at a cafe)