Implementation of Stack

Implementation of Stack

• A stack is a special case of an ordered list, i.e. it is a ordered list with some restrictions on the way in which we perform various operations on a list.

• We need an integer variable top which will keep track of the top of the stack as more and more elements are inserted into and deleted from the stack.

• The declarations in C are as follows.

• Declaration 1: Using Arrays

#define size 100

int stack[size], top = -1;

In the above declaration stack is nothing but an array of integers. And most recent index of that array will act as a top.

The stack is of the size 100. As we insert the numbers, the top will get incremented. The elements will be placed from oth position in the stack. At the most we can store 100 elements in the stack, so at the most last element can be at (size - 1) position, i.e. at index 99.

• Declaration 2: Using Structure

#define size 10

struct stack {

int s[size];

int top; 2 ...

}st;

In the above declaration stack is declared as a structure.

Now compare declaration 1 and 2. Both are for stack declaration only. But the second declaration will always preferred. Why? Because in the second declaration we have used a structure for stack elements and top. By this we are binding or co-relating top variable with stack elements. Thus top and stack are associated with each other by putting them together in a structure. The stack can be passed to the function by simply passing the structure variable.

We will make use of the second method of representing the stack in our program.

• The stack can also be used in the databases.

• For example if we want to store marks of all the students of forth semester we can declare a structure of stack as follows

# define size 60

typedef struct student

{

int roll.no;

char name[30];

float marks;

}stud;

stud S1[size];

int top = -1;

• The above stack will look as shown in Fig. 4.3.3:

• Thus we can store the data about whole class in our stack.

• The above declaration means creation of stack.

• Hence we will write only push and pop function to implement the stack.

• Before pushing or popping we should check whether stack is empty or full.

 

1. Stack Empty Operation

• Initially stack is empty. At that time the top should be initialized to -1 or 0. 10

• If we set top to - 1 initially then the stack will contain the elements from oth position and if we set top to 0 initially, the elements will be stored from 1^st position, in the stack.

• Elements may be pushed onto the stack and there may be a case that all the elements are removed from the stack. Then the stack becomes empty.

• Thus whenever top reaches to - 1 we can say the stack is empty.

int stempty()

{

if(st.top==-1)

return 1;

else

return 0;

}

Key Point If top=-1 means stack empty.

 

2. Stack Full Operation

• In the representation of stack using arrays, size of array means size of stack.

• As we go on inserting the elements the stack gets filled with the elements.

• So it is necessary before inserting the elements to check whether the stack is full or not.

• Stack full condition is achieved when stack reaches to maximum size of array.

int stfull()

{

if(st.top>=size-1)

return 1;

else

return 0;

}

Thus stfull is a Boolean function if stack is full it returns 1 otherwise it returns 0.

Key Point: If top > = size means stack is full.

 

3. The 'Push' and 'Pop' Functions

• We will now discuss the two important functions which are carried out on a stack.

• push is a function which inserts new element at the top of the stack. The function is as follows.

void push(int item)

{

st.top++; /* top pointer is set to next location */

st.s[st.top] = item; /* placing the element at that location */

}

• Note that the push function takes the parameter item which is actually the element which we want to insert into the stack - means we are pushing g the element onto the stack.

• In the function we have checked whether the stack is full or not, if the stack is not full then only the insertion of the element can be achieved by means of push operation.

• Now let us discuss the operation pop, which deletes the element at the top of the stack. The function pop is as given below -

• Note that always top element can be deleted.

int pop()

{

int item;

item = st.s[st.top];

st.top--;

return(item);

}

• In the choice of pop - it invokes the function 'stempty' to determine whether the stack is empty or not. If it is empty, then the function generates an error as stack underflow! If not, then pop function returns the element which is at the top of the stack.

• The value at the top is stored in some variable as item and it then decrements the value of the top, which now points to the element which is just under the element being retrieved from the stack.

• Finally it returns the value of the element stored in the variable item. Note that this is what called as logical deletion and not a physical deletion, i.e. even when we decrement the top, the element just retrieved from the stack remains there itself, but it no longer belongs to the stack. Any subsequent push will overwrite this element.

• Push operation can be shown by following Fig. 4.3.6.

• The pop operation can be shown by following Fig. 4.3.7.

Key Point If stack is empty we cannot pop and if stack is full we cannot push any element.

 

4. Implementation

 

Ex. 4.3.1: Implementing stack using Arrays.

/*************************************************************

Program for implementing a stack using arrays. It involves various operations such as push,pop,stack empty, stack full and display.

*************************************************************/

#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

#define size 5

/* stack structure*/

struct stack {

int s[size];

int top;

}st;

int stfull()

{

if(st.top>=size-1)

return 1;

else

return 0;

}

void push(int item)

{

st.top++;

st.s[st.top] = item;

}

int stempty()

{

if(st.top ==-1)

else

return 1;

else

return 0;

}

int pop()

{

int item;

item=st.s[st.top];

st.top--;

return(item);

}

/*

The display Function

Input:none

Output:none-displays the contents of the stack

Called By:main

Calls:none

*/

void display()

{

int i;

if(stempty())

printf("\n Stack Is Empty!");

else

{

for(i=st.top;i>=0;i--)   Displaying stack from top to bottom

printf("\n%d", st.s[i]);

}

}

void main(void)

{

int item,choice;

char ans;

st.top=-1;

clrscr();

printf("\n\t\t Implementation Of Stack");

do

{

printf("\n Main Menu");

printf("\n1.Push\n2.Pop\n3.Display\n4.exit");

printf("\n Enter Your Choice");

scanf("%d", &choice);

switch(choice)

{

case 1:printf("\n Enter The item to be pushed");

scanf("%d", &item);

if(stfull())    Before pushing we should check stack full condition

printf("\n Stack is Full!");

else

push(item);

break;

case 2:if(stempty())  Before popping we should check stack empty condition

printf("\n Empty stack!Underflow !!");

else

{

item=pop();

printf("\n The popped element is %d",item);

}

break;

case 3:display();

break;

case 4:exit(0);

}

printf("\n Do You want To Continue?");

ans=getche();

} while(ans == 'Y' || ans =='y');

getch();

}

/******End Of Program****************?

Output

Implementation Of Stack

Main Menu

1. Push

2. Pop

3. Display

4. exit

Enter Your Choice1

Enter The item to be pushed 10

Do You Want To Continue?y

Main Menu

1. Push

2. Pop

3. Display

4. exit

Enter Your Choice 1

Enter The item to be pushed 20

Do You want To Continue?y

Main Menu

1. Push

2. Pop

3. Display

4. exit

Enter Your Choice3

20

10

Do You Want To Continue?y

Main Menu

1. Push

2. Pop

3. Display

4. exit

Enter Your Choice2

The popped element is 20

Do You want To Continue?y

Main Menu

1. Push

2. Pop

3. Display

4. exit

Enter Your Choice 2

The popped element is 10

Do You want To Continue?y

Main Menu

1. Push

2. Pop

3. Display

4. exit

Enter Your Choice

Empty stack!Underflow !!

Do You want To Continue?n