[C] Building your first stack 12-12-2014, 09:00 PM
#1
Firstly, before you read this tutorial, you MUST understand the following languages and concepts:
Alright, stacks are a REALLY commonly used structure, but some people have hard times understanding how they are created and used.
Lets get into the concept. Imagine you have a table
_______
| |
Now, we have some empty plates, so we "stack" them onto the table
-- <- first plate
_______
| |
and then another
-- <- second plate
-- <- first plate
_______
| |
and so on. Now, removing the plates, we get them back in the REVERSE order, so we remove the second plate, and then the first plate.
"Why would we do that? cant we just pick up the bottom one?"
No. Imagine that there are 65535 plates. Youre not doing that.
Okay, that was a little spoonfed, but, we can get into how it works in code now.
Every stack has the following basic methods:
init
Init is the method we will use to create the stack, set up how big it is, whatever.
That would be like deciding how high the ceiling is for our table.
push
Push is the method we are going to use to add items to the stack, it is very simple.
pop
Pop is the method we use to remove items from the stack. It is another simple function, but the concept gets really weird sometimes.
destroy
Destroy is the method used when we no longer need the stack. This will de-allocate everything we created in init.
Alright, well, we have a basic understanding of what we need to do, now how do we do it?
I am going to use C for this tutorial, so that you guys get a good grip on what is going on. My next tutorial (if this one rates well) will be making a C++ class for our C stack.
First thing we need is to figure out what type of data we want to store. Let's make our stack hold integers.
Next, we have to define what a stack is, we will do so using a structure.
Breaking that down:
data
data is what will actually store our stack elements once they are pushed on. That one doesnt need a lot of explaining
stack_pointer
the stack pointer holds the next open spot in the stack. If our stack is empty, it will be 0, if it has 5 plates on it, it will be 5, etc. DO NOT CONFUSE THIS WITH A COUNT
This one is a very simple structure, so we can jump right into coding.
init
Okay, to initialize a stack, we are going to need to know the following:
Let's go with the following function prototype:
Now, that function /will/ work, but I can see a number of potential errors.
I can explain those.
What if max_elements is less than 1
Why not 0? Well, if we malloc(0), that is undefined behavior, and who would want a stack that holds no more than 0 elements anyways?
We should probably just do nothing if that is the case.
What if max_elements is too large
What is too large?
max_elements is too large when the call to malloc() fails. How do we know when that happens?
when malloc fails, it will return NULL, we should check for that
How will the program know if an error has occurred
Well, that is a tricky one. I usually solve this by setting a return to init, that way we can check it (a lot of standard methods do this).
So, with all that in mind, lets revise our definition and code:
There, now we have init down. If you dont understand how the if statement works, you can do it this way:
Alright, now that we have a stack to work with, we can worry about data manipulation.
push
Alright, to add data to the stack we need to know the following
Now for this one, we wont worry about a return at all, since the only time there should be an error (conceptual) is if stack_object points to NULL, but that would be a silly user mistake.
So, without further adue, lets get some code in.
For those of you new programmers, here is a less dense version:
The rest should be really simple. Removing an element from the stack is the inverse of adding one.
pop
but, the coding is a little different. I will give the less dense version first this time.
and now the dense one:
NOTE: we dont actually delete the elements in the stack. If you use gdb and dig around you will see they are still there. This isnt important because the next push will overwrite them.
The last step in creating our stack is de-allocation.
destroy
Since this is a very basic stack, the only thing that we need to de-allocate is the data objects in the stack.
And that's it, you made a stack. We can use it like this (sample main)
Now, here are the two files you will need to compile it:
myStack.h
myStack.c
main.c
- English
- C
- Pointers
- Structures
- Functions
Alright, stacks are a REALLY commonly used structure, but some people have hard times understanding how they are created and used.
Lets get into the concept. Imagine you have a table
_______
| |
Now, we have some empty plates, so we "stack" them onto the table
-- <- first plate
_______
| |
and then another
-- <- second plate
-- <- first plate
_______
| |
and so on. Now, removing the plates, we get them back in the REVERSE order, so we remove the second plate, and then the first plate.
"Why would we do that? cant we just pick up the bottom one?"
No. Imagine that there are 65535 plates. Youre not doing that.
Okay, that was a little spoonfed, but, we can get into how it works in code now.
Every stack has the following basic methods:
- init
- push
- pop
- destroy
init
Init is the method we will use to create the stack, set up how big it is, whatever.
That would be like deciding how high the ceiling is for our table.
push
Push is the method we are going to use to add items to the stack, it is very simple.
pop
Pop is the method we use to remove items from the stack. It is another simple function, but the concept gets really weird sometimes.
destroy
Destroy is the method used when we no longer need the stack. This will de-allocate everything we created in init.
Alright, well, we have a basic understanding of what we need to do, now how do we do it?
I am going to use C for this tutorial, so that you guys get a good grip on what is going on. My next tutorial (if this one rates well) will be making a C++ class for our C stack.
First thing we need is to figure out what type of data we want to store. Let's make our stack hold integers.
Next, we have to define what a stack is, we will do so using a structure.
Code:
struct myStack
{
int *data;
int stack_pointer;
};
Breaking that down:
data
data is what will actually store our stack elements once they are pushed on. That one doesnt need a lot of explaining
stack_pointer
the stack pointer holds the next open spot in the stack. If our stack is empty, it will be 0, if it has 5 plates on it, it will be 5, etc. DO NOT CONFUSE THIS WITH A COUNT
This one is a very simple structure, so we can jump right into coding.
init
Okay, to initialize a stack, we are going to need to know the following:
- Which stack we are allocating for
- How many items we want to be able to store
- The type of item
Let's go with the following function prototype:
Code:
void myStack_init(struct myStack *stack_object, int max_elements);
[code]
looks pretty basic, so we can actually just write this one up.
[code]
void myStack_init(struct myStack *stack_object, int max_elements)
{
//allocate the correct amount of data we need
stack_object->data = malloc(sizeof(int) * max_elements);
//remember, we have to multiply by the size of the data we are using
//in this case, sizeof(int)
//initialize our stack pointer, ALWAYS DO THIS
//we will be using 0 in this case
stack_object->stack_pointer = 0;
}
- What if max_elements is less than 1
- What if max_elements is too large
- How will the program know if an error has occurred
I can explain those.
What if max_elements is less than 1
Why not 0? Well, if we malloc(0), that is undefined behavior, and who would want a stack that holds no more than 0 elements anyways?
We should probably just do nothing if that is the case.
What if max_elements is too large
What is too large?
max_elements is too large when the call to malloc() fails. How do we know when that happens?
Code:
void *malloc(size_t size);
How will the program know if an error has occurred
Well, that is a tricky one. I usually solve this by setting a return to init, that way we can check it (a lot of standard methods do this).
So, with all that in mind, lets revise our definition and code:
Code:
char myStack_init(struct myStack *stack_object, int max_elements);
//returns 0 on success, 1 if max_elements < 1, and 2 if malloc fails
char myStack_init(struct myStack *stack_object, int max_elements)
{
//check for too small of a stack (or negative)
if (max_elements < 1)
return 1; //too small, try 1 or higher
//allocate the stack, check for error
if ((myStack->data = malloc(sizeof(int) * max_elements)) == NULL)
return 2; //possibly too large, anyways, couldnt allocate
//initialize the stack pointer
myStack->stack_pointer = 0;
return 0; //all went well, say hello to your new stack
}
There, now we have init down. If you dont understand how the if statement works, you can do it this way:
Code:
char myStack_init(struct myStack *stack_object, int max_elements);
//returns 0 on success, 1 if max_elements < 1, and 2 if malloc fails
char myStack_init(struct myStack *stack_object, int max_elements)
{
//check for too small of a stack (or negative)
if (max_elements < 1)
return 1; //too small, try 1 or higher
//allocate the stack
myStack->data = malloc(sizeof(int) * max_elements);
//check for error
if (myStack->data == NULL)
return 2; //possibly too large, anyways, couldnt allocate
//initialize the stack pointer
myStack->stack_pointer = 0;
return 0; //all went well, say hello to your new stack
}
Alright, now that we have a stack to work with, we can worry about data manipulation.
push
Alright, to add data to the stack we need to know the following
- The stack to add to
- The data to be added
Code:
void myStack_push(struct myStack *stack_object, int insert_data);
So, without further adue, lets get some code in.
Code:
void myStack_push(struct myStack *stack_object, int insert_data)
{
//this one is actually really simple.
stack_object->data[stack_object->stack_pointer++] = insert_data;
}
For those of you new programmers, here is a less dense version:
Code:
void myStack_push(struct myStack *stack_object, int insert_data)
{
//ALWAYS define variables at the TOP of the function
int temp_sp;
//get the stack pointer
temp_sp = stack_object->stack_pointer;
//set the data
stack_object->data[temp_sp] = insert_data;
//update the stack pointer
++stack_object->stack_pointer;
}
The rest should be really simple. Removing an element from the stack is the inverse of adding one.
pop
Code:
int myStack_pop(struct myStack *stack_object);
but, the coding is a little different. I will give the less dense version first this time.
Code:
int myStack_pop(struct myStack *stack_object)
{
//ALWAYS define variables at the TOP of the function
int temp_sp;
int temp_data;
//get the stack pointer
temp_sp = stack_object->stack_pointer - 1; //since the current is empty
//get the data;
temp_data = stack_object->data[temp_sp];
//update the stack pointer
--stack_object->stack_pointer;
//return the data
return temp_data;
}
and now the dense one:
Code:
int myStack_pop(struct myStack *stack_object)
{
//get and return in one step
return stack_object->data[--stack_object->stack_pointer];
}
NOTE: we dont actually delete the elements in the stack. If you use gdb and dig around you will see they are still there. This isnt important because the next push will overwrite them.
The last step in creating our stack is de-allocation.
destroy
Code:
void myStack_destroy(struct myStack *stack_object);
Since this is a very basic stack, the only thing that we need to de-allocate is the data objects in the stack.
Code:
void myStack_destroy(struct myStack *stack_object)
{
free(stack_object->data); //free up our allocated memory
}
And that's it, you made a stack. We can use it like this (sample main)
Code:
int main()
{
struct myStack sample_stack;
int catch;
if (myStack_init(&sample_stack, 5) == 0) //set up our stack to hold max 5 elements, error check
{
//insert 1-4 backwards
myStack_push(&sample_stack, 4);
myStack_push(&sample_stack, 3);
myStack_push(&sample_stack, 2);
myStack_push(&sample_stack, 1);
//pop them off, ALWAYS balance your stack
catch = myStack_pop(&sample_stack); //this one will be 1
catch = myStack_pop(&sample_stack); //this will be 2
catch = myStack_pop(&sample_stack); //3
catch = myStack_pop(&sample_stack); //4
//destroy our stack, we are done with it
myStack_destroy(&sample_stack);
}
else
{
return 1; //stack error
}
return 0;
}
Now, here are the two files you will need to compile it:
myStack.h
Code:
/* sample stack tutorial header */
struct myStack
{
int *data;
int stack_pointer;
};
/* define methods */
char myStack_init(struct myStack *stack_object, int max_elements);
void myStack_push(struct myStack *stack_object, int insert_object);
int myStack_pop(struct myStack *stack_object);
void myStack_destroy(struct myStack *stack_object);
myStack.c
Code:
#include "myStack.h"
#include <stdlib.h> //so we have NULL
char myStack_init(struct myStack *stack_object, int max_elements)
{
//check for too small of a stack (or negative)
if (max_elements < 1)
return 1; //too small, try 1 or higher
//allocate the stack, check for error
if ((myStack->data = malloc(sizeof(int) * max_elements)) == NULL)
return 2; //possibly too large, anyways, couldnt allocate
//initialize the stack pointer
myStack->stack_pointer = 0;
return 0; //all went well, say hello to your new stack
}
void myStack_push(struct myStack *stack_object, int insert_data)
{
//this one is actually really simple.
stack_object->data[stack_object->stack_pointer++] = insert_data;
}
int myStack_pop(struct myStack *stack_object)
{
//get and return in one step
return stack_object->data[--stack_object->stack_pointer];
}
void myStack_destroy(struct myStack *stack_object)
{
free(stack_object->data); //free up our allocated memory
}
main.c
Code:
#include "myStack.h"
#include <stdlib.h>
int main()
{
struct myStack sample_stack;
int catch;
if (myStack_init(&sample_stack, 5) == 0) //set up our stack to hold max 5 elements, error check
{
//insert 1-4 backwards
myStack_push(&sample_stack, 4);
myStack_push(&sample_stack, 3);
myStack_push(&sample_stack, 2);
myStack_push(&sample_stack, 1);
//pop them off, ALWAYS balance your stack
catch = myStack_pop(&sample_stack); //this one will be 1
catch = myStack_pop(&sample_stack); //this will be 2
catch = myStack_pop(&sample_stack); //3
catch = myStack_pop(&sample_stack); //4
//destroy our stack, we are done with it
myStack_destroy(&sample_stack);
}
else
{
return 1; //stack error
}
return 0;
}