Tutorial [C] Building your first stack

Tutorial [C] Building your first stack - Printable Version

+- Sinisterly (https://sinister.ly)
+-- Forum: Coding (https://sinister.ly/Forum-Coding)
+--- Forum: C, C++, & Obj-C (https://sinister.ly/Forum-C-C-Obj-C)
+--- Thread: Tutorial [C] Building your first stack (/Thread-Tutorial-C-Building-your-first-stack)

[C] Building your first stack - phyrrus9 - 12-12-2014

Firstly, before you read this tutorial, you MUST understand the following languages and concepts:

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

Since our stack only stores integers, we can ignore the type.
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;
}

Now, that function /will/ work, but I can see a number of potential errors.

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);

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:

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

So, we can use the following prototype:

Code:
void myStack_push(struct myStack *stack_object, int insert_data);

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.

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;
}

RE: [C] Building your first stack - Nebulous - 12-12-2014

You left out a lot of what certain functions and declarations are/do. Honestly it's just a bunch of code being spoonfed to us without knowing what each of the functions/lines do.

RE: [C] Building your first stack - phyrrus9 - 12-12-2014

do explain?

I explained EXACTLY what each line of code does.

RE: [C] Building your first stack - Nebulous - 12-12-2014

(12-12-2014, 11:21 PM)phyrrus9 Wrote: do explain?

I explained EXACTLY what each line of code does.

Wrong. If I cared enough to go through every line and point out what you didn't explain, I would. But I don't, sorry. There's also a lot of basic shit about a stack that you left out.

Not to mention, your very first code tag, you didn't explain what "*data" is actually called or why there's an asterisk in it.

Don't get me wrong, I'm not trying to bash on you or your tutorial, just pointing out mistakes that could be fixed in your next tutorial.

RE: [C] Building your first stack - phyrrus9 - 12-13-2014

1. this is not a C++ tutorial
2. this is not a "this is what stuff is" thread
3. I have written more about code on this forum.
4. If you had read it, then you would have a place in commenting. You did not, therefore you do not.

Code:
mov rax, Nebulous ;yeah, your whole id is 64-bit, pathetic
sub al, al ;lets assume that your reputation is the lower 8 bits there
mov Nebulous, rax ;push it back
xor eax, eax
ret

Goodbye, troll

RE: [C] Building your first stack - Nebulous - 12-13-2014

(12-13-2014, 03:48 AM)phyrrus9 Wrote: 1. this is not a C++ tutorial
2. this is not a "this is what stuff is" thread
3. I have written more about code on this forum.
4. If you had read it, then you would have a place in commenting. You did not, therefore you do not.

Code:
mov rax, Nebulous ;yeah, your whole id is 64-bit, pathetic sub al, al ;lets assume that your reputation is the lower 8 bits there mov Nebulous, rax ;push it back xor eax, eax ret

Goodbye, troll

What a great response!

Come back when you know how to write a tutorial and stop getting mad because someone criticizes you for it. Grow the fuck up.

Also, when I said C++, I meant your next tutorial because you said you'd make one if this went well.

RE: [C] Building your first stack - dopamine - 12-13-2014

(12-13-2014, 04:02 AM)Nebulous Wrote: What a great response!

Come back when you know how to write a tutorial and stop getting mad because someone criticizes you for it. Grow the fuck up.

Also, when I said C++, I meant your next tutorial because you said you'd make one if this went well.

This tutorial is about stack. Programmers should only look at this when they already understand pointers. There was no need to talk trash when all he really needed to do is write minimal knowledge requirements for his tutorials.

RE: [C] Building your first stack - phyrrus9 - 12-15-2014

I will go ahead and update the original post to include them just to ensure that we don't run into these kinds of problems again.