## Blog posts

Lecture Series #1: Stacks

Welcome,

Today, I would like to talk about stacks, their implementation and field of use.

Stacks are one of the easiest, yet the very basic data structure. One should learn stacks first before learning any other data structure.
Stacks can be imagined as a stack, a bag or an one-side open tube. Let's illustrate it;

| |
| |
| | <---- This is a stack.
| |
| |
---

Stack is a first in last out (FILO/LIFO) data structure. Elements are being added and removed by pop() and push() functions. Push function adds one element to the top of stack and pop removes top element from stack. In order to understand its behavior, let's study an example;

Assume we have some integer number: 1 2 3 4 5
let's add them to stack one by one;

push(1)

| |
| |
| |
| |
|1| <---- New element added to top
---

push(2)

| |
| |
| |
|2| <---- New element added to top
|1|
---

push(3)

| |
| |
|3| <---- New element added to top
|2|
|1|
---

pop()

| |
| |
| | <---- Here the top element removed from stack
|2|
|1|
---

push(4)

| |
| |
|4| <---- New element added to top
|2|
|1|
---

As you can see, when pushing a new element, it is always added to top and when we pop one element it is removed from top. I believe it is clear up to this point. So, how do we implement it. First, we need to declare what stack is. We will use struct for this purpose;

`#define MAX_SIZE 10typedef struct stack{        int data[MAX_SIZE];        int ptr;}stack;`

So, we can say that, our stack has 10 integers and one integer pointer. ptr pointer will point to top element of stack and data array will hold the numbers. Great, now we have declaration of our stack. In order to be able to use our stack, first, we need to initialize (set ptr to top of the stack which is 0) stack. Let's write a method for this purpose;

`void init (stack &s) //we have reference our stack because we are aiming to change its data.{        s.ptr = 0;}`

Now we can initialize our stack and we need pop & push functions to use it. Let's write them also;

`void push(stack &s, const int &data) //push will get reference to stack and reference data. Data is call-by-reference to use less memory but it is set to const, so, we guarantee not to change it.{        if(!isFull(s)) //If stack is full, don't add        {                s.data[s.ptr] = data;                s.ptr++;        }        else        {                cout<<"Stack is full!"<<endl;        }}int pop (stack &s) //we will return the value which has been removed from stack{        if(!isEmpty(s)) //if stack is empty, don't try to remove        {                s.ptr--;                return s.data[s.ptr];        }        else        {                cout<<"Stack is empty!"<<endl;        }}`

isEmpty() and isFull() functions are not shown in this blog post, but they can be found in the git repository. Since we have implemented our pop & push functions, we can start using our stack. Let's look at the main function for how to use it.

`int main(){        stack s;        init(s);        int i = 0;        while(!isFull(s))        {                cout <<"I am adding "<<i<<" to stack"<<endl;                push(s, i);                i++;        }        while(!isEmpty(s))        {                cout<<"I have popped out "<<pop(s)<<" from stack"<<endl;        }        return 0;}`

And the output will be like;

I am adding 0 to stack
I am adding 1 to stack
I am adding 2 to stack
I am adding 3 to stack
I am adding 4 to stack
I am adding 5 to stack
I am adding 6 to stack
I am adding 7 to stack
I am adding 8 to stack
I am adding 9 to stack
I have popped out 9 from stack
I have popped out 8 from stack
I have popped out 7 from stack
I have popped out 6 from stack
I have popped out 5 from stack
I have popped out 4 from stack
I have popped out 3 from stack
I have popped out 2 from stack
I have popped out 1 from stack
I have popped out 0 from stack

This is a very basic stack example. It is limited for 10 integers but this number can be easily changed. Also, if you want to implement it without a maximum number of data, you can decide to use vector instead of an array (vectors also have a maximum value but it is so big (vector::max_size). You can see full implementation of the stack and implementation with vector in git hub repository here.

Stacks are great, they are being used in areas such as game development, OS scheduling algorithms, mathematical calculations etc... Let's give some specific examples for the areas;

Game development: OpenGL developers use stacks for drawing objects on to screen. Also, towers of hanoi game is stack problem.
OS Scheduling algorithms: Stacks are not widely used in scheduling algorithms but it is possible to use them. Also, stacks like call stack is being used to track sequence of function calls in programming. Its details are normally hidden for high level languages. If you want to know more, take a look at here.
Mathematic Calculations: Separating a number to its digits or converting between binary and decimal.

Have a nice day :)

Edit: Class version added to git. Note that, codes are not fault tolerant. They are only written to explain basic concepts.

Edited on: 2016-08-21 15:33:10
by zgrw on 2014-05-19 14:11:20