Getting Started

Synopsis

  • Read the lab writeup on Canvas.
  • This lab is due on October 17, 2017 at 23:59:59.

Requirements

  • Arduino Due
Synopsis
Ah pointers. This is a valuable skill to know in both C and in C++ because you will be using them in your future classes (140, 302, 360, and higher). To practice them, you will be making an extremely simplified version of a stack. I'll go more in depth about what a stack is down below, and how to use one in C++. But be aware that in this lab, you will be building a simplified one yourself, without #include <stack>... you won't use that until CS140..
What is a stack?
Think of it like a "stack" (get it?) of cards. Let's set some rules to this game:
  • You can only draw from the top of the deck ("popping" off the stack).
  • You are only allowed to put a new card on the top of the deck ("pushing" to the stack).
Therefore, if this deck was empty and you started putting cards in the deck, the very first card of the deck placed at the bottom will also be the last one out. Because if you put a card above that first one, you'd have to draw that one before you can draw the first card. A stack is a FILO (First-in, Last-out) data structure.

C++ Example

NOTE: Again, this is just to demonstrate a stack. You will not be using this in your lab. I know some of you like to copy and paste, but this definitely isn't going to be worth much in Arduino.
#include <iostream>
#include <stack>

using namespace std;

int main() {
	stack<int> s;
	int val;
	s.push(1);
	s.push(2);
	s.push(3);
	
	//Loop until the stack is empty
	while (!s.empty()) {
		val = s.top();       //Get the value at the top of the stack
		s.pop();             //Pop off the stack
		cout << val << endl; //Print out
	}
}
The program will push "1", "2", and "3" to the stack "s". Then it will pop them out of the stack, printing each one popped in the process. The output is:
3
2
1

"But Clara, why the reversed order?"

Remember that a stack is FILO (First-in, Last-out). When pushing, "1" goes in first. "2" is placed on top of it. Then "3" is placed on top of "2". When we pop, we take the value on the top and remove it. "3" is on the top, so it's the first one we encounter on the stack. After it has been removed, "2" is next, followed by "1".
Pointers
Stacks are fun once you master them. But now we will be discussing about memory management at its simplest... pointers. If you are taking CS140 or CS302 sometime soon, you're required to use pointers in those classes (They kind of force it in their lab assignments).

So let's think in C++ here, since you'll be using that for a while. Let's declare an array of size 4.
#include <iostream>
using namespace std;
const int ARR_SIZE = 4;
int main() {
	int arr[ARR_SIZE]; //Make an array size 4.
	arr[0] = 1;
	arr[1] = 9;
	arr[2] = 27;
	arr[3] = 42;
}
Now this code should be trivial at this point. Here's a (poorly made) table of what's going on:

arr[0] arr[1] arr[2] arr[3]
1 9 27 42

Makes sense right (This is from CS102)? Great! Now let's see "how" it works, since that is what is important here.

When you declare a variable, you are telling the computer to assign that variable somewhere in memory. Therefore, each variable has some address assigned to it. You can get this address by using the "address-of" operator (&). For example:
int a = 0;
cout << &a; //Print out the address of "a".
Now, the output of this will be different pretty much every time you run the application. The reason why is because the Operating System gives a random address every time. Your program basically asks the Operating System (really nicely) for memory to allocate the variable. The Operating System, then, is like "Hmm... ok this address looks good, here you go".

It should be something like this:


"...Your point?"

Right, right... so here's where it relates. Let's look at that table again... but let's also look at some example addresses.

arr[0] arr[1] arr[2] arr[3]
Value 1 9 27 42
Address 0x1000 0x1004 0x1008 0x100C

When we defined int arr[ARR_SIZE];, all memory in this array is guaranteed to be right next to each other. It's guaranteed to be "contiguous". So because these are integers, they take up 4 bytes. So arr[1] is 4 bytes ahead of arr[0].

Because of this, we can grab a pointer to the first element of the array, and then access the others easily. So let's use a pointer for the first time ever.
#include <iostream>
using namespace std;
const int ARR_SIZE = 4;
int main() {
	int arr[ARR_SIZE]; //Make an array size 4.
	arr[0] = 1;
	arr[1] = 9;
	arr[2] = 27;
	arr[3] = 42;
	
	int* p = &arr[0];   //Access arr[0], and grab the address that points to it.
	cout << p << endl;  //Print out the address
	cout << *p << endl; //Dereference the value at address "p"... which is "arr[0]". Print.
}
So the code will, as the comments say, grab the address pointing toward arr[0], print out that address... and then dereference that pointer to get the value at that location. The value at that location is arr[0]'s value. Then it will print out that value.

Here's the two operators, in case you are confused:
  • & (Address-of Operator) - This will grab the address that holds a value.
  • * (Dereference Operator) - This will take an address, go to it, and grab the value at that address.
What gets confusing is that "*" can also mark a variable as a pointer (hence int *a;)... which holds an address. But yet it is an operator that involves using the address to get a value. Blame the C++ designers for that.

Now for the magic

Let's get arr[1] with pointer arithmetic.
#include <iostream>
using namespace std;
const int ARR_SIZE = 4;
int main() {
	int arr[ARR_SIZE]; //Make an array size 4.
	arr[0] = 1;
	arr[1] = 9;
	arr[2] = 27;
	arr[3] = 42;
	
	int* p = &arr[0];   //Access arr[0], and grab the address that points to it.
	p++;                //Increment p by sizeof(int)
	cout << p << endl;  //Print out the address
	cout << *p << endl; //Dereference the value at address "p"... which is "arr[0]". Print.
}
Stop the presses! The only change here is that p++. But what does it do? You're used to it in for loops where it increments the value by 1. You're correct there. However, the rules of the game changes here. The pointer will increment by the size of the data type the pointer represents. Since the type of the pointer is an int, it will increment by the size of an int, which is usually 4 bytes.

As expected, it prints out "9".
9

The Lab
Your mission, should you choose to accept it (you better, or else you'll fail), is to write a dumbed down version of a stack. You will have STACK_SIZE already defined for you. You will have an array of that size, and start adding in entries from the end of it. You will have a pointer pointing to the current position of the stack. When you push, set the value at that point in memory (dereference, and then set) to the value pushed. Then decrement the stack pointer. Whenever you are popping, grab the value in the stack, then move the stack pointer forward. You should be able to figure out the rest.

Start:
[ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ]

Push (5):
[ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][5]

Push (4):
[ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][4][5]

Pop (4):
[ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][5]