Brief

Basic Data Structures

Data structures are methods of managing and storing data that enables efficient access and modification. There are hundreds of different data structures.

We will be going over three popular data structures: the stack, the queue, and the binary search tree.

Stack

A stack is a container of objects that are inserted and removed according to the last-in first-out (LIFO) principle. This means that the last thing added to the stack is the first thing that gets removed. A real-world example of a stack would be a PEZ dispenser, or a stack of plates at a buffet.

There are two principle operations to a stack:

• push, adds an element to the stack
• pop, removes the most recently added element

Queue

A queue is a container of elements that are inserted and removed according to the first-in first-out principle (FIFO). The first element added to the queue will be the first one to be removed. A real-world example of a queue would be a line of people waiting to get on an amusement park ride.

There are two principle operations to a queue:

• enqueue, adds an element to the back of the queue
• dequeue, removes an element from the front of the queue

Binary Search Tree

A binary search tree is an abstract data type that stores elements hierarchically. They allow fast lookup, insertion, and deletion. They keep their keys stored in order, so that lookup and other operations can use the principle of binary search. They traverse the tree from root to leaf making comparisons to keys stored in the nodes of the tree and deciding, on the basis of the comparison, to continue searching in the left or right subtrees.

There are three principle operations to a binary search tree:

• searching, searches for a specific key
• insertion, searches for the appropriate location to insert the key, then inserts the key
• deletion, searches for the key and deletes it.

Standard Template Library (STL)

The C++ STL provides multiple containers that can be easily used. We will be going over the containers that resemble stacks, queues, and binary search trees.

STL Stack

The STL Stack supports the following operations:

The code below shows the STL Stack in action.

#include <iostream>
#include <stack>

using namespace std;

int main() {
    stack<int> myStack;
    myStack.push(8);
    myStack.push(4);
    cout << myStack.top();
    myStack.pop();

    if (!myStack.empty())
        myStack.pop();
}

stack<int> myStack declares a stack of integers named myStack. myStack.push(x) inserts elements into the stack, while myStack.pop() removes elements from the stack. cout << myStack.top() prints 4. To check if the stack is empty, myStack.empty() is called.

STL Queue

The STL Queue supports the following operations:

The code below shows the STL Queue in action.

#include <iostream>
#include <queue>

using namespace std;

int main() {
    queue<int> myQueue;
    myQueue.push(8);
    myQueue.push(4);
    cout << myQueue.front();
    cout << myQueue.back();
    myQueue.pop();

    if (!s.empty())
        s.pop();
}

queue<int> myQueue declares a queue of integers named myQueue. myQueue.push(x) inserts elements into the queue, while myQueue.pop() removes elements from the queue. cout << myQueue.front() prints 8, while cout << myQueue.back() prints 4. To check if the queue is empty, myQueue.empty() is called.

STL Map

The STL Map supports the following operations:

The code below shows the STL Map in action.

#include <iostream>
#include <map>

using namespace std;

int main() {
    map<string, int> age;
    age["tommy"] = 20;
    age["oscar"] = 21;
    cout << age["tommy"];
    cout << age["oscar"];
    age.erase("tommy");
}

map<string, int> age declares a map with strings as keys and integers as values. age["tommy"] = 20 inserts the key, value pair “tommy” and 20 into the map, while age.erase() removes the key, value pair from the map. cout << age["tommy"] prints 20, while cout << age["oscar"] prints 21.