Chapter 1: Lists, Stacks, and Queues
Activity 1: Implementing a Song Playlist
In this activity, we will implement a tweaked version of a doubly linked list which can be used to store a song playlist and supports the necessary functions. Follow these steps to complete the activity:
- Let's first include the header and write the node structure with the required data members:
#include <iostream>
template <typename T>
struct cir_list_node
{
T* data;
cir_list_node *next, *prev;
~cir_list_node()
{
delete data;
}
};
template <typename T>
struct cir_list
{
public:
using node = cir_list_node<T>;
using node_ptr = node*;
private:
node_ptr head;
size_t n;
- Now, let's write a basic constructor and size function:
public:
cir_list(): n(0)
{
head = new node{NULL, NULL, NULL}; // Dummy node – having NULL data
head->next = head;
head->prev = head;
}
size_t size() const
{
return n;
}
We'll discuss why we need a dummy node between the first and the last node later on, in the case of iterating using iterators.
- Now, let's write the insert and erase functions. Both will take one value to be inserted or deleted:
void insert(const T& value)
{
node_ptr newNode = new node{new T(value), NULL, NULL};
n++;
auto dummy = head->prev;
dummy->next = newNode;
newNode->prev = dummy;
if(head == dummy)
{
dummy->prev = newNode;
newNode->next = dummy;
head = newNode;
return;
}
newNode->next = head;
head->prev = newNode;
head = newNode;
}
void erase(const T& value)
{
auto cur = head, dummy = head->prev;
while(cur != dummy)
{
if(*(cur->data) == value)
{
cur->prev->next = cur->next;
cur->next->prev = cur->prev;
if(cur == head)
head = head->next;
delete cur;
n--;
return;
}
cur = cur->next;
}
}
- Now, let's write a basic structure for the required iterator and add members to access the actual data:
struct cir_list_it
{
private:
node_ptr ptr;
public:
cir_list_it(node_ptr p) : ptr(p)
{}
T& operator*()
{
return *(ptr->data);
}
node_ptr get()
{
return ptr;
}
- Now, let's implement the core functions of an iterator – pre- and post-increments:
cir_list_it& operator++()
{
ptr = ptr->next;
return *this;
}
cir_list_it operator++(int)
{
cir_list_it it = *this;
++(*this);
return it;
}
- Let's add the decrement-related operations to make it bidirectional:
cir_list_it& operator--()
{
ptr = ptr->prev;
return *this;
}
cir_list_it operator--(int)
{
cir_list_it it = *this;
--(*this);
return it;
}
- Let's implement equality-related operators for the iterator, which are essential for range-based loops:
friend bool operator==(const cir_list_it& it1, const cir_list_it& it2)
{
return it1.ptr == it2.ptr;
}
friend bool operator!=(const cir_list_it& it1, const cir_list_it& it2)
{
return it1.ptr != it2.ptr;
}
};
- Now, let's write the begin and end functions with their const versions as well:
cir_list_it begin()
{
return cir_list_it{head};
}
cir_list_it begin() const
{
return cir_list_it{head};
}
cir_list_it end()
{
return cir_list_it{head->prev};
}
cir_list_it end() const
{
return cir_list_it{head->prev};
}
- Let's write a copy constructor, initializer list constructor, and destructor:
cir_list(const cir_list<T>& other): cir_list()
{
// Although, the following will insert the elements in a reverse order, it won't matter in a logical sense since this is a circular list.
for(const auto& i: other)
insert(i);
}
cir_list(const std::initializer_list<T>& il): head(NULL), n(0)
{
// Although, the following will insert the elements in a reverse order, it won't matter in a logical sense since this is a circular list.
for(const auto& i: il)
insert(i);
}
~cir_list()
{
while(size())
{
erase(head->data);
}
}
};
- Now, let's add a class for the music player's playlist for our actual application. Instead of storing the songs, we'll just go ahead and store integers indicating the ID of the song for ease of understanding:
struct playlist
{
cir_list<int> list;
- Let's now implement functions to add and delete songs:
void insert(int song)
{
list.insert(song);
}
void erase(int song)
{
list.erase(song);
}
- Now, let's implement functions to print all the songs:
void loopOnce()
{
for(auto& song: list)
std::cout << song << " ";
std::cout << std::endl;
}
};
- Let's write a main function to use the playlist of our music player:
int main()
{
playlist pl;
pl.insert(1);
pl.insert(2);
std::cout << "Playlist: ";
pl.loopOnce();
playlist pl2 = pl;
pl2.erase(2);
pl2.insert(3);
std::cout << "Second playlist: ";
pl2.loopOnce();
}
- Upon executing this, you should get output like this:
Playlist: 2 1
Second playlist: 3 1
Activity 2: Simulating a Card Game
In this activity, we will simulate a card game and implement an efficient data structure to store the information about each player's cards. Follow these steps to complete the activity:
- First, let's include the necessary headers:
#include <iostream>
#include <vector>
#include <array>
#include <sstream>
#include <algorithm>
#include <random>
#include <chrono>
- Now, let's create a class to store the cards and a utility method to print them properly:
struct card
{
int number;
enum suit
{
HEART,
SPADE,
CLUB,
DIAMOND
} suit;
std::string to_string() const
{
std::ostringstream os;
if(number > 0 && number <= 10)
os << number;
else
{
switch(number)
{
case 1:
os << "Ace";
break;
case 11:
os << "Jack";
break;
case 12:
os << "Queen";
break;
case 13:
os << "King";
break;
default:
return "Invalid card";
}
}
os << " of ";
switch(suit)
{
case HEART:
os << "hearts";
break;
case SPADE:
os << "spades";
break;
case CLUB:
os << "clubs";
break;
case DIAMOND:
os << "diamonds";
break;
}
return os.str();
}
};
- Now, we can create a deck of cards and shuffle the deck to randomly distribute the cards to each of the four players. We'll write this logic inside a game class and call the functions later on in the main function:
struct game
{
std::array<card, 52> deck;
std::vector<card> player1, player2, player3, player4;
void buildDeck()
{
for(int i = 0; i < 13; i++)
deck[i] = card{i + 1, card::HEART};
for(int i = 0; i < 13; i++)
deck[i + 13] = card{i + 1, card::SPADE};
for(int i = 0; i < 13; i++)
deck[i + 26] = card{i + 1, card::CLUB};
for(int i = 0; i < 13; i++)
deck[i + 39] = card{i + 1, card::DIAMOND};
}
void dealCards()
{
unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
std::shuffle(deck.begin(), deck.end(), std::default_random_engine(seed));
player1 = {deck.begin(), deck.begin() + 13};
player2 = {deck.begin() + 13, deck.begin() + 26};
player3 = {deck.begin() + 26, deck.begin() + 39};
player4 = {deck.begin() + 39, deck.end()};
}
- Let's write the core logic to play one round. To avoid duplicating the code, we will write a utility function that will compare two players' hands and remove both cards if required:
bool compareAndRemove(std::vector<card>& p1, std::vector<card>& p2)
{
if(p1.back().number == p2.back().number)
{
p1.pop_back();
p2.pop_back();
return true;
}
return false;
}
void playOneRound()
{
if(compareAndRemove(player1, player2))
{
compareAndRemove(player3, player4);
return;
}
else if(compareAndRemove(player1, player3))
{
compareAndRemove(player2, player4);
return;
}
else if(compareAndRemove(player1, player4))
{
compareAndRemove(player2, player3);
return;
}
else if(compareAndRemove(player2, player3))
{
return;
}
else if(compareAndRemove(player2, player4))
{
return;
}
else if(compareAndRemove(player3, player4))
{
return;
}
unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
std::shuffle(player1.begin(), player1.end(), std::default_random_engine(seed));
std::shuffle(player2.begin(), player2.end(), std::default_random_engine(seed));
std::shuffle(player3.begin(), player3.end(), std::default_random_engine(seed));
std::shuffle(player4.begin(), player4.end(), std::default_random_engine(seed));
}
- Now, let's write the main logic to find out who's the winner. We'll call the preceding function in a loop until one of the players can get rid of all their cards. To make the code more readable, we will write another utility function to check whether the game has been completed:
bool isGameComplete() const
{
return player1.empty() || player2.empty() || player3.empty() || player4.empty();
}
void playGame()
{
while(not isGameComplete())
{
playOneRound();
}
}
- To find out who's the winner, let's write a utility function before starting the main function:
int getWinner() const
{
if(player1.empty())
return 1;
if(player2.empty())
return 2;
if(player3.empty())
return 3;
if(player4.empty())
return 4;
}
};
- Finally, let's write the main function to execute the game:
int main()
{
game newGame;
newGame.buildDeck();
newGame.dealCards();
newGame.playGame();
auto winner = newGame.getWinner();
std::cout << "Player " << winner << " won the game." << std::endl;
}
- One of the possible outputs could be as follows:
Player 4 won the game.
Note
The winner could be any player from 1 to 4. Since the game is based on randomness seeded by the time during execution, any of the players can win. Running the code multiple times may yield a different output every time.
Activity 3: Simulating a Queue for a Shared Printer in an Office
In this activity, we shall implement a queue for handling print requests to a shared printer in an office. Follow these steps to complete the activity:
- Let's include the required headers:
#include <iostream>
#include <queue>
- Let's implement a Job class:
class Job
{
int id;
std::string user;
int time;
static int count;
public:
Job(const std::string& u, int t) : user(u), time(t), id(++count)
{}
friend std::ostream& operator<<(std::ostream& os, const Job& j)
{
os << "id: " << id << ", user: " << user << ", time: " << time << " seconds" << std::endl; return os;
}
};
int Job::count = 0;
- Now, let's implement the Printer class. We'll use std::queue to have a first come, first served policy for jobs. We'll keep the class templated based on the maximum number of jobs it can store in memory:
template <size_t N>
class Printer
{
std::queue<Job> jobs;
public:
bool addNewJob(const Job& job)
{
if(jobs.size() == N)
return false;
std::cout << "Added job in the queue: " << job;
jobs.push(job);
return true;
}
- Now, let's implement another major functionality – printing jobs:
void startPrinting()
{
while(not jobs.empty())
{
std::cout << "Processing job: " << jobs.front();
jobs.pop();
}
}
};
- Now, let's use these classes to simulate the scenario:
int main()
{
Printer<5> printer;
Job j1("John", 10);
Job j2("Jerry", 4);
Job j3("Jimmy", 5);
Job j4("George", 7);
Job j5("Bill", 8);
Job j6("Kenny", 10);
printer.addNewJob(j1);
printer.addNewJob(j2);
printer.addNewJob(j3);
printer.addNewJob(j4);
printer.addNewJob(j5);
if(not printer.addNewJob(j6)) // Can't add as queue is full.
{
std::cout << "Couldn't add 6th job" << std::endl;
}
printer.startPrinting();
printer.addNewJob(j6); // Can add now, as queue got emptied
printer.startPrinting();
}
- Here is the output of the preceding code:
Added job in the queue: id: 1, user: John, time: 10 seconds
Added job in the queue: id: 2, user: Jerry, time: 4 seconds
Added job in the queue: id: 3, user: Jimmy, time: 5 seconds
Added job in the queue: id: 4, user: George, time: 7 seconds
Added job in the queue: id: 5, user: Bill, time: 8 seconds
Couldn't add 6th job
Processing job: id: 1, user: John, time: 10 seconds
Processing job: id: 2, user: Jerry, time: 4 seconds
Processing job: id: 3, user: Jimmy, time: 5 seconds
Processing job: id: 4, user: George, time: 7 seconds
Processing job: id: 5, user: Bill, time: 8 seconds
Added job in the queue: id: 6, user: Kenny, time: 10 seconds
Processing job: id: 6, user: Kenny, time: 10 seconds
