Introduction to Data Structures
Hi there! Welcome to one of the most important chapters in Computer Science. Think of Data Structures as the "containers" we use to store information. Just like you wouldn't store soup in a shoe box or socks in a soup bowl, programmers choose different data structures based on what they need to do with the data.
In this guide, we’ll explore how to organize data so our programs run smoothly and efficiently. Don’t worry if some of this feels a bit abstract at first—we’ll use plenty of real-world examples to make it stick!
1. Arrays: The Organized Row
An Array is a collection of data items of the same data type stored under a single name. Imagine a long row of lockers in a school hallway. Each locker has a number (an index), and you can put one item inside each.
1D, 2D, and 3D Arrays
The syllabus requires you to understand arrays of up to three dimensions. Let's break them down:
- 1D Array (Linear): A simple list. Example: A shopping list or a row of lockers.
- 2D Array (Grid): Like a table or a chessboard. To find a specific "locker," you need a row number and a column number. Example: A spreadsheet or a cinema seating plan.
- 3D Array (Multi-layered): Like a stack of grids. Imagine an apartment building where you need the Floor, the Room Number, and the Cabinet inside that room.
Important Point: In most programming languages, we start counting at 0, not 1. This is called zero-based indexing. So, the first item in an array is at index \(0\).
Quick Review: Array Properties
1. They store data of the same type (e.g., all integers).
2. They have a fixed size (once created, you usually can't change the number of "lockers").
3. You can access any item instantly if you know its index.
2. Records: The Digital Identity Card
While an array is great for a list of the same things (like 100 prices), a Record is used when you want to store different types of data about one specific thing.
Imagine a Student Record. It might contain:
- StudentID: Integer (e.g., 5021)
- Name: String (e.g., "Alice")
- IsEnrolled: Boolean (e.g., True)
Each individual item in a record is called a Field.
Analogy: Think of a Record like a single card in a physical filing cabinet. It holds all the different bits of info for one person or object.
3. Lists and Tuples
These might look like arrays, but they have a few "personality" differences:
Lists
A List is more flexible than an array. Unlike arrays, lists can often grow or shrink in size while the program is running. They are mutable, which is a fancy way of saying they can be changed.
Tuples
A Tuple is a list that is immutable—it cannot be changed once it is created.
Why use a tuple? It’s safer! If you have data that should never change (like the coordinates of a fixed landmark or the RGB values for a specific color), putting it in a tuple prevents accidental changes.
Memory Aid: Tuples are Trapped (they can't change!).
4. Stacks: The "Last-In, First-Out" Structure
A Stack is a data structure where the last item you put in is the first one you take out. We call this LIFO (Last-In, First-Out).
Everyday Analogy: Think of a stack of cafeteria trays or a tube of Pringles. You can only take the top tray off, and you can only add a new tray to the top.
Stack Operations
- Push: Adding an item to the top of the stack.
- Pop: Removing the item from the top of the stack.
- Peek: Looking at the top item without removing it.
Did you know? The "Undo" button on your computer uses a stack! Every action you take is pushed onto a stack. When you hit Undo, the computer pops the last action off the top to reverse it.
Quick Review: Stack Logic
If you push A, then B, then C onto a stack, the first item you "Pop" will be C.
5. Queues: The "First-In, First-Out" Structure
A Queue is the opposite of a stack. It follows the FIFO (First-In, First-Out) rule. The first person to join the line is the first person to be served.
Everyday Analogy: A line at a supermarket or a "queue" for a rollercoaster.
Queue Operations
- Enqueue: Adding an item to the back (rear) of the queue.
- Dequeue: Removing an item from the front of the queue.
Common Mistake: Students often get confused about where items leave. Just remember a real-life queue: You join at the back (Enqueue) and leave from the front (Dequeue) when it's your turn!
Key Takeaway: Stack vs. Queue
Stack = LIFO (Last-In, First-Out)
Queue = FIFO (First-In, First-Out)
Summary and Tips for Success
Don't worry if these seem like just "names" right now. The best way to learn them is to think about how the data moves:
- Use an Array for a fixed-size list of the same type of items.
- Use a Record to group different types of info about one thing.
- Use a Tuple for data that must stay "locked" and unchanged.
- Use a Stack when you need to remember the most recent thing (like "Undo").
- Use a Queue when you need to process things in the order they arrived (like a printer printing documents).
Final Tip: When drawing stacks or queues in an exam, always clearly label the Top (for stacks) or the Front and Rear (for queues). It shows the examiner you truly understand the "pointers" involved!