Stack - Data Structure

algorithm.md

###Stack - Linear Data Structure, Abstract in nature

Follows LIFO, Last In First Out Ideology

####Abstract ? We know the concept, what stack is. Although it's implementation solely depends on the implementor. For example it can be implemented by arrays, structure or linked list, but what remains common is the type of operations that can be performed over this data-structure - PUSH, POP, TRAVERSE, REVERSE, etc.

####Some Assumptions

• The variable TOP always points to the top of the Stack.
• The variable MAX_SIZE contains the maximum possible size of the Stack.

As mentioned, the implementation can vary and so can the algorithm. One provided here is not meant for efficiency, but for basic Stack implementation.

####Stack :: Insertion - or PUSH

PUSH(STACK s, element_to_insert):
	IF TOP == -1:
		/* There's no element in the stack */
		s[0] = element_to_insert
		TOP = 0
	ELSE IF TOP + 1 < MAX_SIZE:
		s[TOP + 1] = element_to_insert
		TOP = TOP + 1
	ELSE
		/* There's no more space in the stack */
		PRINT "Overflow"
	END IF
END PUSH

####Stack :: Deletion - or POP

POP(STACK s):
	IF TOP != -1 :
		/* If we want to pick a plate from a stack of plates, we pick the topmost one. */
		element_fetched = s[TOP]
		
		TOP = TOP - 1

		RETURN element_fetched
	ELSE
		/* Stack's empty. No more elements to fetch. */
		PRINT "Underflow"
	END IF
END POP

####Stack :: Traversal - visiting each elements individually

TRAVERSE(STACK s):
	IF TOP != -1 :
		/* We can easily iterate over the elements to access them */
		FOR i = TOP DOWN TO 0:
			PRINT s[i]
		END FOR
	ELSE
		/* There's no element in the stack */
		PRINT "No elements in the stack"
	END IF
END TRAVERSE

####Stack :: Reversal - Reverse the order of stack

REVERSE(STACK s):
	IF TOP != -1 :
		/* Its quite easy to reverse a stack, if another stack is used. */
		/* Pick an element from stack 1 and insert it in stack 2. */

		STACK s1 = s
		s1_top = TOP

		STACK s2
		s2_top = -1 /* Initially empty */

		WHILE s1_top != -1:
			s2_top = s2_top + 1
			s2[s2_top] = s1[s1_top]
			s1_top = s1_top - 1
		END WHILE

		/* s2 holds the reverse of STACK s */
		TRAVERSE(s2)
	ELSE
		/* There's no element in the stack */
		PRINT "No elements in the stack"
	END IF
END REVERSE

For most of the operations here, the complexity will be in order of O(k) [0 < k <= n], where n denotes the Stack size during the concerned moment. Specifically,

• TRAVERSE and REVERSE (using a second stack) will be of O(n)
• while PUSH and POP will be of O(1)

stack.c

/*
	STACK using array
	0 based indexing
	** for TURBO C, remove // from commented statements
*/

#include<stdio.h>
//#include<conio.h>

#define MAX_SIZE 10
int TOP;
int s[MAX_SIZE];

void PUSH(int *s, int element_to_insert){
	if(TOP == -1){
		s[0] = element_to_insert;
		TOP = 0;
	}else if(TOP + 1 < MAX_SIZE){
		s[TOP + 1] = element_to_insert;
		TOP = TOP + 1;
	}else{
		printf("\nOverflow!");
	}
}

int POP(int *s){
	int element_fetched;
	if(TOP != -1){
		element_fetched = s[TOP];
		TOP = TOP - 1;
		return element_fetched;
	}else{
		printf("\nUnderflow!");
	}
	return -1; /* to denote operation failed */
}

void TRAVERSE(int *s){
	int i;
	if(TOP != -1){
		printf("\n\t____________________\n");
		for(i = TOP; i >= 0; i--){
			printf("\n\t%d", s[i]);
			if (i == TOP) printf("\t<- TOP");
		}
		printf("\n\t____________________");
	}else{
		printf("No elements in the stack!");
	}
}

void REVERSE(int *s){
	int *s1, s1_top;
	int s2[MAX_SIZE], s2_top;

	printf("\n\nReverse stack :: ");
	if(TOP != -1){
		s1 = s;
		s1_top = TOP;

		s2_top = -1;

		while(s1_top != -1){
			s2_top = s2_top + 1;
			s2[s2_top] = s1[s1_top];
			s1_top = s1_top - 1;
		}
		TRAVERSE(s2);
	}else{
		printf("No elements in the stack");
	}
}

int main(){
	int ch = 0, element;
	TOP = -1; /* Initial condition */

	//clrscr();

	do{
		printf("\n\nAvailable Operations:\n1. PUSH\n2. POP\n3. TRAVERSE\n4. REVERSE\n5. QUIT");
		printf("\nEnter your choice (1 - 5): "); scanf("%d", &ch);
		switch(ch){
			case 1:
				printf("\nEnter an element to insert: ");  scanf("%d", &element);
				PUSH(s, element);
				printf("\nSTACK STATUS :: "); TRAVERSE(s);
			break;
				
			case 2:
				element = POP(s);
				if(element != -1)	printf("\nPopped element : %d", element);
				printf("\nSTACK STATUS :: "); TRAVERSE(s);
			break;

			case 3:
				printf("\nSTACK TRAVERSAL :: "); TRAVERSE(s);
			break;

			case 4:
				printf("\nPresent Stack :: "); TRAVERSE(s);
				REVERSE(s);
			break;

			case 5: break;

			default:
				printf("\nInvalid options! Choose between [1,2,3,4,5]");
		}
	}while(ch > 0 && ch < 5);

	printf("\n");
	//getch();
	return 0;
}

Stack.java

/*
	STACK using array
	0 based indexing
	Save File as Stack.java
*/

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Stack{
	static int TOP, MAX_SIZE = 10;
	static int[] s = new int[MAX_SIZE];

	/*  Why all members are static? Since most of them are called from main, which itself is static. */

	static void PUSH(int[] s, int element_to_insert){
		if(TOP == -1){
			s[0] = element_to_insert;
			TOP = 0;
		}else if(TOP + 1 < MAX_SIZE){
			s[TOP + 1] = element_to_insert;
			TOP = TOP + 1;
		}else{
			System.out.print("\nOverflow");
		}
	}

	static int POP(int[] s){
		int element_fetched;
		if(TOP != -1){
			element_fetched = s[TOP];
			TOP = TOP - 1;
			return element_fetched;
		}else{
			System.out.print("\nUnderflow");
		}
		return -1; /* to denote operation failed */
	}

	static void TRAVERSE(int[] s){
		if(TOP != -1){
			System.out.print("\n\t____________________\n");
			for(int i = TOP; i >= 0; i--){
				System.out.print("\n\t" + s[i]);
				if (i == TOP) System.out.print("\t<- TOP");
			}
			System.out.print("\n\t____________________\n");
		}else{
			System.out.print("No elements in thr Stack!");
		}
	}

	static void REVERSE(int[] s){
		int[] s1; int s1_top;
		int[] s2 = new int[MAX_SIZE]; int s2_top;

		System.out.print("\n\nReverse stack :: ");
		if(TOP != -1){
			s1 = s;
			s1_top = TOP;

			s2_top = -1;

			while(s1_top != -1){
				s2_top = s2_top + 1;
				s2[s2_top] = s1[s1_top];
				s1_top = s1_top - 1;
			}
			TRAVERSE(s2);
		}else{
			System.out.print("No elements in the Stack!");
		}
	}

	public static void main(String args[]) throws Exception{
		BufferedReader ip = new BufferedReader(new InputStreamReader(System.in));
		int ch = 0, element, index;
		TOP = TOP = -1; /* Initial condition */

		do{
			System.out.print("\n\nAvailable Operations:\n1. PUSH\n2. POP\n3. TRAVERSE\n4. REVERSE\n5. QUIT");
			System.out.print("\nEnter your choice (1 - 5): "); ch = Integer.parseInt(ip.readLine());
			switch(ch){
				case 1:
					System.out.print("\nEnter an element to insert: ");  element = Integer.parseInt(ip.readLine());
					PUSH(s, element);
					System.out.print("\nSTACK STATUS :: "); TRAVERSE(s);
				break;
					
				case 2:
					element = POP(s);
					if(element != -1)	System.out.print("\nDeleted element : " + element);
					System.out.print("\nSTACK STATUS :: "); TRAVERSE(s);
				break;

				case 3:
					System.out.print("\nSTACK TRAVERSAL :: "); TRAVERSE(s);
				break;

				case 4:
					System.out.print("\nPresent Stack:: "); TRAVERSE(s);
					REVERSE(s);
				break;

				case 5: break;

				default:
					System.out.print("\nInvalid options! Choose between [1,2,3,4,5]");
			}
		}while(ch > 0 && ch < 5);

		System.out.print("\n");
	}
}