Categories : C

 

LIFO is short for Last In First Out, otherwise known as a stack. LIFOs are data structures that are very useful in programming, as they can provide a way to store data in your program relatively securely with a decent retrieval method. Stacks are a fundamental part of programming. Those familiar with C’s memory management system know that it uses a stack (but none of those people would want to read this tutorial), and those who are familiar with Machine or Assembly language know that there is a stack native to the code.

Why a Stack?

As I’ve said before, a stack is a data structure that provides a pretty secure and stable method of storing data inside your programs. It is stable and secure because it has only one point through which code can enter and exit through the structure. This means that when you put something into the structure, you can’t implicitly overwrite it (Though there are ways of doing this, but you would have to actively try). So your data is stored when you push it onto the stack, and it won’t go away until YOU retrieve it.

The other side of this coin is that there is only one way out of the stack, and once again, you do the retrieving through the same “hole” that you do the placing, so unless you tell the program to pop data out of the stack, a misplaced incriment won’t feed the wrong data to one of your methods.

Unlike Assembler, C doesn’t provide a stack for us, so we have to create one ourselves. Don’t get too alarmned though… the code is extremely simple, and if you’re creative, I’m sure that you’ll see a myriad of ways of expanding the skeletal example that I’ve given below. Before I get to the code, let me explain what a stack is in principle.

How a Stack Works

I’m sure that you’ve been to a caffeteria at some point in your life, and I’m also willing to bet that you’ve seen those spring-loaded tray mechanisms. You put one tray on top of the others, and push all the other trays down one as you push your tray on to the stack of trays. Then, someone else wants a tray to put their food on, and grabs the top tray, popping it off of the stack of trays, which all pop up one tray. Our LIFO/Stack works in the same way. Consider this example… I have a box, call it box one. It looks like this:

|—|
| 1 |
|—|

But then for the hell of it, someone else comes along and gives me another box. because my apartment’s a mess, I have to stack the boxes, so I put my second box on top of the first box, and so now it looks like this:

 

|—|
| 2 |
|—|
|—|
| 1 |
|—|

Now my cat is happy, because she has something taller to stand on. My sadistic buddy then comes along, and insists that I take yet another box from her, so I put that on top of the other two, and now my stack of boxes (minus the cat) looks like this:

|—|
| 3 |
|—|
|—|
| 2 |
|—|
|—|
| 1 |
|—|

Woah! This stack of boxes is getting to high to manage in my one-room, low ceiling apartment. I have only one choice… I must throw away one box:

|—|
| 2 |
|—|
|—|
| 1 |
|—|

There, much better. My stack of boxes is only two boxes high. It’s not too much clutter, and the cat is happy again because she can jump up to the top and presume that she’s the greatest thing since sliced bread.

The moral of the story is, the LAST thing you put on a stack is the FIRST thing that you will remove from the stack. By attrition the first thing you put in the stack is the last thing that comes out of the stack. Congratulations, you now know the basic principles of a stack. Now lets look at some code…

#include 

#define MAX_SIZE 10

char a[MAX_SIZE];
int top = -1;

int isempty()
{
 return top == -1;
}

void push(char c)
{
 a[++top] = c;
}

char pop()
{
 return a[top--];
}
There, look at how nice and simple that looks, and genuinely is. With just a few lines of code, we’ve created a stack that, while limited in scope, is expandable. When you learn more, you can put this into a struct, make the buffer a linked list, etc. But for now let’s just focus on understanding what is going on here.

#define MAX_SIZE 10
Here I’ve defined a static variable. I’ll use this variable as the buffer size, so I don’t want something else to come along and change it mid-operation. If 10 is too small, you can put in whatever number you like.

char a[MAX_SIZE];
This is where we create the buffer. Yes, it is an array that is designed to hold characters. Because a stack needs some kind of underlying structure, and because I’m trying to keep this example simple, I’ve used an array, but I could have just as easily used a linked list… well okay, so that would have been a little more difficult.

int top = -1;
Pay very close attention to this, because it’s very important. As I’ve said before, the stack has 1 entry/exit point. Top is that point. It is a pointer (NOT A POINTER TYPE) to the top of the stack, which is the only place to put things onto the stack or get them from the stack. By initializing top to -1, we set the stack at an unuseable point. Refferencing a[-1] is not a legal operation. Therefore, to be able to access the stack, we have to put something into the stack (which will incriment top).

int isempty()
This is a simple function definition. But note that the return type is int even though what we’re looking for is a boolean value. Unlike Java, C provides no boolean type, so you kind of have to fudge it.

return top == -1;
Yes, the function is that simple. This function checks to see if the stack is empty, and relies on this boolean operation to do it. If top is the same as its initial value, than either we haven’t put anything on the stack (and thus it is empty), or we’ve removed everything from the stack (and thus it is empty). The function return and integer true or integer false depending on the value of top. I told you that number would be important.

void push(char c)
Here we define function push with a return type of void, and with a single character as a parameter.

a[++top] = c;
I just said a mouthful. Okay, let me explain this as it happens. top gets incrimented; because the pre-incriment operator has precedence, the first thing that happens is that top is incrimented. If this is the first push operation, top now equals 0. a at top gets c; Because top is now a legal array refference number, we can put something into the buffer. This thing happens to be c, which is the character that the method takes as a parameter. The call for this would look like this: push(‘x’);. Now we actually have something in the buffer, and isempty() would return false.

char pop()
Yep, another function definition. Pop is the method that we’ll use to get stuff out of the stack. Thus, it returns a char.

return a[top--];
And here is our return ststement that actually gets the first thing out of the stack. Here’s how it works: a at top is returned; Whatever was stored in a at the address of top is returned to the function that calls pop(). top is decrimented; then top is decrimented, so that it points to the next-highest item in the stack. If we’ve just popped the last item in the stack, then top is equal to -1 and the stack is empty.

Well, there you have it, a stack. Realize that this stack is a very elementary one. If you’re going to expand upon this example, you should definitely explore changing the underlying data structure to a linked list, as that would give you more flexability in what you can push onto the stack. I would also recommend learning a little about using structs, as you may need more than one of these to work at once. I leave those tutorials to another day.

 Posted on : August 22, 2014
Tags:

You might also likeclose