Implementing a Queue

There are many ways to hold a bundle of data in memory. Novice programmers will be aware of the array, a data structure that holds data in sequence within a block of memory. The key feature of an array is the use of indices assigned to each item in the array. This allows us to quickly recall items from memory. We can even dynamically allocate memory to the array using C++'s new and delete keywords.

In programming, just as in economics, there is no such thing as a free lunch. We pay for the speed of an array by losing the ability to change the amount of data held in an array. If we create an array to hold n elements, there is no way to make it hold n+1 elements without allocating new memory. If, for instance, we create an array holding n ints, and we want it to hold just one more int (n+1), the total cost of the operation is 2n+4. That is, if we had 100 ints and we want it to hold 101 ints instead, we would need 804 bytes of memory - 400 for the first array, 400 more for the first 100 intes of the second array, and 4 more for the last int.

If we are willing to sacrifice a bit of speed, we can use linked lists to structure our data instead. Linked lists contain 'nodes' which hold data and pointers to the next node in the list. There are actually many types of linked lists, but for now, let's take a look at the queue list. As a data structure, a queue replicates the behaviour of a queue in real life - like the lineup at a drive through or at an amusement park. Nodes move from the back of the queue to the front, and at the front, they are deleted from a queue.

So how does this look in C++? Let's take a look:

//
//  main.cpp
//  Queue
//
//  Created by Natesh Mayuranathan on 11-10-12.
//

#include <iostream>

using namespace std;

class Queue; 

class QNode {
  int _data;
  QNode* _next;
  
  QNode(int data, QNode* next = (QNode*)0){
  
    _data = data;
    _next = next;
    
  }
  
  friend class Queue;
  
};


class Queue{ 
  
  QNode* _front; 
  QNode* _back;
  QNode* _current;
  
  public:
  
  Queue(){
    _front = (QNode*)0;
    _back = _front;
  }
  
  void add(int data){
    
    //create a new node item and a pointer to it
    QNode* temp = new QNode(data); 
    
    //if the list is empty, add temp to the front of the list
    if(isEmpty()) {
      _front = temp;
    }
    
    //if the list is not empty, point back's next to temp
    if (_back) {
      _back->_next=temp;
    }
    
    //assign temp to back
    _back = temp;
}//add a node to the list 
  
int remove() {
  int val = _front->_data;
  delete _front;
  _front = _front->_next;
  return val;
}//remove node from the list
  
bool isEmpty(){
  return !_front;
}
  
~Queue(){
  while (!isEmpty()) {
    remove();
  }
  
}
  
};

int main (int argc, const char * argv[])
{

  Queue q;
  
  for (int i=100; i<1000; i+=100) {
    q.add(i);
  }
  
  while (!q.isEmpty()) {
    cout << q.remove()<<endl;
  }
  
  return 0;
}

RapidSVN: A Primer for the rest of us

I recall once speaking to a friend in a concert lineup. Both of us being the nerds that we were, we'd been in an excited conversation about Perl. It somehow dawned on another person in line that we were talking about something or other related to computers, and in the interest of conversation asked, "So you guys are in IT, huh?" at which my friend bristled. His reply was simply, "I suppose...but don't ask me to fix your computer."

I often recall this comment in the midst of coding or simply using an application when what I think ought to be a simple task escapes me. It makes me feel frustrated and vulnerable. Most recently, I was setting up and making use of the revision control program, RapidSVN, and ended up having a great deal of trouble creating a directory structure within my branch as well as being able to get what I needed out of the repository. I spoke to Fardad after class (as this happened during the class where he was introducing SVN in detail, as well as the process involved in collaborative coding with SVN), and we arranged the needful.

Afterwards, I found myself with some free time during the afternoon, and decided to boot up RapidSVN and try again. This time I was more successful, and so I decided to create a step-by-step pseudo-transposition of the steps provided on the OOP344 wiki for Mac users who shall likely end up with RapidSVN. It is (at least for me) a bit slow, but it is functional and handy, and with a little practice, one can get used to it as well as SVN in general.

Get RapidSVN (of course)

From the OOP344 wiki, here's a link to the disk image. It's one of the simpler ones that simply includes the executable for you to copy to your Applications folder. Peanuts.

Create a folder to house a working copy of the repo on your home computer.

Another easy step: simply use Finder or Terminal to create a folder that's named logically to which RapidSVN can route a working copy to. Terminal may be preferable, because you can copy the path, which you'll need for the next step

Add the repository to RapidSVN

Ready to sink your teeth into RapidSVN? Launch the app. 

Fairly Spartan interface. I'll go through some of the more relevant (to us) commands, but first click on Bookmarks.

You'll get a list of options. Add Existing Working Copy, Add Existing Repository, Switch Repository URL, Edit Bookmark and Remove Bookmark. We're going to select Add Existing Repository.

Add your SVN account URL. You will have to provide a username and password. Obviously, this can refer to any applicable repository. Check out your bookmarks tab. If the add was successful, your repository is now available to browse! Also, you will no longer have to log in to the repo (from the current workstation). Click on the account in the Bookmarks tab.

The directory structure will be familiar to you, but it's incomplete. Now to make it feel a bit more like home (I guess). The next two steps can be done in any order, but if you perform them as presented, you'll save yourself the trouble of having to merge multiple times.

Create the directory structure Pt. 1 - create your workspace

It's important to be careful of this; it's where I got into a bit of trouble, mostly because of my overzealousness and because, admittedly, I didn't listen as closely as I ought to have. I entered the Modify menu and attempted to create a new directory, for which we don't have permissions. Eep. Here's a tip for you: just don't open the Modify menu at all. I was about to type, "in the root", but I think using the contextual menus is more reliable in almost all cases. Anyway, open up the branches directory.

Right-click anywhere inside the whitespace. Select Make directory A prompt shows up which allows you to name it. Do so, and click OK. The message that appears tells you that your action has resulted in a commit. I provided a comment. I suppose you should, too.

Create the directory structure Pt. 2 - create a task folder

Follow the same instructions as in the previous step to create a folder called task inside your workspace. This is simply a placeholder; you will be renaming it as need be.

Create the directory structure Pt. 3 - branch the trunk into your workspace

Go back to the root and right-click trunk. Select copy, open up your branch, and paste. And that's it, your workspace is complete...on the repository. Your workstation still doesn't have your directory structure.

Merge workstation with repository

Click on the Repository menu and click merge. Enter the path/to/your/working/copy, and click OK. Your workstation now has the same directory structure as the repo.

Follow Steps 4-6 from the Development and Submission steps using SVN entry on the OOP344 wiki

Here they are, starting from step 4.

And that's that. Hopefully this reference proves to be handy to coders using revision control on OS X.

Addendum: Useful hints

If the idea of having to create a new working copy is daunting to you, consider storing the one from your working computer on  the always handy Dropbox application. You can be fairly assured that you have the latest version of the code in case you're working on a computer other than your own this way, and it acts as a backup in disaster scenarios.

One other thought might be to use RapidSVN to version control files on your own hard drive if only to practice with the interface and version control example code of your own. This may also be great for rolling back extreme changes to your code. You can accomplish this by using the svnadmin create command as follows:

~ User$ svnadmin create /path/to/repository

And you're set!

Coda

Any error indications, comments or suggestions would be appreciated. I want this to be as accurate as possible. Thanks!

(Postscript: Sorry about the image sizes messing with the layout. Still working out the kinks in the Blogger platform)