CPSC 1430: Programming and Problem Solving II: 5 credit class

About

Continuation of programming and problem solving, including abstract data types (ADTs), dynamic memory, linked lists, stacks, queues, and testing.

Learning Outcomes

• Design and implement computer programs using multiple classes across multiple files, applying good style and appropriate documentation.
• Explain and appropriately use dynamic memory.
• Implement algorithms to manipulate linked lists, stacks and queues and use them appropriately in solving problems.
• Create unit test cases using pre-and post-conditions and boundary values.
• Use systematic debugging techniques effectively to trace code and identify problems.

Abstract Data Types

A type (or class) defined by its behavior (semantics) from the point of view of a user, particularly in terms of possible values, possible operations on data of this type, and the behavior of these operations.

ADTs are crucial in object-oriented programming because they allow programmers to define data structures and operations on those structures without specifying the implementation details.

Common examples of ADTs include stacks, queues, lists, trees, and graphs.
To implement an ADT in C++, you typically use classes.

Dynamic Memory

Dynamic memory in C++ refers to the allocation of memory at runtime using pointers.

Unlike static or automatic memory allocation, which is handled by the compiler and occurs at compile time, dynamic memory allocation provides more flexibility by allowing the program to request and release memory as needed while the program is running.

Operations: allocation using the 'new' operator & deallocation using the 'delete' operator

// Allocate memory for a single integer
int* p = new int;
*p = 5; // Assign a value to the allocated memory

// Allocate memory for an array of integers
int* arr = new int[5];
for (int i = 0; i < 5; ++i) {
arr[i] = i * 2; // Assign values to the array
}

// Deallocate memory
delete p; // Deallocate single integer
delete[] arr; // Deallocate array

Linked Lists

A linked list is a data structure used to store a collection of elements, where each element (node) contains a value and a pointer to the next element in the sequence.

Unlike arrays, linked lists do not require contiguous memory allocation, allowing for dynamic resizing and efficient insertion and deletion of elements.

Components of a Linked List
Node: A basic unit containing:
Data: The value stored in the node.
Next: A pointer/reference to the next node in the list.

Basic Operations
Insertion: Adding a new node to the list (at the beginning, end, or middle).
Deletion: Removing a node from the list.
Traversal: Accessing each node in the list.
Search: Finding a node with a specific value.

// Node structure
struct Node {
int data;
Node* next;
};

Stacks

A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. This means that the last element added to the stack is the first one to be removed.

Basic Operations on a Stack
Push: Add an element to the top of the stack.
Pop: Remove the element from the top of the stack.
Peek/Top: Retrieve the top element without removing it.
isEmpty: Check if the stack is empty.

A stack can be implemented using arrays, linked lists, or the C++ Standard Template Library (STL).

Queues

A queue is a linear data structure that follows the First In, First Out (FIFO) principle. This means that the first element added to the queue will be the first one to be removed.

Basic Operations on a Queue
Enqueue: Add an element to the end of the queue.
Dequeue: Remove the element from the front of the queue.
Front: Retrieve the front element without removing it.
isEmpty: Check if the queue is empty.

A queue can be implemented using arrays, linked lists, or the C++ Standard Template Library (STL).