IB COMPUTER SCIENCE | Data Structures for Topic 5

ABSTRACT DATA STRUCTURES | DATA STRUCTURES

Topics from the IB Computer Science Specification 2014

ALSO IN THIS TOPIC
RECURSION
YOU ARE HERE | DATA STRUCTURES
LINKED LISTS
TREES
APPLICATION
TOPIC 5 REVISION
KEY TERMINOLOGY
TOPIC 5 ANSWERS

SECTION 1 | ONE VS TWO DIMENSIONAL ARRAYS

In computer programming, arrays are a way of storing and organizing data in a particular format. at IB level you should be confident with both one dimensional and two dimensional arrays. Here's a brief description of both:

ONE DIMENSIONAL ARRAY

A one-dimensional array is a collection of elements of the same data type that are stored in a linear format.
It is also known as a single-subscript array because it is accessed using only one index.
The elements are stored sequentially in memory, and they can be accessed using their index or position.
A one-dimensional array can be used to store a list of items, such as an array of names, ages, or grades.

TWO DIMENSIONAL ARRAY

A two-dimensional array is a collection of elements of the same data type that are stored in a tabular format.
It is also known as a double-subscript array because it is accessed using two indexes, one for the row and one for the column.
The elements are stored in rows and columns, just like a table, and they can be accessed using their row and column indexes.
A two-dimensional array can be used to store data that has a natural structure or relationship between rows and columns, such as a spreadsheet or a chess board.

COMPARISION BETWEEN A ONE AND TWO DIMENSIONAL ARRAY

One-dimensional arrays are best suited for storing lists of data that don't have a natural structure or relationship between elements.
Two-dimensional arrays are best suited for storing data that has a natural structure or relationship between rows and columns.
One-dimensional arrays can be used to store large amounts of data in a compact way, making them efficient in terms of memory usage.
Two-dimensional arrays can be used to represent complex data structures that require multiple dimensions, such as matrices or grids.
One-dimensional arrays are often used for simple operations like searching, sorting, and filtering data.
Two-dimensional arrays are often used for more complex operations like matrix multiplication or image processing.

SECTION 2 | CONSTRUCT A 2D ARRAY ALGORITHM

STACKS AND QUEUES

SECTION 3 | WHAT ARE STACKS AND QUEUES

Stacks and queues are similar in nature to lists or arrays in programming, the both hold data in a linear way and both can have data added and removed. Stacks and queues are two methods of handling data flow. The main difference between stacks and queues is how the data is taken (popped) from each. Both Stacks and Queues are commonly used in RAM to store temporary data that is about to be processed.
Stacks have a Last In First Out structure - LIFO
Queues have a First In First Out structure - FIFO

SECTION 4 | STACKS LIFO STRUCTURE

With a LIFO stack the last item of data in to the stack is always the first item of data out. To illustrate this, imagine piling books on top of each other, the last book you placed(at the top of the pile) is the first book you will pick up, even if you want to read the book from the bottom of the pile you would need to remove (pop) each book above it first. This is known as Last In First Out (LIFO)

You can only put in or take out one item at a time in the stack. If you want to access the third item in the stack you would have to remove the first item, then remove the second item before you could access the third item.

Stack are used in many computational processes such as the Polish and Reverse Polish notation discussed later on this page, they are are used for everyday processing such as an undo function in a program, the last thing you did will be at the top of the stack therefore when you click undo that is the first item to be removed, hence actuating the undo feature.

There are many features of stacks however 3 methods that are popular and common to A-Level and IB Computer Science are:
✓ push(item) add item to the top of the stack
✓ pop() remove and return the item from the top of the stack
✓ isEmpty() return true or false depending on the items in the stack

We can easily simulate a stack in Python or Java using Lists and Arrays. For example in Python to to insert an item to the top (end) of a list you can use the append method, to remove an item from the top(end) of a list you can use the pop method. Below shows some examples in both Python and Java simulating these three methods, push(), pop() and isEmpty().

STACK METHODS IN PYTHON

PUSH METHOD IN PYTHON
Copy and try the code below, the append method is simulating a stack push by adding an item to the last(top) of the list one at a time.
myStack = []

myStack.append("Bob")
myStack.append("Jill")
myStack.append("Jane")
print (myStack)

POP METHOD IN PYTHON
Copy and try code below. the pop() method pops(removes) the last(top) item in the list.
myStack = ["Bob","Jane","Jill"]
myStack.pop()
print(myStack)

ISEMPTY METHOD IN PYTHON
Copy and try the code below, this is one way to simulate a stack isEmpty method in python.
myStack = []

if not myStack:
print ("The Stack is Empty")

SECTION 5 | QUEUE FIFO STRUCTURE

With a FIFO queue the first item of data in to the queue is always the first item of data out. To illustrate this, imagine a queue at a coffee shop, the person at the front of the queue if the first to get processed, new people join the back of the queue and work their way to the front at other customers are processed, they cannot jump the queue at any point. This is known as First In First Out (FIFO)

There are many features of queue however 3 methods that are popular and common to A-Level and IB Computer Science are:
✓ enqueue() add item to the end of the queue
✓ dequeue(queue location 0) remove and return the item from the front of the queue
✓ isEmpty() return true or false depending on the items in the queue

QUEUE METHODS IN PYTHON

ENQUEUE METHOD IN PYTHON
We can you the same method as the stack to place an item at the end of the queue, Copy and try the code below, the append method is simulating a queue enqueue by adding an item to the last position of the list one at a time.
myQueue = []
myQueue.append("Bob")
myQueue.append("Jill")
myQueue.append("Jane")
print (myQueue)

DEQUEUE METHOD IN PYTHON
Like used in the stack, we can also use the pop() method to remove the item at the front of the queue, the difference being we now need to stipulate the position of the item, the item at the front of the queue will always be position zero. Copy and try code below.
myStack = ["Bob","Jane","Jill"]
myStack.pop(0)
print(myStack)

ISEMPTY METHOD IN PYTHON
Copy and try the code below, this is one way to simulate a Queue isEmpty method in python.
myQueue = []
if not myQueue:
print ("The Queue is Empty")

Arrays can be used as static data structures to implement stacks and queues.

STATIC STACK

A static stack is a data structure that follows the Last In First Out (LIFO) principle.
Elements are added and removed from the same end, which is usually the top of the stack.
Static stacks can be implemented using a one-dimensional array by restricting access to the array's elements to only one end.
Example 1: Undo/Redo feature in a text editor. Every time a user makes a change, it can be pushed onto the stack, and the user can undo/redo changes by popping them off the stack.
Example 2: Backtracking in a maze solving program. The program can push the current state onto the stack, move to a new state, and if it doesn't lead to the solution, it can pop the previous state from the stack and try a different move.

STATIC QUEUE

A static queue is a data structure that follows the First In First Out (FIFO) principle.
Elements are added to one end of the queue (the rear) and removed from the other end (the front).
Static queues can be implemented using a one-dimensional array by keeping track of the front and rear indexes and shifting elements to the left after each dequeue operation.
Example 1: Print spooling in a computer system. Print jobs are added to the end of the queue, and the printer prints them in the order they were added.
Example 2: Request handling in a web server. Incoming requests are added to the end of the queue, and the server processes them in the order they were received.

In general, using arrays as static stacks and queues can be useful when the size of the data structure is known in advance and doesn't change during the program's execution. They can provide a simple and efficient way to manage data in memory without the overhead of dynamic memory allocation. However, their static nature can also be a limitation when the size of the data structure needs to be changed dynamically, as it requires copying elements to a new array.

SECTION 6 | MEMORY ALLOCATION

Stacks and queues can be implemented using different types of memory. Heap memory is not on the IB Computer Science 2014 Specification however it is useful to know in the understanding of memory types.

STACK MEMORY

The stack memory is a type of memory used by programs to store temporary variables, function calls, and other data during runtime.
The stack memory is a region of memory that is allocated automatically by the operating system when a program is run.
Stacks can be implemented using stack memory because of their LIFO (Last In First Out) nature. When a function is called, its local variables and other data are pushed onto the stack, and when the function returns, they are popped off the stack.

HEAP MEMORY

The heap memory is a type of memory used by programs to allocate and deallocate memory dynamically during runtime.
Unlike stack memory, the heap memory is not automatically managed by the operating system, and the program has to manually allocate and deallocate memory.
Queues can be implemented using heap memory because of their dynamic nature. When a new element is added to the queue, memory can be allocated on the heap to store it, and when an element is removed, the memory can be deallocated.

STATIC MEMORY

Static memory is a type of memory that is allocated during the compilation of a program and exists for the duration of the program's execution.
Static memory is used to store global variables and other data that needs to be accessible throughout the program.
Stacks and queues can also be implemented using static memory by allocating a fixed amount of memory for them and using indexes or pointers to keep track of the current position.

In general, the type of memory used to implement stacks and queues depends on the specific requirements of the program. Stack memory is often used when the size of the data structure is fixed, and the data can be stored temporarily. Heap memory is used when the size of the data structure is dynamic, and the data needs to be allocated and deallocated frequently. Static memory is used when the size of the data structure is known in advance, and the data needs to be accessed globally throughout the program.

SECTION 7 | DYNAMIC MEMORY

Dynamic memory allocation is a feature in programming languages that allows the program to allocate and deallocate memory during runtime. Unlike static memory allocation, which is determined at compile time, dynamic memory allocation enables programs to adapt to changing memory requirements and allocate memory only when needed. This can be particularly useful when dealing with data structures whose size or contents are not known in advance. In many programming languages, dynamic memory allocation is performed using functions such as malloc() or new(), which allocate memory on the heap and return a pointer to the allocated memory. The program can then use this pointer to access the allocated memory and store data. Once the memory is no longer needed, it can be deallocated using functions such as free() or delete().

SECTION 8 | HEAP MEMORY

Heap memory is a region of memory in a computer's RAM that is used for dynamic memory allocation. Unlike the stack memory, which is used for static memory allocation, the heap memory is managed manually by the programmer, allowing for dynamic allocation and deallocation of memory during runtime. This memory is commonly used to allocate memory for data structures such as arrays, linked lists, and trees. The programmer is responsible for managing the lifetime of the allocated memory by freeing it using functions such as free() or delete() when it is no longer needed. If not managed correctly, heap memory can lead to memory leaks, segmentation faults, or other memory-related errors, so it requires careful and deliberate management.

Heap memory storage is typically structured as a large contiguous block of memory that is allocated to the program during runtime. The heap is usually managed by the operating system or runtime environment, which tracks the allocation and deallocation of memory to ensure that it is used efficiently.

SECTION 9 | STACK OVERFLOW

A stack overflow is an error that occurs when a program's call stack, the data structure that stores information about the active subroutines or functions, exceeds its limit. The size of the call stack is finite, and if too many nested calls are made, or if too much data is stored in the stack frames, it can "overflow", leading to a program crash or other unintended behavior.

Every time a function is called in a program, a new stack frame is allocated on the call stack. This stack frame contains things like the function's local variables, the arguments passed to the function, and the return address that the function needs to jump back to when it's done. If the total size of these stack frames exceeds the stack's limit, a stack overflow occurs.

Recursive functions can potentially cause a stack overflow if they don't have a proper base case or if the base case is not reached in a reasonable amount of recursive calls. A recursive function is a function that solves a problem by solving smaller instances of the same problem.

For example, consider a function that calculates the factorial of a number recursively:

def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n - 1)

This function works fine for small inputs, but if you call factorial(1000000), it will lead to a stack overflow because it makes a million nested calls, creating a million stack frames, which will likely exceed the stack limit.

One solution to prevent stack overflow in recursive functions is to ensure the recursion depth is kept under control, often by ensuring input sizes are manageable. Alternatively, certain problems can be reformulated in an iterative manner, which uses the program's heap for storing data, rather than the stack, avoiding the issue of stack overflow.

What is a stack data structure and how does it differ from a queue data structure?
What is the principle behind the Last-In-First-Out (LIFO) method of a stack?
How does the push and pop operations work in a stack?
What are the applications of stack data structures in computer science?
What is the difference between a static stack and a dynamic stack?
What is the First-In-First-Out (FIFO) method of a queue data structure?
How does enqueue and dequeue operations work in a queue data structure?
What are the advantages of using a queue data structure over a stack data structure?
How can a queue data structure be implemented in real-life situations, such as printing jobs or process management in an operating system?
What is the difference between a linear queue and a circular queue, and in what cases would one be preferred over the other?

Consider the following pseudocode function that uses a stack to check if a given string is a palindrome:

Explain how the createStack(), push(stack, character), and pop(stack) functions work in the above code. (3 marks)
Using the provided function, write pseudocode for a function called isPalindromicWord(word: string) -> boolean that takes a single word as input and checks if it is a palindrome. You may assume that the word contains only lowercase letters. (5 marks)
Modify the isPalindrome(string: string) -> boolean function to handle palindromic phrases with spaces. Your solution should remove all spaces from the input string before checking if it is a palindrome. (7 marks)

ALSO IN THIS TOPIC

RECURSION
DATA STRUCTURES
LINKED LISTS
TREES
APPLICATION
TOPIC 5 REVISION
KEY TERMINOLOGY
TOPIC 5 ANSWERS