Linked-list-based stack and queue

Question

This is my first attempt at building a linked-list-based stack and queue. It is the result of ~90 minutes of trying to implement some of what we're being taught in Algorithms class.

I would like feedback on possible optimisation and oversights. I did try to segment and comment the code the best I could.

This was written and tested on DevCpp, just in case it contains certain quirks or behaves differently on other IDEs.

#include<iostream>
#include<cstdlib>
#include<string>
using namespace std;
class charNode //basic node containing a character and a single link
 {
 private: 
 char val;
 charNode* next;
 public :
 charNode();
 charNode(char c);
 void setVal(char c);
 void setNext(charNode* n); 
 char getVal();
 charNode* getNext(); 
 };
class charStack //prototype for stack of char nodes
 {
 private:
 charNode* head;
 int counter;
 public :
 charStack(); //default constructor
 charStack(char c); //constructor that sets a value
 ~charStack(); //destructor
 void setHead(charNode* h); //assigns a pointer to the top node of the stack
 charNode* getHead(); //returns the address of the top node in stack
 void decCounter(); //decrements counter of nodes
 void incCounter(); //increments counter of nodes
 int getCounter(); //returns the number of nodes in stack
 void push(char c); //adds a node to the top of the stack
 char pop(); //removes top node and returns its character value
 int search(char c); //returns position of character in stack, or 0 if not found. 
 };
class charQueue //prototype for queue of char nodes
 {
 private:
 charNode* rear;
 charNode* front;
 int counter;
 public :
 charQueue(); //default constructor
 charQueue(char c); //constructor that initializes the queue with one node
 charQueue(char r, char f); //constructor that initializes the queue with two nodes
 ~charQueue(); //destructor
 void setRear(charNode* r); //assigns a pointer to the rear of the queue
 void setFront (charNode* f); //assigns a pointer to the front of the queue
 void incCounter(); //increments counter of nodes
 void decCounter(); //decrements counter of nodes
 charNode* getRear(); //returns the address of the rear node in queue
 charNode* getFront(); //returns the address of the front node in queue
 int getCounter(); //returns the number of nodes in queue
 void add(char c); //adds a node to the rear of the queue
 char remove(); //removes a node from the front of the queue and returns its value
 bool isEmpty(); //checks whether the queue is empty
 int search(char c); //returns position of character in queue, or 0 if not found. 
 };
// Implementation for methods in the node class
charNode::charNode() {this->next=NULL;}
charNode::charNode(char c) {this->val=c; this->next=NULL;}
void charNode::setVal(char c) {this->val=c;}
void charNode::setNext(charNode* n) {this->next=n;}
char charNode::getVal() {return this->val;}
charNode* charNode::getNext() {return this->next;}
//end of node method implementation
// Implementation for methods in the stack class
charStack::charStack(){this->head=NULL; this->counter=0;}
charStack::charStack(char c) {this->head= new charNode(c); this->counter=1;}
charStack::~charStack() 
 {
 charNode* tmp=this->head;
 while(1)
 {
 if(tmp==NULL) break;
 head=head->getNext(); 
 delete tmp;
 tmp= head;
 }
 this->counter=0;
 }
int charStack::getCounter() {return this->counter;}
charNode* charStack::getHead() {return this->head;}
void charStack::decCounter() {this->counter--;}
void charStack::incCounter() {this->counter++;} 
void charStack::setHead(charNode* h) {this->head=h;} 
void charStack::push(char c) 
 {
 if (this->head==NULL) {this->head=new charNode(c); this->counter=1; return;}
 charNode* tmp= new charNode(c); 
 tmp->setNext(this->head);
 this->head=tmp;
 this->incCounter();
 //diagnostic cout << endl<< "pushed (" << c << ")! Counter= " << counter << endl;
 }
char charStack::pop()
 {
 if (this->head==NULL) return ' ';
 charNode* tmp= this->head;
 this->head= this->head->getNext();
 char res=tmp->getVal();
 delete tmp;
 this->decCounter();
 //diagnostic cout << endl<< "popped (" << res << ")! Counter= " << counter << endl; 
 return res;
 }
int charStack::search(char c)
 {
 charNode* tmp= this->getHead();
 bool found=false; int loc=0;
 while((tmp!=NULL)&&(!found)) {loc++; found=(tmp->getVal()==c); tmp=tmp->getNext();}
 if(found) return loc; else return 0; 
 }
// end of stack method implementation
// Implementation for methods in the stack class
charQueue::charQueue() {this->rear=NULL; this->front=NULL; this->counter=0;}
charQueue::charQueue(char c) {rear=new charNode(c); front=rear; counter=1;}
charQueue::charQueue(char r, char f) {rear= new charNode(r); front= new charNode(f); rear->setNext(front); counter =2;}
charQueue::~charQueue() 
 {
 while(rear!=NULL)
 {
 charNode* tmp=rear->getNext();
 delete rear;
 rear=tmp;
 }
 front=NULL; 
 counter=0;
 }
void charQueue::setRear(charNode* r) {this->rear=r;}
void charQueue::setFront (charNode* f) {this->front =f;}
charNode* charQueue::getRear() {return this->rear;}
charNode* charQueue::getFront() {return this->front; }
void charQueue::incCounter() {this->counter++;}
void charQueue::decCounter() {this->counter--;}
int charQueue::getCounter() {return this->counter; }
void charQueue::add(char c) 
 {
 if(rear==NULL) {rear= new charNode(c); front=rear; counter=1; return;}
 charNode* tmp=new charNode(c); tmp->setNext(rear); rear=tmp; this->incCounter(); 
 }
char charQueue::remove()
 {
 if(rear==NULL) return ' ';
 if(this->counter==1) {char res=this->rear->getVal(); this->~charQueue(); return res;}
 charNode* tmp=rear;
 while(tmp->getNext()!=front) tmp=tmp->getNext();
 char res=front->getVal(); 
 delete front; front=tmp; front->setNext(NULL); this->decCounter();
 return res; 
 }
bool charQueue::isEmpty() {return this->getCounter()==0;}
int charQueue::search(char c)
 {
 charNode* tmp= this->getRear();
 bool found=false; int loc=this->getCounter()+1;
 while((tmp!=NULL)&&(!found)) {loc--; found=(tmp->getVal()==c); tmp=tmp->getNext();}
 if(found) return loc; else return 0; 
 }
bool isCap(char c)
 {
 return (((int)c>=(int)'A')&&((int)c<=(int)'Z')); 
 }
//end of queue method implementation
//main 
int main()
{
 //using stack of char nodes to reverse a string input
 charStack* s=new charStack();
 string name; cout << "enter your name: "; cin >> name;
 for(int i=0; i<name.length(); i++) s->push(name[i]);
 cout << "character to find: "; char f; cin >> f; int loc=s->search(f); 
 if(!loc) cout << "character not found!" << endl; 
 else cout << "character found in position #" << s->getCounter()-loc+1<< endl;
 cout << "your name reversed: "; while(1) {char c=s->pop(); if(c==' ')break; cout<<c;} cout << endl;
//using a queue of char nodes to detect and display capital letters in a string input
 string pass; cout << "Type in a squence of capital and small letters:"; cin >> pass;
 charQueue* caps=new charQueue();
 for(int i=0; i<pass.length(); i++) if(isCap(pass[i])) caps->add(pass[i]);
 cout << "capital character to find: "; cin >> f; loc=caps->search(f);
 if(!loc) cout << "character not found!" << endl; 
 else cout << "character is the capital #" << loc<< endl;
 cout << "The string you entered has these capital letters: "; while(!caps->isEmpty()) cout << caps->remove(); cout << endl;
//end of program
 system("pause"); return 0;
}//end of main

• forsvarir: Your indentation is somewhat interesting, is that the way your code looks in your editor?
• blitzilla: @forsvarir its how DevCpp adds spaces, I just use tabs, and it adds them unevenly for some reason. Any tips welcome.

Answer 1

Some tips that I think can improve your code:

• As the data encapsulation you should not return the actual location of your stack in the memory because the user of your stack can corrupt the mechanism of the stack. Instead you should return the data included in the node(Whether it is a char, int, or any other type)(I mean charNode* getHead();)
• Instead of using a while(true) loop with a break; statement in its scope try to figure out a good condition for your loop and avoid using break; statements in scopes. (I mean the while in the constructor of your charStack)
• If any unwanted condition is happened try to aware the user of your class not by returning a data like any other normal data. In other words in your pop() method if the stack is empty and a pop action wants to be executed you return the space character that is ambiguous if actually the space character is in the stack.

Answer 2

Design

You should not expose pointers in C++.

void setHead(charNode* h);
charNode* getHead();

Pointers have no ownership semantics associated with them. Ownership is the concept of who is responsible for deleting a pointer (releasing a resource). If you have a pointer you can't tell (without reading the code/documentation) who is responsible for freeing it (or how to free it or if it is even freeable).

In the above interface I can quite easily break the program by doing:

charNode x('R');
list.setHead(&x); // pass the address of 'x' rather than
 // dynamically allocated object.

If you are using dynamically allocated memory you should be using some form of smart pointer to indicate the ownership of the object. If the object is not dynamically allocated then you can use a reference rather than a pointer.

But in this case I would not even expose this interface as it introduces coupling (by exposing the internal implementation of the class).

Your internal structure charStack is exposed as a public class and you return a pointer to this type of object via getHead(). This means you will need to support both of these indefinitely. This may prevent you from improving the class in the future (as both of these will need to be maintained to keep old code working).

The internal structure of a class should be kept private. This will reduce coupling with external code and allow you to change the underlying implementation if you discover a better technique without having to modify any of the code that uses your class.

Naming conventions. There is no absolute standard for C++ (so take as you require). But a common convention is that user defined classes begin with an upper case letter. The names of objects (variables/functions) begin with a lower case letter. This makes it easy to quickly identify what is a type and what is an object (which is very useful in a language where type information is paramount).

Your comments are bad. Comments need to tell me something that is not obvious from the code. Also the code should be self documenting. Thus usually comments should tell me why (or describe in detail the algorithm that is being used). I can read code so the comments should not repeat the code (otherwise you have to maintain the code and the comments to make sure they say the same thing (and that is extra work)).

The worst thing in development is finding code that does one thing and the comments say something else. Which is correct (the comments or the code). Which do I fix?

So minimize your comments and only write stuff I can not tell from reading the code.

Code Review

Why are you publically exposing methods that can break the state of the object.

 void decCounter(); //decrements counter of nodes
 void incCounter(); //increments counter of nodes

I can increment/decrement the count of nodes, without changing the actual number of nodes in the class?

In this case it's not bad; but:

char pop(); //removes top node and returns its character value

But in the general case where the return value can be any type. This is not an exception safe method. This is why in standard containers pop() simply removes the top item, and there is another method top() for getting a copy of the top element. You may want to copy this pattern to be consistent with standard types.

Don't use this

charNode::charNode() {this->next=NULL;}

The need to use this is only required if we have shadowed variables. Shadowed variables are dangerous as you can accidently forget to use this and then you will be changing the wrong variable (and how do you tell if you should be using a local or a member variable if they have the same name)!

Shadowed variables are bad practice and can be detected by the compiler (and thus removed). When you have removed shadowed variables (because you code compiles with no errors) there is no longer any need to use this.

The use of this only creates problems so don't use it.

Only put one statement per line.

void charQueue::add(char c) 
{
 if(rear==NULL) {rear= new charNode(c); front=rear; counter=1; return;}
 charNode* tmp=new charNode(c); tmp->setNext(rear); rear=tmp; this->incCounter();
}

This is hard to read (and its a very short function).

void charQueue::add(char c) 
{
 if(rear==NULL)
 {
 rear= new charNode(c);
 front=rear;
 counter=1; 
 return;
 }
 charNode* tmp=new charNode(c);
 tmp->setNext(rear);
 rear=tmp;
 this->incCounter();
}

Now that I can see the code. I see a lot of common elements (and I am not sure I believe it is correct). Looks like the tmp element is being set as the second last element in the list and rear points to this element.

• blitzilla: Thanks for the pointers. In regards to exposing the methods that control the counter, that was a bad mistake on my part, I only made them in case I needed them in other methods (which is in itself stupid since they're a single line each.), in any case, they should have been declared private not public.
• blitzilla: As for the last point, the add() method creates a new node using the tmp pointer, links it to the previous last node, and then makes it the rear of he queue by moving the rear pointer onto it. I should probably find a less convoluted way of implementing the add() method.