Queue Interview Code basic methods made from struct Node

Question

Thanks for all the feedback, I optimized the code here.

Here I'm Writing a very simple Queue of struct Nodes with only these methods get_front(), get_back(), pop_front(), push_back(), print. I hope using namespace std; is okay, I will note it should not be used this way in production and I am only using the approach to write my code as quickly as possible so I can have more time to test and refactor while I discuss the code with my interviewer.

This is not for production and is to be treated as code that could be used in an interview or a quick and dirty prototype. I'm really curious about the approach I've taken here to keep track of the size, empty status, and back and front pointers, and use of only previous in my Node struct instead of next and previous pointers. I felt having both was not needed and previous makes more sense for a queue.

I'd like to know also if my member functions for the Queue have any edge cases I am not catching and any improvements I can make to run time efficiency. Anyway I can simplify this code further with c++11 features, shorter variable names or any other suggestions would be appreciated too.

Lastly if you optionally would like to share the memory/space complexity for my code that would be a huge help! I have noted some examples in the member data of my Node struct.

#include <iostream>
using namespace std;
struct Node
{
 int data; // 4 bytes for primatives
 Node* previous; // 8 bytes for pointers
 Node(int data) : data(data), previous(nullptr) { }
};
struct Queue
{
 Node* queue;
 int size;
 bool is_empty;
 Node* front;
 Node* back;
 Queue() : queue(nullptr), size(0), is_empty(true), front(nullptr), back(nullptr) { }
 string get_front() {
 if (front == nullptr) {
 return "empty";
 }
 else {
 return to_string(front->data);
 }
 }
 string get_back() {
 if (back == nullptr) {
 return "empty";
 }
 else {
 return to_string(back->data);
 }
 }
 void push_back(int data, Node* current) {
 if (current->previous == nullptr) {
 Node* n = new Node(data);
 current->previous = n;
 back = n;
 }
 else {
 push_back(data, current->previous);
 }
 }
 void push_back(int data) {
 if (is_empty) {
 queue = new Node(data);
 back = queue;
 front = queue;
 is_empty = false;
 }
 else {
 push_back(data, queue);
 }
 size++;
 }
 void pop_front() {
 size--;
 if (front->previous == nullptr) {
 front = nullptr;
 back = nullptr;
 delete queue;
 is_empty = true;
 }
 else {
 Node* dangling = front;
 front = front->previous;
 delete dangling;
 }
 }
 void print(Node* current, string queue_string) {
 if (current->previous == nullptr) {
 queue_string = to_string(current->data) + " " + queue_string;
 cout << queue_string << endl;
 }
 else {
 queue_string = to_string(current->data) + " " + queue_string;
 print(current->previous, queue_string);
 }
 }
 void print() {
 if (is_empty) {
 cout << "_____________\n\n";
 cout << "_____________\n";
 }
 else {
 cout << "_____________\n";
 print(front, "");
 cout << "_____________\n";
 }
 }
};
int main()
{
 Queue queue;
 queue.push_back(9);
 queue.push_back(8);
 queue.push_back(7);
 queue.push_back(6);
 queue.push_back(5);
 queue.print();
 cout << "front " << queue.get_front() << endl;
 cout << "back " << queue.get_back() << endl;
 cout << "size " << to_string(queue.size) << endl;
 cout << boolalpha << "queue empty status is " << queue.is_empty << endl;
 queue.pop_front();
 queue.pop_front();
 queue.pop_front();
 queue.print();
 cout << "front " << queue.get_front() << endl;
 cout << "back " << queue.get_back() << endl;
 cout << "size " << to_string(queue.size) << endl;
 cout << "queue empty status is " << queue.is_empty << endl;
 queue.pop_front();
 queue.pop_front();
 queue.print();
 cout << "front " << queue.get_front() << endl;
 cout << "back " << queue.get_back() << endl;
 cout << "size " << to_string(queue.size) << endl;
 cout << "queue empty status is " << queue.is_empty << endl;
}

Answer 1

I see a number of things that could help you improve your code.

Don't abuse using namespace std

Putting using namespace std at the top of every program is a bad habit that you'd do well to avoid. Know when to use it and when not to (as when writing include headers). If I were hiring, I'd prefer that the candidate actually write production quality code, rather than point out that the just-produced sample was not, even if they could articulate and justify the difference. After all, they're probably not hiring someone to produce non-production sample code, right?

Don't define a default constructor that only initializes data

Instead of writing this:

struct Queue
{
 Node* queue;
 int size;
 bool is_empty;
 Node* front;
 Node* back;
 Queue() : queue(nullptr), size(0), is_empty(true), front(nullptr), back(nullptr) { }
 // etc.
};

write this:

struct Queue
{
 Node* queue = nullptr;
 int size = 0;
 bool is_empty = true;
 Node* front = nullptr;
 Node* back = nullptr;
 // no need to write default constructor
 // other code
};

See Cpp Core Guidelines C.45 for details.

Use class rather than struct if there are invariants

The current Queue has pointers and size and is_empty members. Will everything still work if those are arbitrarily changed to random values? No, it will not. There are expectations that size and is_empty will always have the right values and the values of the pointers are critical to the operation of the data structure, therefore this must be a class and not a struct. See Cpp Core Guidelines C.2.

Eliminate redundant data

Rather than maintaining a separate is_empty data item, I'd suggest only keeping the size and defining a function instead like this:

bool is_empty() const { return size == 0; }

As per the previous advice, I'd also keep size private and provide a public access function if needed:

std::size_t size() const { return size_; }

Also, you don't really need both queue and front. The code would be both clearer and more compact if only front and back pointers were included.

Use the appropriate data types

Would it ever make sense to have a negative size for a queue? I'd suggest not, and so it would make more sense to have size be a std::size_t type.

Rethink the interface

If a user of this Queue were to invoke get_front() on an empty queue, I think it would be a much better interface to either throw an exception or to return an empty string rather than the special value "empty". It's also quite peculiar to push ints and then pop strings. That's not what I'd want. Here's how I'd write get_front:

int get_front() const {
 if (is_empty()) {
 throw std::out_of_range{"cannot get data from empty queue"};
 }
 return front->data;
}

Use const where practical

The current print() functions do not (and should not) modify the underlying object, and so both should be declared const:

void print(const Node* current, std::string queue_string) const;
void print() const;

I would also make the first variant private because the user of the class should not have any pointer to an internal structure.

Fix the bugs

There are several problems with pop_front. First, it doesn't check for an empty queue before decrementing the size which is an error. Second, it does not correctly update queue and leads to dereferencing freed memory which is undefined behavior.

Don't use std::endl if '\n' will do

Using std::endl emits a \n and flushes the stream. Unless you really need the stream flushed, you can improve the performance of the code by simply emitting '\n' instead of using the potentially more computationally costly std::endl.

Avoid to_string

The print function currently contains these lines:

queue_string = to_string(current->data) + " " + queue_string;
cout << queue_string << endl;

This creates another string and then prints that string which is not needed. Instead, just print directly:

cout << current->data << ' ' << queue_string << '\n';

Use all of the required #includes

The type std::string is used but its declaration is in #include <string> which is not actually in the list of includes.

Prefer iteration over recursion

Recursion tends to use additional stack space over iteration. For that reason (and often for clarity) I'd recomment writing print like this instead:

void print() const {
 std::cout << "_____________\n";
 for (const auto *item = front; item; item = item->previous) {
 std::cout << item->data << ' ';
 }
 std::cout << "\n_____________\n";
}

Even better would be to pass a std::ostream & argument to this function to allow printing to any stream.

Simplify your code

The recursive push_back function is much longer than it needs to be. I'd write it like this:

void push_back(int data) {
 auto temp = new Node{data};
 ++size_;
 if (back == nullptr) { // adding to empty queue
 front = back = temp;
 } else {
 back->previous = temp;
 back = temp;
 }
}

Note that this version assumes that the data members queue and is_empty have already been removed per the suggestions above.

Make test success obvious

The current test code exercizes the queue, but it doesn't indicate what is expected to be printed. I'd instead write both test scenarios and also the expected result so that it would be clear to anyone running the code whether everything was working as expected or not.

Make private structures private

Nothing outside of Queue needs to know anything about Node, so I'd strongly recommend making the definition of Node private within Queue.

Don't leak memory

This program leaks memory because the Queue's destructor doesn't free all resources. This is a serious bug.

Consider using a template

A queue is a fairly generic structure that could hold any kind of data if the class were templated, and not just an int.

Consider possible uses

For any code production, but especially if you're in an interview, think about how the class is being used and whether there are any restrictions or limits inherent in the design. For example, think about copy and move operations. If you write this, does the code do the right thing?

Queue queue;
queue.push_back(5);
queue.push_back(6);
queue.push_back(7);
auto a_copy{queue};
a_copy.pop_front();
queue.print();
a_copy.print();

Also consider multithreaded code. Would it be thread-safe to push from one thread and pull from another? If not, what would be needed to make that work?

Don't make platform assumptions

Although it doesn't adversely affect the code, the assumptions about data sizes in the comments for Node are simply incorrect on my machine and would be a red flag in an interview.

Answer 2

using namespace std;

Possibly already failed the interview

---

Note: I added an underscore here to avoid another warning that your code generates, namely variable shadowing

struct Node
{
 int data; // 4 bytes for primatives
 Node* previous; // 8 bytes for pointers
 Node(int data_) : data(data_), previous(nullptr) { }
};

Those size assumptions are not necessarily true (also note the typo).
Depending on the compiler and warning levels you might get padding warnings for the Node struct as well as for this part:

struct Queue
{
 Node* queue;
 int size;
 bool is_empty;
 Node* front;
 Node* back;
 ...

e.g.:

warning: padding struct 'Node' with 4 bytes to align 'previous' [-Wpadded]
warning: padding struct 'Queue' with 3 bytes to align 'front' [-Wpadded]

Which is the compiler telling you that it will align things in a way that results in wasted space in the middle of your structs.

---

Queue() : queue(nullptr), size(0), is_empty(true), front(nullptr), back(nullptr) { }

If you don't intend to parameterize your Queue then you don't need to initialize in the ctor.
Instead you can initalize directly like so:

struct Queue
{
 Node* queue{nullptr};
 int size{0};
 bool is_empty{true};
 Node* front{nullptr};
 Node* back{nullptr};
 ...

---

if (front == nullptr) {

You compare to nullptr in various places. Don't. Instead do e.g. !front.

---

At a glance this seems to leak memory as there is no cleanup code and you don't use smart pointers.

---

Apply const where appropriate, at least for the print functions.

• greg: Thanks yuri this was really helpful. Only have a few questions, everything else is really clear. Also I'll consider explicitly calling the namespace in an interview to make sure I show up at my very best. I don't fully understand the padding issue and how to fix it, can you explain more? Why should I uses void print() const { } or consider using const in other areas?
• yuri: @greg (1) For questions about const refer to the other excellent reviews. (2) In your case the padding issue could be fixed by manually inserting padding to satisfy the compiler (e.g. char padding[4] / char padding[3] at places where the compiler complained). More1 about² padding³
• greg: That's so interesting, firs time I've seen a warning like this. Out side of using the -W flag is there any way to notice a padding issue just by looking at the code?
• greg: Also Node(int data_) I noticed the use of underscore in the Node param, is this a style choice or a common practice?
• yuri: (1) Sorry about the underscore. I left it in when I was refactoring your code a bit. It hides another warning, namely that your variable is shadowed. My personal preference is to append a suffix (underscore) to parameters having the same name as a member to evade this. (2) Yes if you rewrite your code please ask another question with the new code and maybe linking to this question.

Answer 3

To expand on the other review(s), you should pay attention to const correctness.

• The functions get_front, get_back and both overloads of print should be made const as they don't modify the object. This increases readability and protects from unintended mistakes.

• There is no need to take the argument by-value in print. You can rewrite this to e.g.,

  void print(Node* current, const string& queue_string) const
  {
   const std::string qs = to_string(current->data) + " " + queue_string;
   if (!current->previous) {
   cout << qs << endl;
   }
   else {
   print(current->previous, qs);
   }
  }
  

• You need to include <string> because you use std::string.

• Ultimately, you should properly encapsulate the data and methods in your class (i.e., not use a struct that publicly exposes everything).