Quartz 5

02 Data Structure

10 min read

Data Structure

Collections

Definition

  • A collection is a group of items that are treated as a conceptual unit
  • Collections can be homogeneous, meaning all items must be of the same type, or heterogeneous, meaning items can be of different types

Types of Collections

Linear Collections
  • Items are ordered by position
  • Examples include grocery lists, stacks of dinner plates, or a queue of customers
  • Stacks and queues are examples of linear collections
Hierarchical Collections
  • These structures resemble an upside-down tree
  • Examples include file directory systems or a company’s organisational tree
  • D3’s parent is D1, and its children are D4, D5, and D6 in such a structure
  • Binary trees are a type of hierarchical collection
Graph Collections
  • Each data item can have many predecessors and many successors
  • D3’s neighbours would be its predecessors and successors
  • Examples include maps of airline routes between cities
Unordered Collections
  • Items are not in any particular order
  • This means that an item’s predecessor or successor does not exist
  • An example is a bag of marbles.

Operations on Collections

  • Traversal: Visiting each item in a collection.
  • Search and retrieval: Finding a given target item or an item at a specific position.
  • Insertion: Adding an item to a collection at a given position.
  • Removal: Deleting a given item or the item at a given position.
  • Size Determination: Finding the number of items a collection contains.

Array

Definition

  • An array represents a sequence of items of the same data type
  • Items can be accessed, retrieved, stored, or **replaced **at given index positions

Data Structure

Random Access

  • Arrays support random access, meaning any item can be accessed directly using its index, because **data **is stored in contiguous memory
  • The **address **of an item is calculated as base address + (index * k), where k is the memory cells per item
Static Memory
  • Arrays are static, meaning their capacity or length is determined at compile time, requiring you to specify the size with a constant
Physical and Logical Size

  • You must track both the physical size (total number of cells) and the logical size (number of items currently in it)
  • This is to avoid reading “garbage” data
    • If the logical size is 0, the array is empty
    • The **index of the last item **is logical size - 1
    • If logical size equals physical size, there is no more room for data

Operations on Arrays

Insertion
  • **Check **for available space before attempting an insertion
  • Shift items from logical end of array to target index position down by one
  • To open “hole” for new item at target index
  • Assign new item to target index position
  • Increment logical size by one
Removal

  • Shift items from **next target position **to the logical end of the array up by one
  • To close “hole” left by removed item at target index
  • Decrement logical size by one

Linked List

Definition

  • Linked lists are concrete linear data types used to implement various collections
  • A key characteristic of linked structures is that they decouple the logical sequence of items from any ordering in memory
  • This means that they use a dynamic memory representation scheme

Data Structure

Node

  • This is done through the use of a node, of which stores data and a pointer
  • There is also the head, where it is a pointer referencing the first node or a null pointer

Operations on Linked Structures

Traversal

  • In order to visit each node without deleting it, we can use a temporary pointer variable which traverses the linked list
  • Stops the process when the current node points to a null pointer
Searching
  • Resembles a traversal, but two possible stopping conditions:
    • Data is not present
    • Node data that equals the target item
Replacement
  • Replacement operations employ traversal pattern
    • If the target item is not present, no replacement occurs
    • If the target is present, the new item replaces it
Insertion

  • To add a given item or the item at a given position, traverse the list to find the position
  • There are two cases to consider:
Insert at front: Updates the head pointer
Insert at position i: Updates the pointer of the (i - 1)th node
Deletion

  • To remove a given item or the item at a given position, traverse the list to search for the node to be deleted
  • As in insertion, must consider two cases:
Delete at front: Updates the head pointer
Delete at position i: Updates the pointer of the (i - 1)th node

Array Representation

Free Space List


Stack

  • LIFO (last-in-first-out) structure which is completely restricted to the top
  • It has two basic operations: **push **and pop

Common Problems

Bracket Expressions
  • Compilers need to determine if the brackets in expressions are balanced
Determining the balance of bracket expression
  • Iterate through the expression
  • If the character is an opening bracket, push a closing bracket of the same type onto the stack
If the character is a closing bracket, peek the top of the stack:
  • If stack is empty, expression is invalid
  • If top of stack is not the same closing bracket, expression is invalid
  • If the end of the expression is reached, stack should be empty, otherwise expression is invalid
Code
#include <iostream>
#include <stack>
#include <string>
 
bool bracketex(std::string expr){
    std::stack<char> st;
    for (int i = 0; i < expr.length(); i++){
	  if (expr[i] == '(') 
            st.push(')');
        else if (expr[i] == '[') 
            st.push(']');
	  else if (expr[i] == '{') 
            st.push('}');
        else if (st.empty() || st.top() != expr[i]) 
            return 0;
        else 
            st.pop();
    }
    return 1;
}
Arithmetic Expression
  • An arithmetic expression can be represented by two forms:
    • Infix form: Each operator is located **between **its operands. e.g. A + B
    • Postfix form: An operator immediately follows its operands. e.g. A B +
  • Operands appear in the same order, but operators do not in both forms
  • Infix forms might require parentheses, but the postfix form never does
  • Infix evaluation involves rules of precedence, but the postfix evaluation applies to operators as soon as they are encountered
Converting Infix to Postfix

  • Start with an empty postfix expression and an empty stack, the stack will hold operators and left parentheses
  • Iterate through infix expression from left to right
  • On encountering an operand, append it to postfix expression
  • On encountering a ‘(‘, push it onto the stack
  • On encountering an operator
    • Pop off the stack all operators with equal or higher precedence
    • Append them to postfix expression
    • Push scanned operator onto stack
  • On encountering a ‘)’
    • Pop operators from stack and add to postfix expression
    • Stop when meeting matching ‘(‘, which is discarded
  • On encountering the end of the infix expression, pop remaining operators from the stack to the postfix expression
Code
#include <iostream>
#include <stack>
#include <string>
#include <cctype>
 
int prec(char op) {
    if (op == '*' || op == '/') return 2;
    if (op == '+' || op == '-') return 1;
    return 0;
}
 
std::string inf_to_post(std::string expr){
    std::stack<char> st;
    std::string new_expr; 
    for (int i = 0; i < expr.length(); i++){
        if (expr[i] == ' ') continue;
        else if (isdigit(expr[i]))
            new_expr = new_expr + expr[i] + ' ';
        else if (expr[i] == '(') st.push('(');
        else if (expr[i] == ')'){
            while (!st.empty() && st.top() != '('){
                auto tmp = st.top();
                st.pop();
                new_expr += tmp + ' ';
            }
            st.pop();
        }
        else {
            while (!st.empty() && prec(st.top()) >= prec(expr[i])){
                auto tmp = st.top();
                st.pop();
                new_expr += tmp + ' ';
            }
            st.push(expr[i]);
        }
    }
    while (!st.empty()){
        auto tmp = st.top
        st.pop();
        new_expr += tmp + ' ';
    }
    return new_expr;	
}
Evaluating Postfix Expression
  • Scan across the postfix expression from left to right
  • On encountering an operand, push it onto the stack
  • On encountering an operator
    • Pop the top two operands
    • Apply the operator to the operands
    • Push the result onto the stack
  • Continue scanning until you reach expression’s end
Code

Only works for single digits

float eval_postfix(std::string expr){
    std::stack<float> st;
    
    for (int i = 0; i < expr.length(); i++){
        if (expr[i] == ' ') continue;
        else if (isdigit(expr[i])) st.push(expr[i]-'0');
        else {
            float a = st.top(); st.pop();
            float b = st.top(); st.pop();
            
            float res;
            char op = expr[i];
            
            switch (op){
                case '+': res = b + a; break;
                case '-': res = b - a; break;
                case '*': res = b * a; break;
                case '/': res = b / a; break;
            }
            
            st.push(res);
        }
    }
    
    float final_res = st.top();
    st.pop();
    
    return final_res;
}

Memory Management

Function Call

The run-time system must keep track of various details:

  • Associating variables with data objects stored in memory so they can be referenced
  • Remembering the return address of the instruction where function is called to carry on to the next instruction after finishing execution
  • Allocating memory for a function’s arguments and temporary variables, which exist only during the execution of that function
Stack Frame

  • Whenever a subroutine is called, a stack frame is created to store the current environment for that function.
  • This includes: parameters, temporary variables, return address and return value
What data structure should be used to store stack frames?
  • Problem:
Function A can call Function B
Function B can call Function C
  • When a function calls another function, it interrupts its own execution and needs to be able to resume its execution in the same state it was in when it was interrupted
    • When Function C finishes, control should return to Function B
    • When Function B finishes, control should return to Function A
  • Order of returns from a function is the reverse of function invocations (LIFO)
  • Use a stack to store the activation records, which is called the run-time stack.
What happens when a function is called?
  1. Push a copy of its activation record onto the run-time stack
  2. Copy its arguments into the parameter spaces
  3. Transfer control to the starting address of the body of the function
  • Top stack frame in the run-time stack is always the function currently being executed
What happens when a function terminates?
  1. Pop the stack frame of terminated function from the run-time stack
  2. Use new top stack frame to restore the environment of the interrupted function and resume execution of the interrupted function

Queue

  • FIFO (first-in-first-out) structure
  • **Insertions **are restricted to the rear
  • **Removals **are restricted to the front
  • It has two basic operations: **enqueue **and dequeue

Common Array Implementations

Method 1
Idea
  • Fixes variable **front **at position 0
  • Variable **rear **points to last item at position n-1
Evaluation
  • Efficient enqueue operation: All items just placed at position n
  • Inefficient dequeue operation: All items must be shifted to the left
Method 2
Idea
  • Maintain a second variable **front **that points to item at front of queue
  • Starts at 0 and **advances **as items are dequeued
  • Cells to the **left **of the queue’s front pointer are **unused **until we shift all elements left, which we do whenever the rear pointer is about to run off the end
Method 3
Idea
  • Use a circular array implementation
  • Variable **rear **starts at –1; Variable **front **starts at 0
  • **Front **chases rear pointer through the array
  • When a **pointer **is about to run off the end of the array, it is reset to 0
  • This wraps the queue around to the **beginning without **the moving any items

Graph View

Backlinks