Stack
Stack is a linear data structure. In stack, data access is limited. It follows the rule of insertion and deletion of data. Stack is a collection of only similar data types. Elements in the stack are arranged sequentially. It follows the LIFO principle which is the last-in and first-out rule.
Example
To understand this concept, let us take an example of arranging coins. If we start placing coins one after the other in such a way that the first coin will be placed first at the bottom and the next coin will come on above the first coin and so on. Now if we want to remove coins, then the topmost coin which is the third coin will be removed first. So in this way, the last coin will be removed first according to the LIFO principle.
Working Principle Of Stack
Insertion and deletion can be performed from only one side. Stack follows the LIFO principle. LIFO means last in and first out. If we want to place an element into the stack, it will be placed at the top of the stack. Similarly, if we want to delete an element from the stack, it will be deleted from the top of the stack. Initially, there will be no elements in the stack so the top will be equal to ‘-1’.
Operations On Stack
It has two fundamental operations:
Push Operation
The operation of putting an element into a stack is called ‘’push’’. It can be written as :
Push(x)
Where ‘x’ is the data of the same type.
POP Operation
The process of deleting an element from the stack is called ‘’POP’’. It can be written as :
POP( )
In pop operation, no argument will be passed.
Top Operation
It is also called peak operation. It will return the topmost element of the stack without removing that element from the stack. It can be represented as :
T op( )
Isempty Operation
It is true if the stack is empty. It can be written as:
isempty( )
Isfull Operation
It will give true if the stack is full. It can be denoted as :
isfull ( )
Representation of Stack
Stack is represented by a container as shown below. This container has one open end from where data can be inserted or deleted. We need to allocate memory in this stack. So for this purpose, we have to find the size of this stack to add some data to this stack. Suppose if the size of the stack is 6. It means that it can store only six elements from 0 to 5. In the beginning, the top will be -1. If we call the pop( ) operation in this situation, no element will be removed due to the empty stack. So this will be an underflow condition. And if element ‘2’ is called, There will be two methods to allocate memory in this stack:
Static Memory Allocation.
In this method, the stack is implemented using arrays.
Dynamic Memory Allocation.
In this method, a linked list is used to implement the stack.
Implementation of Stack Using Array
A stack can be implemented by using an array with the help of static memory allocation. When we implement stack using, we first need to check overflow and underflow conditions. Overflow condition occurs when we insert an element to the stack which is already having maximum elements. While underflow conditions occur when we delete an element from an empty stack.
Let us consider that an array ‘A’ and integer having data size 6. Now 6 blocks will be allocated in memory for this array. And we will represent this array in stack form using ‘int stack’. Now different stack functions will be defined and then will be called in the main function. Data will be inserted into the stack using 'push()' function. Now 'pop( )' operation will be defined. We will pass no element in the pop function because always top element will be popped out in this. For displaying the topmost deleted value, firstly this top value will be stored in some variable ‘x’ and then that value will be displayed. Then 'display()' the function will be used to traverse the stack.
int A[6].
int T = -1 ;
void push ( )
{
if ( T = = 5 ){
printf ("Overflow")
}else{
T ++;
A [T] = element;
}
}
void pop ( ){
if( T == -1 ){
printf("Underflow state")
}else{
element = A[T];
T --;
}
}
void display ( ){
if( T != -1 ){
for( y = T ; y > = 0 ; y --){
printf ("%d", A [y])
}
}else{
printf ( “Stack is empty ” );
}
}Implementation of Stack Using Linked List
In this, we will first specify dynamic memory allocation. The singly-linked list will be used in this implementation. A node will consist of data and address fields. There is also a head part that contains the address of the first node. It will follow the LIFO principle. Firstly structure will be created for a node. The insertion and deletion operation will be performed from the beginning of the list.
struct node
{
int x;
struct node * pointer;
}
struct node *T = 0;
void push ( int z ){
struct node* n_node;
n_node = (struct*node) malloc (size of( struct node));
x = z;
next = T;
T= n_node;
}
void display ( ) {
struct node * tp ;
tp = T ;
if( T== 0 ){
print f( “list empty”)
}else {
while( tp != 0){
printf ("%d", x );
}
tp = pointer ;
}
}
void peek ( ){
if ( T == 0 ){
printf("Empty Stack")
}else{
printf("Top Element %d", x );
}
}
void pop ( ){
struct node*tp;
tp = T;
if( T == 0 ){
printf("Underflow State");
}else{
printf ("%d", x );
T = pointer;
}
}Queue
The queue is a linear data structure. Elements are arranged sequentially. The data structure is a method of storing and organizing data. The queue is an abstract data type. The queue is an ordered less structure that follows the principle of FIFO ( First in first out). So the elements that will be inserted first, will also be removed first.
Example
To understand this concept, let's take an example of persons standing in a line for reserving a train ticket. The person who is standing first in the line will get his ticket first. Similarly, the person standing at the last will get his ticket at last.
In Queue, insertion is performed from one end which is known as ‘Rear’. The deletion process is performed from the other end in the queue which is called ‘Front’.
enqueue( )
The insertion process in the queue is named ‘enqueue( )’.
dequeue ( )
The deletion process in a queue is named ‘dequeue ( )’.
Representation of Queue
A queue has two open ends i.e rear and front. The data will be inserted from the rear end. And the data will be deleted from the front end. If this queue has four elements i.e 5,6,7 and 8 at index 0,1,2 and 3.So front end will point towards 5 and the read end will point towards 8. To insert another element, the rear side variable will be incremented. Similarly, for deleting any element, the font side variable will be decremented.
Operations On Queue
It has the following major operations:
enqueue ( )
Its purpose is to add an element to the queue. This operation is performed at the rear end.
dequeue ( )
Its purpose is to delete an element from the queue. In this operation, we pass no data to the queue. This operation is performed at the front end.
front ( )
This operation is to find the element at the front of the queue without removing that element.
isfull ( )
This operation will return true if the queue is full.
isempty ( )
This operation will return true if the queue is empty.
Implementation of Queue Using Array
Now we will implement a queue using an array. Implementation of queue follows FIFO rule. During its implementation, overflow and underflow conditions will be checked. For this let us consider an array B. Static memory location will be used to allocate this array. So firstly array will be declared with data type ‘int’ and assume its size ‘6’.Now front and rear variables will be taken and initialized with ‘-1’ because the queue is empty. Now enqueue function will be defined and the integer variable ‘y’ will be passed to it. Then an overflow condition will be checked.
int B [ 6 ];
int F = -1;
int R= -1;
void enqueue( int y ){
if(R == 5){
printf ("overflow state");
}else if(F == -1 & R == -1){
F= R=0;
B[R] = y;
}else{
R++;
B[R] = y;
}
}
void dequeue () {
if (F == -1 && R == -1){
printf("Under flow Condition")
}else if( F == R ){
F = R = -1;
}else{
printf("%d", B[F])
F++;
}
}To display the above data in the queue, let us see the following code:
void display (){
if(F == -1 && R==-1){
printf("Queue is Empty")
}else{
for( g = F ; g < R+1 ; g++){
printf("%d" , B[g])
}
}
}For peek operation:
peek(){
if( F == -1 && R == -1 ){
printf("Queue is Empty")
}else{
printf("%d" , B[F]);
}
}Implementation of Queue Using Linked List
By using a linked list, a queue is implemented by dynamic memory allocation. It will follow the FIFO principle in this method. The linked list comprises different nodes with data and the next address field.
struct node
{
Int data;
struct node* next;
}
struct node * F = 0;
struct node * R = 0;
void enqueue ( int y ){
struct node * n_node ;
n_node = ( struct node * ) malloc ( size of ( struct node ));
data = y;
next = 0;
if(R== 0){
F=n_node;
R=n_node;
}else{
R -> next = n_node ;
R=n_node;
}
}
void dequeue ( ){
if(F== 0){
printf("Queue is empty");
}else{
tp = F;
F= F -> next;
tp -> next = 0;
free(tp);
}
}
void display ( ){
if( F==0)
printf("Queue empty");
}else{
while( tp ! = 0){
printf("%d", data )
tp= tp -> next;
}
}
}Application of Stack
Following are the applications of the stack:
Stack is used to reversing a string.
It Is used to evaluate prefix infix or postfix expression.
Also used to convert one form of expression to another.
It can also be used in recursion or function call operation.
Also used to check the balance of the parenthesis.
Application of Queue
It has the following applications:
It is used in customer care services
It is used in the breadth-first search.
Also used in buffer and pipes etc.
It is also used to serve a request on a single shared resource.