Skip to content

AEiE0701 Data structure and algorithm

Data type, data structure, and abstract data type

Term Meaning
Data type Set of values plus allowed operations at language level
Data structure Concrete way of organizing data in memory
Abstract data type Logical specification of data and operations independent of implementation

Key distinction:

  • ADT defines what operations exist.
  • Data structure defines how those operations are physically implemented.

Linear data structures

  • Linear data structures arrange elements in a sequence.
  • Arrays, linked lists, stacks, and queues are standard examples.

Stack

  • Stack follows LIFO: last in, first out.
  • Basic operations: push, pop, peek or top, isEmpty, isFull in array implementation.
  • Applications: recursion support, function-call stack, expression conversion, postfix evaluation, backtracking.

Queue

  • Queue follows FIFO: first in, first out.
  • Basic operations: enqueue, dequeue, front, rear.
  • Variants: circular queue, priority queue, deque.

Stack and queue implementation cues

Structure Array implementation cue Linked implementation cue
Stack Top index moves Insert/delete at head convenient
Queue Front and rear indices, circular array useful Front and rear pointers

Infix to postfix conversion

  • Postfix places operator after operands.
  • Use a stack for operators while scanning the infix expression.
  • Respect precedence and associativity.
  • Parentheses control grouping but disappear in postfix output.

Typical precedence reminder:

  • Exponentiation highest.
  • Multiplication and division next.
  • Addition and subtraction lower.

Postfix evaluation

  1. Scan left to right.
  2. Push operands.
  3. On operator, pop required operands.
  4. Apply operator.
  5. Push result.

Array implementation of lists

  • Array list stores elements in contiguous memory.
  • Supports direct indexing in \(O(1)\) time.
  • Insertion or deletion in the middle often requires shifting elements.

Stack and queue as list views

  • Stack can be seen as a restricted list allowing insertion and deletion at one end only.
  • Queue can be seen as a restricted list allowing insertion at rear and deletion at front.

Linked list basics

  • A linked list stores nodes connected by pointers.
  • Dynamic memory use avoids contiguous-allocation requirement.
  • Sequential access is natural; random indexing is poor.

Linked-list operations the syllabus explicitly names:

Operation Core idea
Creation Allocate nodes and link them
Insert at beginning New node points to old head
Insert at middle Adjust predecessor and new-node links
Insert at end Traverse to tail unless tail pointer exists
Delete at beginning Move head to next node
Delete at middle Bypass target node
Delete at end Find predecessor of tail unless doubly linked or tail tracked

Trees and binary trees

  • Tree is a hierarchical non-linear data structure.
  • Root has no parent.
  • Leaf has no children.
  • Degree is number of children.
  • Height or depth measures levels depending on convention.

Binary-tree operations commonly expected:

  • Insertion.
  • Deletion.
  • Traversal: preorder, inorder, postorder.
  • Search.

Cue:

  • In a binary search tree, left subtree keys are smaller and right subtree keys are larger than the node key.

Data-structure examples

  1. Expression A+B*C becomes ABC*+ in postfix because multiplication has higher precedence.
  2. Pushing 2, then 5, then popping returns 5 first, confirming LIFO.
  3. Array lists index quickly, while linked lists insert at head quickly.

AEiE0701 revision box

  • ADT says what; data structure says how.
  • Stack = LIFO, queue = FIFO.
  • Postfix evaluation uses operand stack.
  • Array lists give direct indexing; linked lists give flexible insertion without shifting.
  • Binary tree traversal names must stay distinct: preorder, inorder, postorder.