Stack

One way to think about this implementation is to think of functions as being stacked on top of each other; the last one added to the stack is the first one taken off. In this way, the data structure itself enforces the proper order of calls. Conceptually, a stack is simple: a data structure that allows adding and removing elements in a particular order. Every time an element is added, it goes on the top of the stack; the only element that can be removed is the element that was at the top of the stack.

Consequently, a stack is said to have "first in last out" behavior (or "last in, first out"). The first item added to a stack will be the last item removed from a stack. So what's the big deal? Where do stacks come into play? As you've already seen, stacks are a useful way to organize our thoughts about how functions are called. In fact, the "call stack" is the term used for the list of functions either executing or watiing for other functions to return. In a sense, stacks are part of the fundamental language of computer science. When you want to express an idea of the "first in last out" variety, it just makes sense to talk about it using the common terminology. Moreover, such operations show up an awful lot, from theoretical computer science tools such as a push-down automaton to AI, including implementations of depth-first search.

Stacks have some useful terminology associated with them:

1. Push To add an element to the stack
2. Pop To remove an element from the stock
3. Peek To look at elements in the stack without removing them
4. LIFO Refers to the last in, first out behavior of the stack
5. FILO Equivalent to LIFO

General Algorithm

1. [Prologue] Save the parameters, Local Variables and return address.
2. [Body] If the base criterion has been reached, then perform the final computation and go to step 3; otherwise, perfprm the partial computation and go to step 1(initialize a recursive call)
3. [Epilogue] Restore the most recently saved parameters, local variables, and return address. Go to this return address.

/**************** C Program For Impelmetation Of Stack ********************/

#define MAXSIZE 10

struct st
{
int top;
int stack[MAXSIZE];
};

struct st s;

int empty(void);
int full(void);
void push(void);
void pop(void);
void display(void);

void main()
{
char ans;
int ch;
do
{
clrscr();
printf("********Stack Program**********\n");
printf("1.PUSH\n");
printf("2.POP\n");
printf("3.DISPLAY\n");
printf("4.QUIT\n");
printf("Enter Your Choice : ");
scanf("%d",&ch);
switch(ch)
{
case 1:
push();
break;
case 2:
pop();
break;
case 3:
display();
break;
case 4:
exit(1);
break;

default:
printf("INVALID CHOICE!!!!!!!!!!!!!!!!\n");
break;
}
printf("Want To Go To The Main Menu[y/n]");
flushall();
ans = getch();
}
while(ans == 'y' ans == 'Y');
printf("\nPress Any Key To Exit");
getch();
}

int full(void)
{
if (s.top == MAXSIZE)
return(1);
else
return(0);
}

int empty(void)
{
if (s.top == 0)
return(1);
else
return(0);
}
void push(void)
{
char ch;
int x;
do
{
if(full() == 1)
{
printf("\nStack Full\n");
break;
}
else
{
s.top = s.top + 1;
printf("\nEnter An Element To Be Pushed: ");
scanf("%d",&x);
s.stack[s.top] = x;
}
printf("\nDo You Want To Push More Elements[y/n]");
flushall();
ch = getch();
}
while(ch == 'y' ch == 'Y');
}

void pop(void)
{
char ch;
do
{
if(empty() == 1)
{
printf("\nStack Empty\n");
break;
}
else
{
printf("\n%d has been popped !",s.stack[s.top]);
s.top = s.top - 1;
}
printf("\nDo you Want To Pop Out More?[y/n]");
flushall();
ch = getch();
}
while(ch == 'Y' ch == 'y');
}

void display(void)
{
int i;
clrscr();
if(empty() == 1)
printf("\nStack Empty!!!");
else
{
printf("Displaying Stack............\n");
for(i = s.top; i>0;i--)
printf("%d",s.stack[i]);
}
}
/************** OUTPUT *************

********Stack Program**********
1. PUSH
2. POP
3. DISPLAY
4. QUIT
Enter Your Choice : 1

Enter An Element To Be Pushed : 1
Do YOu Want To Push More Elements [y\n] y
Enter An Element To Be Pushed : 2
Do YOu Want To Push More Elements [y\n] y
Enter An Element To Be Pushed : 3
Do YOu Want To Push More Elements [y\n] y
Enter An Element To Be Pushed : 4
Do YOu Want To Push More Elements [y\n] y
Enter An Element To Be Pushed : 5
Do YOu Want To Push More Elements [y\n] n
Want To Go Main Menu? [y\n] y

********Stack Program**********
1. PUSH
2. POP
3. DISPLAY
4. QUIT
Enter Your Choice : 3

Displaying Stack......
5
4
3
2
1
Want To Go Main Menu? [y\n] y

********Stack Program**********
1. PUSH
2. POP
3. DISPLAY
4. QUIT
Enter Your Choice : 2

5 Has Been Popped!
Do You Want To Pop More? [y\n] y
4 Has Been Popped!

Do You Want To Pop More? [y\n] n
Want To Go Main Menu? [y\n] y

********Stack Program**********
1. PUSH
2. POP
3. DISPLAY
4. QUIT
Enter Your Choice : 3

Displaying Stack.........
3
2
1
Want To Go Main Menu? [y\n] y

********Stack Program**********
1. PUSH
2. POP
3. DISPLAY
4. QUIT
Enter Your Choice : 4 */