Data Structures

Algorithms and Programming - Chapter 5: Data Structures

Introduction

  • When writing programs, variables are commonly used to store data.
  • However, when dealing with a large amount of related data items, data structures are preferred for organizing the data.

5.1 Data Structures Overview

  • Data is stored in computer memory cells arranged in a row.
  • Each memory location stores only one piece of data.
  • Data structures are methods for storing and organizing data in computer memory.
  • They determine the sequences and locations of data items in memory.

Arrays

  • An array is a simple linear data structure.
  • It stores a set of data sequentially in a continuous computer memory.

Pointers

  • A pointer is a variable that stores a computer memory address.
  • This address is usually the address of another variable.
  • A pointer "points" to a specific variable.

Common Data Structures

  • Data structures have different methods for data organization and manipulation.
  • This chapter covers three common data structures, represented using arrays and pointers:
    • Stack (堆疊)
    • Queue (隊列)
    • Linked list (鏈表)

5.2 Stacks

  • A stack is a data structure that follows the Last-In First-Out (LIFO) principle.
  • Analogy: Imagine a librarian stacking books on a bookshelf: The first book put becomes the bottom of the stack.
Concept and Manipulation of Stacks
  • Push: Adding an item to the stack places it on top.
  • Pop: Removing an item from the stack retrieves the item from the top.
Applications of Stacks in Computer Systems
  • Undo/Redo Operations: Commonly use the stack data structure.
    • Each operation is added to the undo stack.
    • Pressing "undo" moves the last operation from the undo stack to the redo stack.
    • Pressing "redo" moves the last undone operation from the redo stack back to the undo stack.
    • Performing a new operation clears the redo stack.
  • Call Stack: Stored in RAM and used to coordinate sub-programs.
    • When a sub-program is called, its stack frame (containing information like return address) is pushed into the call stack.
    • After execution, the stack frame is popped.
Manipulation of Stacks in Python

  • A Python list can be used to implement stack manipulations.

  • Creating an Empty Stack:

    the_stack = []

  • Pushing an Item:

    the_stack.append('A') # Adds "A" to the end of the list.

  • Popping an Item:

    temp = the_stack.pop() # Removes the last item and saves it to the variable temp.
Stack Considerations
  1. Underflow Error: Occurs when trying to pop from an empty stack.
  2. Overflow Error: Occurs when trying to push an item into a full stack.
Example 5.1 (Austin's Soft Drink Boxes)
  • Austin uses stacks to manage plastic boxes storing soft drinks.
  • Consider a stack with four boxes containing 10, 15, 10, and 20 bottles, respectively.
  • Sub-programs:
    • push(S, c): Pushes a box with c bottles into stack S.
    • pop(S): Takes a box from stack S and returns the number of bottles.
    • isEmpty(S): Returns True if S is empty, False otherwise.
Example 5.1 (a)

  • (i) Initially, stack S1S1 is empty. After executing the following:

    push(S1, 30)
push(S1, 10)
push(S1, 10)
push(S1, pop(S1) + pop(S1))
push(S1, 25)

  • (ii) Initially, stack S2S2 is empty. After executing the following:

    push(S2, 20)
push(S2, 10)
pop(S2)
if isEmpty(S2) then
    push(S2, 15)
else
    push(S2, 25)
Example 5.1 (b)

  • Initially, stacks S1S1 and S2S2 have content. After executing:

    temp ß 0
while not isEmpty(S1)
    temp ß temp + pop(S1)
    if temp > 25 then
        push(S2, 25)
        temp ß temp – 25
    push(S2, temp)
Example 5.1 (c)

  • The sub-program reverse(A, B) moves all boxes from stack A to stack B in reverse order, Initially S1S1 is non-empty and S2S2 is empty. The pseudocode is:

    while not isEmpty(A)
    push(B, pop(A))
Example 5.1 (d)

  • Remove the bottom NN boxes from S1S1 and keep the remaining boxes in the original order in S1S1. The pseudocode to achieve this is:

    reverse(S1, S2)
for i from 1 to N
    pop(S2)
reverse(S2, S1)
Example 5.1 (e)

  • Move kk boxes from the nthn^{th} layer of stack S1S1 to stack S2S2 and keep the remaining boxes in the original order in S1S1. The pseudocode is:

    define stack S3
t ß number of boxes in stack S1
for i from t down to n
    push(S3, pop(S1))
for i from 1 to k
    push(S2, pop(S3))
reverse(S3, S1)
Checkpoint 5.1
  • Uses stacks to implement "go back" and "go forward" functionality in a web browser.
  • (a) (i) Illustrates the goBack and goForward stacks after visiting a series of websites.
  • (a) (ii) Illustrates the goBack and goForward stacks after visiting a series of websites.
  • (b) (i) push (goForward, pop(goBack))
  • (b) (ii) push (goBack, pop(goForward))
  • (c) No action
  • (d) Firstly, remove the bottommost item in goForward. Then, perform the stack manipulation for clicking “go back”, i.e. push(goForward, pop(goBack)).

5.3 Queues

Concept and Manipulation of Queues
  • A queue is a data structure that follows the First-In First-Out (FIFO) principle.
  • Analogy: Imagine a queue outside a restaurant: The first one in the queue is the first one to enter the restaurant.
  • Enqueue: Adding an item to the end of the queue.
  • Dequeue: Taking an item from the beginning of the queue.
Applications of Queues in Computer Systems
  • Queues are widely applied in computer systems.
  • For example, the order of printing documents is stored as a queue in the printer memory.
Manipulation of Queues in Python

  • A Python list can be used to implement queue manipulations.

  • Creating an Empty Queue:

    the_queue = []

  • Enqueuing an Item:

    the_queue.append('A')  # Adds "A" to the end of the list.

  • Dequeuing an Item:

    temp = the_queue.pop(0)  # Removes the first item and saves it to the variable temp.
Example 5.2 (Marco's Number Array)
  • Marco creates a number array QQ with indexes from 1 to 10 and manipulates the array as a queue.
  • Sub-programs for queue manipulation:
    • enq(Q, num)
    • deq(Q)
    • isEmpty(Q)
    • isFull(Q)
Example 5.2 (a)

Write down the content of array QQ after the following algorithm has been executed:

enq(Q, 20)
deq(Q)
deq(Q)
Example 5.2 (b)

Marco writes the pseudocode for the sub-program isEmpty(Q), as follows:

Sub-program isEmpty(Q)
if item(Q) = 0 then
    return True
else
    return False

Write the pseudocode for the sub-program isFull(Q).

Sub-program isFull(Q)
if item(Q) = 10 then
    return True
else
    return False
Example 5.2 (c)

Complete the pseudocode for the following sub-program enq(Q, num) for Marco.

Sub-program enq(Q, num)
if ______________ then
    Output "Unsuccessful“
else
    ______________

Solution:

Sub-program enq(Q, num)
if isFull(Q) then
    Output "Unsuccessful“
else
    Q[item(Q) + 1] ß num
Example 5.2 (d)

Write the pseudocode for the sub-program deq(Q).

Sub-program deq(Q)
if isEmpty(Q) then
    Output "Unsuccessful“
else
    temp ß Q[1]
    for i from 1 to item(Q)-1
        Q[i] ß Q[i+1]
    Q[item(Q)] = ""
    return temp
Queues Manipulated with Pointers
  • Use two pointers (head and tail) to indicate the first and last items of the queue respectively.
  • Move the pointers when adding or deleting an item.
Circular Queues
  • When a pointer reaches the end of the array, reset the pointer to the index of the first item in the array.
  • Solve the problem of not being able to add new items or reuse the array items once the tail of the queue reaches the end of the array in a fixed-size array.
Queue Considerations
  1. Underflow Error: Cannot pop an item from an empty queue.
  2. Overflow Error: Cannot push an item into a full queue.
Example 5.3 (Steve's Ticketing Program)
  • Steve is developing a ticketing program for VIP counter services for a bank.
  • Uses an array T with indexes from 0 to 9 to store the names of the waiting customers.
  • Variables and sub-programs:
    • N: Number of customers in the queue.
    • first: Index of the first customer in the queue.
    • addQ(T, name): Adds a customer's name to the queue.
    • delQ(T): Removes a customer from the queue.
    • last(T): Returns the index of the last customer in the queue.
Checkpoint 5.2
  • (a) (i) P=2P = 2, Q=5Q = 5
  • (a) (ii) P=4P = 4, Q=8Q = 8
  • (b) P > Q
  • (c) Overflow error (index out of range)
Checkpoint 5.3

  • (a) N

  • (b) start = 3, next = 1

  • (c)

    Sub-program push(TAXI, no)
    if (next + 1) % N = start then
        Output "The queue is full.“
    else
        TAXI[next] ß no
        next ß (next + 1) % N

Sub-program pop(TAXI)
    if start = next then
        return "No taxi"
    else
        start ß (start + 1) % N
        return TAXI[start]

  • (d)

    Sub-program waiting(TAXI)
    if next >= start
        return next – start
    else
        return N - (start - next)

  • (e)

    total ß 0
i ß start
while i != next
    if P[i] = 5 then
        total ß total + 1
    i ß (i + 1) % N
Output total

5.4 Linked Lists

Concept and Manipulation of Linked Lists
  • A linked list is formed by many nodes.
  • Each node stores its own data and a pointer, which stores the address of the next node.
  • Nodes in the linked list are all connected by pointers.
Applications of Linked Lists in Computer Systems
  • Used in memory management to connect fragments of a file.
Differences between Linked Lists and Arrays
FeatureLinked ListsArrays
Types of data storedDifferentSame
Data access methodSequentialDirect access / Random access
Speed of data accessLowHigh
Speed of adding/deleting dataHighLow
Example 5.4 (Nicole's MTR Stations)
Nicole uses a linked list to store the English names of some MTR stations.
  • The content of the first node in the linked list stores “start”, while the pointer stores the index of the next node.
Example 5.4 (Anson's Linked List)
  • Anson constructed linked list DLL to store the student numbers of students studying Physics.
  • Each node has two pointers: pointer prev stores the address of the previous node; pointer next stores the address of the next node. The content of the first node in linked list DLL stores “physics”.
Checkpoint 5.4
  • (a) (b) start à Kyle à Daniel à Benson à Mike
  • (c) The memory (storage space) required is less.

5.5 Implementing Linked Lists with Arrays

Example 5.5 (Andrew's Implementation)
Andrew uses two arrays, D and NP, to implement linked list operations.
  • Andrew designs the following sub-programs to manipulate the linked list:
    • insert (n, name, i)
    • delete(n)
    • length()
    • start
Checkpoint 5.5

  • (a) painting, tea, yoga, japanese

  • (b)

    Sub-program printList()
    current ß monday
    while current != null
        Output schedule[current]
        current ß ptr[current]