Queues in C++

/* 

 * File:   queue.cpp
 * Author: dk
 *
 * Created on September 9, 2016, 5:06 PM
 * Note : Implementation of Queues with only head pointer, enqueue is O(1) and
 *        dequeue is O(n) operation.
 */
#include <iostream>

using namespace std;

struct queue_node{

    int var;
    queue_node *next;
};


queue_node *EnQueue(queue_node **head , int val){

    queue_node *temp = (*head);

    queue_node *new_node = new queue_node;
    temp->var = val;
    new_node->next = NULL;

    if (temp != NULL)
        new_node->next = (*head);

    (*head) = new_node;

    return new_node;
}

int QueueSize(queue_node **head){

    queue_node *temp = (*head);
    int queue_size = 0;

    while (temp->next != NULL) {
        ++queue_size;
        temp = temp->next;
    }
    return queue_size;
}

void DeQueue(queue_node **head){
 
    queue_node *temp = (*head);
    queue_node *prev = (*head);
 
    if(temp->next == NULL){
        cout << "Empty Queue" << endl;
        return;
    }
 
    while(temp->next != NULL) {
     
        prev = temp ;
        temp = temp->next;
    }
 
    prev->next = NULL;
    cout << "Dequeued value is : " << temp->var << endl;
 
    delete temp;
}

/*
 *
 */
int main(int argc, char** argv) {
 
    queue_node *head = new queue_node;
 
    head->next = NULL;
 
    EnQueue(&head , 1);
    EnQueue(&head , 2);
    EnQueue(&head , 3);
    EnQueue(&head , 4);
    cout << "Queue Size : " << QueueSize(&head) << endl;

    DeQueue(&head);
    DeQueue(&head);
    DeQueue(&head);
    DeQueue(&head);
    cout << "Queue Size : " << QueueSize(&head) << endl;
    DeQueue(&head);
 
    delete head;
    return 0;
}


Output :

Queue Size : 4
Dequeued value is : 1
Dequeued value is : 2
Dequeued value is : 3
Dequeued value is : 4
Queue Size : 0
Empty Queue

Stack In C++

#include <iostream>

using namespace std;

typedef struct stack_node{

    int var;
    stack_node *next;
};

stack_node *Push(stack_node **head , int val){

    stack_node *temp = (*head);

    stack_node *new_node = new stack_node;
    new_node->var = val;
    new_node->next = NULL;

    if (temp != NULL)
        new_node->next = (*head);

    (*head) = new_node;

    return new_node;
}

int StackSize(stack_node **head){

    stack_node *temp = (*head);
    int stack_size = 0;

    while (temp->next != NULL) {
        ++stack_size;
        temp = temp->next;
    }
    return stack_size;
}

void Pop(stack_node **head){

    stack_node *temp = (*head);

    if (temp != NULL)
        (*head) = temp->next;

    cout << "Poped node value is : " << temp->var << endl;
    delete temp;
}

int main()
{
    stack_node *head = new stack_node;

    head->next = NULL;

    Push( &head , 10);
    Push( &head , 5);
    Push( &head , 3);
    Push( &head , 9);

    cout << "Stack Size : " << StackSize(&head) << endl;

    Pop(&head);
    cout << "Stack Size : " << StackSize(&head) << endl;

    Pop(&head);
    cout << "Stack Size : " << StackSize(&head) << endl;

    Pop(&head);
    cout << "Stack Size : " << StackSize(&head) << endl;

    Pop(&head);
    cout << "Stack Size : " << StackSize(&head) << endl;

    return 0;
}

#include <iostream>

using namespace std;

typedef struct stack_node{

    int var;
    stack_node *next;
};

stack_node *Push(stack_node **head , int val){

    stack_node *temp = (*head);

    stack_node *new_node = new stack_node;
    new_node->var = val;
    new_node->next = NULL;

    if (temp != NULL)
        new_node->next = (*head);

    (*head) = new_node;

    return new_node;
}

int StackSize(stack_node **head){

    stack_node *temp = (*head);
    int stack_size = 0;

    while (temp->next != NULL) {
        ++stack_size;
        temp = temp->next;
    }
    return stack_size;
}

void Pop(stack_node **head){

    stack_node *temp = (*head);

    if (temp != NULL)
        (*head) = temp->next;

    cout << "Poped node value is : " << temp->var << endl;
    delete temp;
}

int main()
{
    stack_node *head = new stack_node;

    head->next = NULL;

    Push( &head , 10);
    Push( &head , 5);
    Push( &head , 3);
    Push( &head , 9);

    cout << "Stack Size : " << StackSize(&head) << endl;

    Pop(&head);
    cout << "Stack Size : " << StackSize(&head) << endl;

    Pop(&head);
    cout << "Stack Size : " << StackSize(&head) << endl;

    Pop(&head);
    cout << "Stack Size : " << StackSize(&head) << endl;

    Pop(&head);
    cout << "Stack Size : " << StackSize(&head) << endl;

    return 0;
}

Output:

Stack Size : 4

Poped node value is : 9

Stack Size : 3

Poped node value is : 3

Stack Size : 2

Poped node value is : 5

Stack Size : 1

Poped node value is : 10

Stack Size : 0

ASCII to hex conversion

Sometimes one need to convert from a ASCII  to hex of a particular character. Here is a small function that will take care of that need. It will convert only 0 .. 9 , a .. f , A .. F , rest of the character will be returned as it is.

char atoh(char ch){

    if(ch >= 0x30 && ch <= 0x39){
        return (ch - 0x30);
    }else if(ch >= 0x41 && ch <= 0x46){
        return (ch - 0x37);
    }else if(ch >= 0x61 && ch <= 0x66){
        return (ch - 0x57);
    }else{
        return ch;
    }
}

Pointer to a function/Function pointer

In c we can use pointer to point to function also. It's similar to a pointer to a int or char or a struct. when we declare pointer to a function it points to a code sitting in a memory for a function. following example shows the use of function pointer

#include <stdio.h>

// Simple function to add 2 number

int sum(int x, int y){

        return x+y;

}

// use of typedef to declare a function pointer 

typedef int (*funct_ptr)(int a , int b);

int main(){

        int (*ptr)(int,int);   // deceleration of  function pointer 

        ptr = &sum;          // Initialize the pointer to point to a function sum

        funct_ptr ptr1;      // this will show how to use typedef to declare pointer variable.

        int sumation;

        sumation = (*ptr)(3,4);    // call the function using pointer 

        printf("sum is %d \n",sumation);

        ptr1 = sum;                     //  Second type of call for a function pointer

        sumation = ptr1(3,5);

        printf("sum is %d \n",sumation);

        return 0;

}


Output:

sum is 7
sum is 8

Another example of function pointer is as mentioned below. Function pointer can be used inside a structure to access the data member of a structure. By default C does not support Function inside a structure.

#include <stdio.h>
#include <stdlib.h>

typedef void (*fp_set)(int, int, int);
typedef long (*fp_cal)();

struct volume
{
int h;
int b;
int l;
fp_set setval;
fp_cal calvol;
};
typedef struct volume vol;
static vol v;

void set(int a, int b , int c)
{
v.h = a;
v.b = b;
v.l = c;
}

long cal()
{
return v.h*v.b*v.l;
}

int main()
{
v.setval= set;
v.calvol = cal;

v.setval(4,5,6);
printf("volume is %ld \n",v.calvol());

return 0;
}

Output:

volume is 120