Stack

Stack is a linear data structure. It follows Last In First Out (LIFO) principle. In other words, the item which is inserted most recently will be deleted/accessed first.

We cannot access an element from the middle position until all elements over it are deleted.

In parties or buffet, the plates piled on top of each other and if someone wants to eat, that person will take the topmost plate instead of trying to get a plate from the middle. This is stack.

Basic operations :-

1. push(x): It pushes the value x on the stack. This new value is the new top.
2. top(): It returns the value on top of the stack.
3. pop(): It deletes/pops the value on top of the stack.

All operations can be performed in constant time, O(1).

It is implemented in 2 ways :-

1. Stack using Array
2. Stack using LinkedList

Both implementations have their merits and demerits and which one to use generally depends upon the nature of the problem.

We will be discussing them in detail.

Stack using Array

It is classified as a static data structure because the size of the array is generally fixed.

Approach

1. First, we declare an array of a fixed size of the name stk.
2. After that, we initialize a variable ptr = -1 that points to the top position of stack.
3. ptr = -1 indicates that the stack is empty.
4. To push data, we first increment ptr then store value at stk[ptr].
5. If we want to see the value on top, we just print stk[ptr] as ptr points to the top of the stack.
6. To pop/delete value from the top of the stack, we decrement ptr.

See diagram for better understanding

Stack using array in c/c++

#include<stdio.h>

/*
First, we declare 3 global variables 
stack: stores the stack elements
ptr: points to the top of the stack
size: maximum size of the stack
ptr is initialized as "-1" which tells us that the stack is empty
*/

int stk[100];
int size = 100;
int ptr = -1;

/*
The push(x) function pushes the value 'x' on top of the stack
If the stack is full, "OverFlow" message is printed on screen else
The ptr is first incremented by 1 then x is overwritten on stk[ptr] position
*/
void push(int x){
        // check if stack is full or not
	if(ptr==size-1){
		printf("OverFlow \n");
	}
	else{
		++ptr;
		stk[ptr] = x;
	}
}
/*
Returns top elemnt of the stack
*/
int top(){
        // check if stack is empty or not
	if(ptr==-1){
		printf("UnderFlow \n");
		return -1;
	}
	else{
		return stk[ptr];
	}
}

/*
Decrements ptr
Now, if we push value in the stack it will overwrite the deleted value
*/
void pop(){
        // check if stack is empty or not
	if(ptr==-1){
		printf("UnderFlow \n");
	}
	else{
		--ptr;
	}
}

int isEmpty(){
	if(ptr==-1)
		return 1;
	else
		return 0;
}

int main()
{		
	   push(1);
	   push(3);
	   push(4);
	   push(5);
	   
	   if(isEmpty())	printf("STACK IS EMPTY\n");
	   else			printf("STACK IS NOT EMPTY\n");
	   
	   printf("%d\n",top());
	   pop();
	   
	   printf("%d\n",top());
	   pop();
	   
	   printf("%d\n",top());
	   pop();
	   
	   printf("%d\n",top());
	   pop();
	   
	   if(isEmpty())	printf("STACK IS EMPTY\n");
	   else			printf("STACK IS NOT EMPTY\n");
}


Output

STACK IS NOT EMPTY
5
4
3
1
STACK IS EMPTY

Advantages

• It is very easy to implement because we do not have to worry about allocating memory.
• No need to store the address of the next element whereas in the link list each node stores the address of the previous top.
• It provides more flexibility.

Disadvantages

• Array size is constant.
• Some languages allow to reallocate memory to the array but it is not preferred due to contiguous memory.
  For example, suppose you have an array of size 200 and you want to reallocation memory and make it 400. In this case, the system will first search for a block of 400 then copy the values from the previous location to the new location.

Stack Using LinkedList

It is classified as dynamic data because it has the flexibility to grow/shrink as per programmers’ need for better utilization of memory.

Approach

1. First, we define a structure node that stores data and the address of the next node.
2. After that, we initialize a variable Top of type node with NULL that stores the address of the node on top of the stack.
3. Each node stores data as well as the address of the node below it.
4. When the Top is NULL, it indicates that the stack is empty.
5. To push x, we initialize a new node temp with value x and address of the current Top. After that, temp is set as the new Top.
6. To delete/pop data, we simply move to the next node stored in the Top.

See diagram for better understanding

Stack using LinkedList in c/c++

#include<stdio.h>
#include<stdlib.h>

struct node{
	int v; // value to be store in stack
	struct node *next; // to store address os the next node
};

// points to the top of the stack
struct node *Top;


int stack[100];
int size = 100;
int ptr = -1;

/*
The push(x) function pushes the value 'x' on top of stack
If the stack is full, "OverFlow" message is printed on screen else
*/
void push(int x){
	struct node *temp = (struct node*)malloc(sizeof(struct node));
	temp->v = x;
	temp->next = Top; // storing address of previous top in temp
	Top = temp;	// changing Top to temp
}

/*
Returns top elemnt of the stack
*/
int top(){
	if(Top==NULL){
		printf("UnderFlow \n");
		return -1;
	}
	else{
		return Top->v;
	}
}

/*
Decrements ptr
Now, if we push a value in stack it will overwrite the deleted value
*/
void pop(){
	if(Top==NULL){
		printf("UnderFlow \n");
	}
	else{
		// initialize temp with Top
		node *temp = Top;
		// Set Top to node just below it
		Top = Top->next;
		// release memory of popped element
		// since it is no longer of out use
		// if memory is not released
		// then at one point system will have no memory left
		// and operations which may required new memory
		// will fail, like creation of new node
		free(temp);
	}
}

int isEmpty(){
	if(Top==NULL)
		return 1;
	else
		return 0;
}

int main()
{	
	   // initialize Top with NULL	
	   Top = NULL;
	   
	   push(1);
	   push(3);
	   push(4);
	   push(5);
	   
	   if(isEmpty())	printf("STACK IS EMPTY\n");
	   else			printf("STACK IS NOT EMPTY\n");
	   
	   printf("%d\n",top());
	   pop();
	   
	   printf("%d\n",top());
	   pop();
	   
	   printf("%d\n",top());
	   pop();
	   
	   printf("%d\n",top());
	   pop();
	   
	   if(isEmpty())	printf("STACK IS EMPTY\n");
	   else			printf("STACK IS NOT EMPTY\n");
}

Output

STACK IS NOT EMPTY
5
4
3
1
STACK IS EMPTY

Advantages

• It will only require memory proportional to the number of elements.
• It can easily grow/shrink.

Disadvantages

• For each element, the link list will also store the address of the next node whereas in the array there’s no overhead for address.
• The system may not have memory available during insertion operations. Therefore, the program should be able to handle such a situation.
• It is hard to implement.

Applications

• Convert infix expression to postfix expression.
• To convert recursion based programs to iteration based. For example, converting recursive Depth First Search to non-recursive.
• In Pushdown automata.
• All the recursive functions use an internal stack.

Read more articles related to this topic

References

https://simple.wikipedia.org/wiki/Stack_(data_structure)