Before we study the basic building blocks of the C programming language, let us look at a bare minimum C program structure so that we can take it as a reference in the upcoming chapters.
A C program basically consists of the following parts −
Let us look at a simple code that would print the words "Hello World" −
#include <stdio.h> int main() { /* my first program in C */ printf("Hello, World! \n"); return 0; }
Let us take a look at the various parts of the above program −
The first line of the program #include <stdio.h> is a preprocessor command, which tells a C compiler to include stdio.h file before going to actual compilation.
The next line int main() is the main function where the program execution begins.
The next line /*...*/ will be ignored by the compiler and it has been put to add additional comments in the program. So such lines are called comments in the program.
The next line printf(...) is another function available in C which causes the message "Hello, World!" to be displayed on the screen.
The next line return 0; terminates the main() function and returns the value 0.
Let us see how to save the source code in a file, and how to compile and run it. Following are the simple steps −
Open a text editor and add the above-mentioned code.
Save the file as hello.c
Open a command prompt and go to the directory where you have saved the file.
Type gcc hello.c and press enter to compile your code.
If there are no errors in your code, the command prompt will take you to the next line and would generate a.out executable file.
Now, type a.out to execute your program.
You will see the output "Hello World" printed on the screen.
$ gcc hello.c $ ./a.out Hello, World!
Make sure the gcc compiler is in your path and that you are running it in the directory containing the source file hello.c.
It is possible to pass some values from the command line to your C programs when they are executed. These values are called command line arguments and many times they are important for your program especially when you want to control your program from outside instead of hard coding those values inside the code.
The command line arguments are handled using main() function arguments where argc refers to the number of arguments passed, and argv[] is a pointer array which points to each argument passed to the program. Following is a simple example which checks if there is any argument supplied from the command line and take action accordingly −
#include <stdio.h> int main( int argc, char *argv[] ) { if( argc == 2 ) { printf("The argument supplied is %s\n", argv[1]); } else if( argc > 2 ) { printf("Too many arguments supplied.\n"); } else { printf("One argument expected.\n"); } }
When the above code is compiled and executed with single argument, it produces the following result.
$./a.out testing The argument supplied is testing
When the above code is compiled and executed with a two arguments, it produces the following result.
$./a.out testing1 testing2 Too many arguments supplied.
When the above code is compiled and executed without passing any argument, it produces the following result.
$./a.out One argument expected
It should be noted that argv[0] holds the name of the program itself and argv[1] is a pointer to the first command line argument supplied, and *argv[n] is the last argument. If no arguments are supplied, argc will be one, and if you pass one argument then argc is set at 2.
You pass all the command line arguments separated by a space, but if argument itself has a space then you can pass such arguments by putting them inside double quotes "" or single quotes ''. Let us re-write above example once again where we will print program name and we also pass a command line argument by putting inside double quotes −
#include <stdio.h> int main( int argc, char *argv[] ) { printf("Program name %s\n", argv[0]); if( argc == 2 ) { printf("The argument supplied is %s\n", argv[1]); } else if( argc > 2 ) { printf("Too many arguments supplied.\n"); } else { printf("One argument expected.\n"); } }
When the above code is compiled and executed with a single argument separated by space but inside double quotes, it produces the following result.
$./a.out "testing1 testing2" Program name ./a.out The argument supplied is testing1 testing2
final variables will become constant,
final methods, restrict overriding concepts
final classes , restricts the inheritance concepts
will be explain with programs and examples in the next class
best example for the interface is OS you can explain your own how it is, we can implement poly morphism by using interfaces.
all the variables defined in the interface by default will become public, final i.e constants , these are used by implementing class
all the methods defined in the interface will become public, abstract methods
Recursion is the process of repeating items in a self-similar way. In programming languages, if a program allows you to call a function inside the same function, then it is called a recursive call of the function.
void recursion() { recursion(); /* function calls itself */ } int main() { recursion(); }
The C programming language supports recursion, i.e., a function to call itself. But while using recursion, programmers need to be careful to define an exit condition from the function, otherwise it will go into an infinite loop.
Recursive functions are very useful to solve many mathematical problems, such as calculating the factorial of a number, generating Fibonacci series, etc.
The following example calculates the factorial of a given number using a recursive function −
#include <stdio.h> unsigned long long int factorial(unsigned int i) { if(i <= 1) { return 1; } return i * factorial(i - 1); } int main() { int i = 12; printf("Factorial of %d is %d\n", i, factorial(i)); return 0; }
When the above code is compiled and executed, it produces the following result −
Factorial of 12 is 479001600
The following example generates the Fibonacci series for a given number using a recursive function −
#include <stdio.h> int fibonacci(int i) { if(i == 0) { return 0; } if(i == 1) { return 1; } return fibonacci(i-1) + fibonacci(i-2); } int main() { int i; for (i = 0; i < 10; i++) { printf("%d\t\n", fibonacci(i)); } return 0; }
When the above code is compiled and executed, it produces the following result −
0 1 1 2 3 5 8 13 21 34
Sometimes, you may come across a situation, when you want to have a function, which can take variable number of arguments, i.e., parameters, instead of predefined number of parameters. The C programming language provides a solution for this situation and you are allowed to define a function which can accept variable number of parameters based on your requirement. The following example shows the definition of such a function.
int func(int, ... ) { . . . } int main() { func(1, 2, 3); func(1, 2, 3, 4); }
It should be noted that the function func() has its last argument as ellipses, i.e. three dotes (...) and the one just before the ellipses is always an int which will represent the total number variable arguments passed. To use such functionality, you need to make use of stdarg.h header file which provides the functions and macros to implement the functionality of variable arguments and follow the given steps −
Define a function with its last parameter as ellipses and the one just before the ellipses is always an int which will represent the number of arguments.
Create a va_list type variable in the function definition. This type is defined in stdarg.h header file.
Use int parameter and va_start macro to initialize the va_list variable to an argument list. The macro va_start is defined in stdarg.h header file.
Use va_arg macro and va_list variable to access each item in argument list.
Use a macro va_end to clean up the memory assigned to va_list variable.
Now let us follow the above steps and write down a simple function which can take the variable number of parameters and return their average −
#include <stdio.h> #include <stdarg.h> double average(int num,...) { va_list valist; double sum = 0.0; int i; /* initialize valist for num number of arguments */ va_start(valist, num); /* access all the arguments assigned to valist */ for (i = 0; i < num; i++) { sum += va_arg(valist, int); } /* clean memory reserved for valist */ va_end(valist); return sum/num; } int main() { printf("Average of 2, 3, 4, 5 = %f\n", average(4, 2,3,4,5)); printf("Average of 5, 10, 15 = %f\n", average(3, 5,10,15)); }
When the above code is compiled and executed, it produces the following result. It should be noted that the function average() has been called twice and each time the first argument represents the total number of variable arguments being passed. Only ellipses will be used to pass variable number of arguments.
Average of 2, 3, 4, 5 = 3.500000 Average of 5, 10, 15 = 10.000000
Deque is a data structure that inherits the properties of both queues and stacks. Additionally, the implementation of this data structure requires constant time, i.e., time complexity = O(1). This means you can use deque to your advantage to implement both the queue and stack. So, in this tutorial, you will discover deque in a data structure to understand its functionalities and applications.
Deque is a more generalized version of a linear queue. As you know, the linear queue has some restrictions while performing the insertion and deletion of elements. The insertion in a linear queue must happen from the rear end and deletion from the front end. But, in deque, you can perform both insertion and deletion operations at both of its ends. That’s why it is called a Double-Ended Queue (Deque).
The image above represents how different operations take place at both ends of the deque.
Now, you will look into the primary properties of deque in a data structure.
The insertion and deletion in deque can be limited to one node. When you do that, the deque becomes a stack. Hence, it follows the Last In First Out Principle for insertion and deletion.
As shown in the image above, initially, there were four elements inside this deque. However, after repeating the removal of an element twice, data elements 2 and 12 get removed from the deque, respectively. You inserted element 2 at last and removed it at first. This example demonstrates the LIFO principle.
As deque can operate on both ends, you can extract queue properties by limiting insertion at the front node and removal at the rear node. Doing this will allow deque to act as a linear queue.
As shown in the image above, the element which enters at first will also leave the queue first. This is how deque can use the FIFO principle to perform insertion and deletion.
There are two types of deque which are created by restricting certain operations. Let’s clearly understand them.
Four basic operations are performed on deque, they are as follows:
Along with these primary operations, you can also perform isEmpty(), isFull() and Peek() operations. These operations are called supportive queue operations. But, in this tutorial, you will only implement primary queue operations. The time required to implement all these functions must be constant, i.e., time-complexity = O(1).
The Deque can be implemented using either a circular queue or a doubly-linked list. The circular queue implementation of the deque is the most straightforward approach to implement a double-ended queue. Hence, in this tutorial, you will only focus on the circular queue representation of deque. Primarily, understand what a circular queue is.
A circular queue is an extended version of a linear queue as it follows the First In First Out principle with the exception that it connects the last node of a queue to its first, by forming a circular link. Hence, it is also called a Ring Buffer. The illustration of a circular queue below shows the connectivity between the queue’s first and last node.
Additionally, a circular queue manages memory efficiently because of its circular link. If the rear pointer has reached the maxsize of a queue, it will again arrive at the beginning of a queue. Bringing the rear node to the beginning of a queue is called circular incrementation. The image given below shows how to achieve circular incrementation.
You must be clear about the concept of a circular queue. Now, moving ahead, you will look into how to implement the deque using a circular queue.
To implement deque using a circular queue, you should be able to implement the insertion and deletion at both ends of a queue. Let’s begin with implementing insertion at both ends.
First, understand insertion using the rear node with the help of an example.
Initially, there is only one element inside the queue. Hence, both front and rear are pointing to the index 0. Additionally, as you are inserting elements using a rear node, its incrementation will bring you to the empty space for putting in a new element. The image shown above represents how insertion occurs using a rear pointer.
Let’s deal with the insertion using a front pointer. Consider the example given below. In this example, a front node points to index 0, and now you want to insert elements using it. In order to do that, set the front pointer to MAXSIZE - 1. Doing this will allow your front pointer to reach the end of a queue. After that, you can insert a new element at this new location (index 5). But, for further insertions, you will just decrement the value of a front pointer.
The diagrammatic representation above explains insertion at front operation.
Consider the diagrammatic representation of a circular array given below. In this representation, a front node is pointing to index 4 and a rear node to index 2. Now, to perform the deletion, you will have to increase the location of the front pointer until it reaches the maxsize of a queue. For further deletions, set a front pointer to index 0. The diagram below will help you to visualize that.
The diagrammatic representation given below explains how you can perform deletion operations using a front node.
In this example, the rear node is at index 2. To perform the removal of elements, reduce the location of a rear pointer until it arrives at index 0. Once it reaches the index 0, you will either set it to MAXSIZE - 1 (if there are elements inside the queue) or -1 along with front = -1 (if there is no element inside the queue).
Once you are clear with the different cases for both insertion and deletion, you will dive into the implementation of deque in a data structure.
As mentioned previously, you will implement four main primary deque operations as listed below:
You will use the C programming language to implement deque in data structure using a circular array (Queue).
#include<stdio.h> #include<iostream> //Global scope #define size 5 int dq[100]; int front = -1, rear =-1; //Insertion from front void front_Enqueue(int z) { if((front==0 && rear==size-1) || (front==rear+1)) { printf("deque is full, Insertion is not possible"); } else if((front==-1) && (rear==-1)) { front=rear=0; dq[front]=z; } else if(front==0) { front=size-1; dq[front]=z; } else { front=front-1; dq[front]=z; } } // insertion from rear end void rear_Enqueue(int z) { if((front==0 && rear==size-1) || (front==rear+1)) { printf("deque is full"); } else if((front==-1) && (rear==-1)) { rear=0; dq[rear]=z; } else if(rear==size-1) { rear=0; dq[rear]=z; } else { rear++; dq[rear]=z; } } //function to analyze state of queue. void display() { int i=front; printf("\n Elements inside the double ended queue are : "); while(i!=rear) { printf("%d ",dq[i]); i=(i+1)%size; } printf("%d",dq[rear]); } void front_Dequeue() { if((front==-1) && (rear==-1)) { printf("There is no element to delete inside a deque"); } else if(front==rear) { printf("\nThe deleted element from the front is %d", dq[front]); front=-1; rear=-1; } else if(front==(size-1)) { printf("\nThe deleted element from the front is %d", dq[front]); front=0; } else { printf("\nThe deleted element from the front is %d", dq[front]); front=front+1; } } // dequeue_rear() function deletes the element from the rear void rear_Dequeue() { if((front==-1) && (rear==-1)) { printf("Deque is empty"); } else if(front==rear) { printf("\nThe deleted element from rear is %d", dq[rear]); front=-1; rear=-1; } else if(rear==0) { printf("\nThe deleted element from the rear node is %d", dq[rear]); rear=size-1; } else { printf("\nThe deleted element from rear node is %d", dq[rear]); rear = rear-1; } } int main() { front_Enqueue(-5); front_Enqueue(23); rear_Enqueue(17); rear_Enqueue(12); rear_Enqueue(47); display(); front_Dequeue(); rear_Dequeue(); display(); return 0; } |
The display() function implemented in this program is an additional function that you have to implement to visualize the state of a deque. The image given below is the output that you will receive after running this code in a compiler.
The deque can act as both the queue and stack. Thus, all the applications of queue and stacks can be implemented using a double-ended queue. Given below are some critical applications of deque in data structure:
The string or a number that reads the same backward as forward is known as a palindrome. The program to check if the given string is palindrome or not can be implemented using deque in a data structure. If the string reads the same from both the deque ends, it will consider it a palindrome. The image given below is an illustration of a palindrome checker implementation using a double-ended queue.
When multiple processes are being executed by multiple processors (CPU, Core) in a system, then that system utilizes a multiprocessor scheduling algorithm. In this algorithm, the deque is used by each processor to store different threads of processes. This algorithm is also called the A-Steal algorithm for scheduling. The illustration given below represents the process of multiprocessor scheduling.
In this tutorial, you explored the deque in a data structure in detail. You went through different properties and types of deque along with its representation using a circular queue. You also understood the operations in deque with the help of a pictorial representation. Finally, you also discovered different applications of deque to understand its importance.
A deque, also known as a double-ended queue, is an ordered collection of items similar to the queue. It has two ends, a front and a rear, and the items remain positioned in the collection. What makes a deque different is the unrestrictive nature of adding and removing items. New items can be added at either the front or the rear. Likewise, existing items can be removed from either end. In a sense, this hybrid linear structure provides all the capabilities of stacks and queues in a single data structure. Figure 1 shows a deque of Python data objects.
It is important to note that even though the deque can assume many of the characteristics of stacks and queues, it does not require the LIFO and FIFO orderings that are enforced by those data structures. It is up to you to make consistent use of the addition and removal operations.
