Chapter 17 - Worked Exercises 1

Exercise 1

Complete the Restaurant Queuing System from Worked Exercises 1, which makes use of the std::deque class.

Chapter 15 - Worked Exercises 1 | C++ Lessonstutoring.cho.io

Exercise 2 - Palindrome

Preamble

The problem of identifying whether a string is a palindrome can be solved by using a deque data structure.

The solution stores each character of a string in a deque, checks the whether the front and back of the deque are identical.

If the elements are found identical, the elements are removed from the deque, and the process is repeated for the next elements.

If the elements are found to not be identical, then we know that the string cannot be a palindrome.

If we can keep matching the first and last elements, eventually we will run out of characters to match, or be left with a deque of size 1 if the length of the original string was odd; in either case this must mean that the string must be a palindrome.

Exercise

Implement the following function based on the algorithm using a deque as described above:

bool isPalindrome(std::string word);

Exercise 3 - Cafeteria Queue

Preamble

A school cafeteria only serves two meal options which students can choose from: sandwiches, or bento boxes.

Students queue up at the cafeteria every day to get their meals, but these meals are prepared on-the-fly and so require time to prepare. If 3 students in a row order the same thing, the first two students will be served, but third student will have to be sent to the back of the queue.

You can imagine that there would be a "counter" keeping track of this.

Once a student is sent to the back of the queue, the "counter" is reset and the next 2 students would be able to order the same thing again.

Exercise

You are provided a deque of integers with values either 1 or 2. Each element represents a student, and the value represents their meal choice of either a sandwich, or a bento box.

You are meant to implement a function that simulates the above process, and calculate the number of students that will have to be "processed" before all students have been served.

int numStudentsProcessed(std::deque<int> choices);

Example 1

Starting with: [1, 2, 1, 1, 2]

Iteration 1: [2, 1, 1, 2] (one student served)

Iteration 2: [1, 1, 2] (one student served)

Iteration 3: [1, 2] (one student served)

Iteration 4: [2] (one student served)

Iteration 5: [] (one student served)

The answer is 5.

Example 2

Starting with: [1, 1, 1, 2]

Iteration 1: [1, 1, 2] (one student served, counter = 1)

Iteration 2: [1, 2] (one student served, counter = 2)

Iteration 3: [2, 1] (one student sent back to the queue, counter = 0)

Iteration 4: [1] (one student served)

Iteration 5: [] (one student served)

The answer is 5.

Example 3

Starting with: [1, 1, 1, 1, 1, 1]

Iteration 1: [1, 1, 1, 1, 1] (one student served, counter = 1)

Iteration 2: [1, 1, 1, 1] (one student served, counter = 2)

Iteration 3: [1, 1, 1, 1] (one student sent back to the queue, counter = 0)

Iteration 4: [1, 1, 1] (one student served, counter = 1)

Iteration 5: [1, 1] (one student served, counter = 2)

Iteration 6: [1, 1] (one student sent back to the queue, counter = 0)

Iteration 6: [1] (one student served, counter = 1)

Iteration 6: [] (one student served, counter = 2)

The answer is 6.