We can implement the data structure through the C language. There are several types of data structure available to store and access the data in an efficient way. Stack is one of them.
A stack is a modified version of array. We can add or remove an element at the stack’s one end. This end is at the Top of the stack.
Stack is a specialized way to handle, store, insert, delete, access the data. It is abstract in nature.
Array and Stack
- There is a bit of difference between the array and the stack in terms of their accessibility. We can access any element from the array at any condition but in the case of stack, we can insert or delete the element from one end one by one. This end is called Top. In terms of accessibility, the array is faster than the stack.
- Stack has two main function called push and pop.
- The push function is used to insert in a stack and the pop function is used to remove an element from the stack.
Representation
We can only access the last element inserted in stack. This is the top of stack. We can either insert or remove from top.
This is known as the Last in Fast out (LIFO) and the Fast in Last out (FILO).
Implementation
Stack can be implemented as follows:
Operation
Algorithm Push: PUSH (STACK, TOP, MAXSTK, ITEM)
1. [Stack is full]
Show Message: OVERFLOW and Return
2. Set TOP = TOP + 1
3. SET STACK [TOP] = ITEM
4. Return
Algorithm Pop: POP (STACK, TOP, ITEM)
1. [element removed from stack]
Show Message: Underflow and Return
2. SET ITEM = STACK[ TOP ]
3. TOP : TOP -1
4. Return
Stack Using Array
{
int top ;
unsigned capacity ;
int *array ;
}
Here, we define a user defined data type called arraystack. It has three data members named top, capacity, and a pointer named *array.
Polish Notation
Polish notation is writing operators of an expression either before or after their operand.
Ways of Writing:
Infix 2. Prefix 3. Postfix
1. Infix
The operators are kept between the two operands.
Example:Â A + B
2. Prefix
The operators are kept before their operands.
Example:Â + A B
3. Postfix
The operators are kept after their operands.
Example:Â A B +
Convert
1.
( A + B ) * C
Prefix:
* + A B C
Postfix:
A B + C *
2.
A + ( B * C )
Prefix:
+ A * B C
Postfix:
A B C * +
3.
Prefix:/ + A B – C D
Postfix:A B + C D - /
All of this conversion can be done using stack. Now, we want to show how a stack can be created and how the element or data is inserted. The elements can be removed from the stack through programming.
Programming Example
#include<stdlib.h>
int item ;
struct arraystack // define an data type ;
{
int top ;
int capacity ;
int *array ;
} ;
struct arraystack *createstack ( int cap ) // create a stack ;
{
struct arraystack *stack ;
stack = malloc ( sizeof ( struct arraystack ) ) ;
stack-> top = - 1 ;
stack-> capacity = cap ;
stack-> array = malloc ( sizeof ( int ) * stack-> capacity ) ;
return ( stack ) ;
}
int full ( struct arraystack *stack ) // checking the stack is full or not.
{
if ( stack-> top == stack-> capacity - 1 )
return ( 1 ) ;
else
return ( 0 ) ;
}
int empty ( struct arraystack *stack ) // checking the stack is empty or not.
{
if ( stack-> top == -1 )
return ( 1 ) ;
else
return ( 0 ) ;
}
void push ( struct arraystack *stack , int item ) // insert elements in the stack ;
{
if ( !full ( stack ) )
{
stack-> top++ ;
stack-> array [ stack-> top ] = item ;
}
}
int pop ( struct arraystack *stack ) // remove elements from the stack ;
{
if ( !empty ( stack ) )
{
item = stack->array [ stack->top ] ;
stack-> top-- ;
return ( item ) ;
}
return ( -1 ) ;
}
int main()
{
int choice ;
struct arraystack *stack  ;
stack = createstack ( 4 ) ;
while( 1 )
{
printf ( " \n 1 . push " ) ;
printf ( " \n 2 . pop " ) ;
printf ( " \n 3 . exit \n " ) ;
printf ( " enter your choice \n " ) ;
scanf( "%d" ,&choice) ;
switch ( choice )
{
case 1:
printf ( " enter a number \n " ) ;
scanf( " %d ", &item) ;
push ( stack , item ) ;
break ;
case 2 :
item = pop ( stack ) ;
if ( item == - 1 )
printf ( " stack is empty " ) ;
else
printf ( " popped value is %d ",item ) ;
break ;
case 3:
exit ( 0 ) ;
}
}
return 0 ;
}
Output:
Explanation
As we said earlier, we define a user defined data type named arraystack. It has three data members named top, capacity, and a pointer array. Then, we define a function named createstack where we pass a value which the total block of array is created. The malloc() function creates this array and returns the address to the variable stack which is the arraystack type. The stack->array holds the address of the array which is created by the malloc() function.
Next, we define another function named full() to check if the stack is full or not.
Create another function named empty to check if the stack is empty.
Then, we define another function named push() where we insert the elements one by one in the stack from one end called top. To insert the element in the stack, we first check if the stack is full.
Then, we define another function named pop() where we delete the elements one by one from the stack from one end called top. To remove the element in the stack, we first check if the stack is empty.
Then, inside the main() function, we write the switch case to give the user a menu option to select his choice whether the element is inserted or deleted in the stack.
Conclusion
From the discussion about the stack, we have come to reach this conclusion that stack is a well-defined data structure which is used to manage the data in a structural way. Our daily life stack is implemented in various fields to store, insert, or delete elements.
