Stack (Pile)

INTRODUCTION TO STACK DATA STRUCTURE

Before talking about stacks, here is a resume about linked list:

>> A linked list allocates the memory dynamically.

>> The nodes of LL are maintained in non-continuous memory.

>> Each node contains the next pointer, which keeps the reference of the next node.

>> The last node always contains NULL in its address.

Now in order to make a stack using a pre-entered linked list (or make your own) is very simple, If you understood the principle of linked list and how they are structured then you know 90% about stacks.

Actually, if you go back into the linked list part, in the example when I said that when we use the function insertion_tete, the head or the starting point (that plays the role of reference to our linked list) points to the last element entered by the user. It is actually a representation of a stack or the main principle of a stack, which is called: LIFO principle >> Last in First Out.

So in order to make things a bit harder let us code a stack using two ways: first one we just re-use the insertion_tete function to insert (or we say: push) an element into our stack let’s call this new function push (). The second one, we are going to see a function that takes a pre-entered linked list and gives us a stack representation of it.

As all data structures, there is some operations we can perform to a stack:

The Fanta-stack* 4 operations

1- A function that delete the head value or pop up the last element of the stack we will call it pop ().

2- A function that return the last element (retrieve the top-most node) of a stack without deleting it we will call this function peek ().

3- A function that traverse a stack, which means display the values of a stack in order (from top to bottom- LIFO)

4- A function that tells us if a stack is empty.

Note: because this function has no arguments, we will use a loop in order to enter values in main function.

Concerning the TOP that will keep track of the last element in the stack we will keep it move on after each value entered.

Now we finished our push function (easy right ?) let us play with it :)

~ The function that will delete the last element in the stack: POP ()

In the illustration bellow you can see that the process of deleting is easy because it concerns just the last element.

To do the deletion we make first a temporary variable (a twin) to our TOP, then we display (if we want) the value of this last node, after that, we make our TOP variable pointes to the next element in the stack (which is just below it) and because linked lists allocates the memory dynamically we need to free that last space and the way to do it is by using a C function called free(). {simple right ?!}

~ We have three function to go: the Traversal or display function, the peek function and the is Empty function.

As an Exercice for you, : ) I will keep the peek function for you to do, because we did it implicitly in the pop function.

Now let us make the function that will display to us the data in the stack.

As usual, very easy : if the stack is empty which means the TOP pointes to NULL then there is no elements in the stack and it is empty, otherwise we loop through the stack and print for each time we encounter an element till we reach the “bottom” of the stack which pointes to NULL.

Becaue we are using the insertion_tete function the process will be similar to copying and pasting to the new stack structure. To do so, we’re goin to make some temporary nodes to hold the values and keeps things safe.

As you can see in the above image we have that linked list in the order of 3-> 2->1 and we want it to be displayed or pushed in this order because when the user entered the values the last element or value entered was 3 so to respect the principle of LIFO we will keep it in this order.

(after we finish this part we will discuss the other way when we have to inverse the linked list when passing it into the stack).

Let’s go back to illustrations now.

They said that one image is worth a thousand words, as you can notice in the image above we created a new_liste with a value (data) of the same as head value (head->data) and then we made this new liste points to NULL after that the TOP pointes to that new liste (read this again to understand the principle).

Now the things will be a bit harder.

First in order to copy and paste the second value of the linked list to the next node in the stack we need to make some temporary variables :

>The temporary head will be the brother of the head that keep track of the linked list and for each pass this variable will move forward.

>The temporary TOP will play the role of the TOP while traversing the stack, because we want to know each time the last element in the stack (the element at the bottom in the image) so that we push it to the top each time (because remember we are using the insertion_tete function so we’re just copying and pasting).

>The two other nodes will play a big role here: the first one (prev_liste) will hold the previous Node we entered so that we will not loos it; The second one (new_liste) will take the value brought from the linked list by the temporary head.

- So each time the temporary head will move forward in the linked list.

- Then the new_liste take the data in this current head.

- Then we move one to the stack temporary TOP that will loop through the stack until we reach the NULL (the bottom).

- Before this third step we make the prev_liste takes the Node pointed by the TOP.

- After that we make this previous Node pointes to the new_liste and then the new liste pointes to NULL.

>> Like that, we copied and pasted successfully the linked list into our stack structure (of course respecting the principle of LIFO).