ALL SUMMARY DATA STRUCTURE

LINKED LIST

A linked list is a linear data structure, but the elements aren't stored at the contagious location, but the elements are linked using pointers.

Why we must use linked list:
 - you must know that array has a fixed size, so we must know the upper limit of an array, and also the memory allocation is equal to the array upper limit. 

// A linked list node
struct Node {
    int data;
    struct Node* next;
};

References: https://www.geeksforgeeks.org/linked-list-set-1-introduction/

SUMMARY STACK AND QUEUE DATA STRUCTURES

Stack is a data structure that stores its elements in an ordered manner, and it follows a particular order in which the operations are performed. The order may be LIFO (Last in First out) or FILO (First in Last out). The following three basic operations are performed in the stack:
  • Push: Adds an item in the stack. If the stack is full, then it is said to be an Overflow condition.
  • Pop: Removes an item from the stack. The items are popped in the reversed order in which they are pushed. If the stack is empty, then it is said to be an Underflow condition.
  • Peek or Top: Returns the top element of the stack.
  • isEmpty: Returns true if the stack is empty, else false.
The applications of the stack are:
// C program for array implementation of stack
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
  
// A structure to represent a stack
struct Stack {
    int top;
    unsigned capacity;
    int* array;
};
  
// function to create a stack of given capacity. It initializes size of
// stack as 0
struct Stack* createStack(unsigned capacity)
{
    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
    stack->capacity = capacity;
    stack->top = -1;
    stack->array = (int*)malloc(stack->capacity * sizeof(int));
    return stack;
}
  
// Stack is full when top is equal to the last index
int isFull(struct Stack* stack)
{
    return stack->top == stack->capacity - 1;
}
  
// Stack is empty when top is equal to -1
int isEmpty(struct Stack* stack)
{
    return stack->top == -1;
}
  
// Function to add an item to stack.  It increases top by 1
void push(struct Stack* stack, int item)
{
    if (isFull(stack))
        return;
    stack->array[++stack->top] = item;
    printf("%d pushed to stack\n", item);
}
  
// Function to remove an item from stack.  It decreases top by 1
int pop(struct Stack* stack)
{
    if (isEmpty(stack))
        return INT_MIN;
    return stack->array[stack->top--];
}
  
// Function to return the top from stack without removing it
int peek(struct Stack* stack)
{
    if (isEmpty(stack))
        return INT_MIN;
    return stack->array[stack->top];
}
  
// Driver program to test above functions
int main()
{
    struct Stack* stack = createStack(100);
  
    push(stack, 10);
    push(stack, 20);
    push(stack, 30);
  
    printf("%d popped from stack\n", pop(stack));
  
    return 0;
}
    Same as a stack, a queue is a data structure that stores its elements in an ordered manner. The order is FIFO (First in First Out). Mainly the following four basic operations are performed on queue:
    • Enqueue: Adds an item to the queue. If the queue is full, then it is said to be an Overflow condition.
    • Dequeue: Removes an item from the queue. The items are popped in the same order in which they are pushed. If the queue is empty, then it is said to be an Underflow condition.
    • Front: Get the front item from the queue.
    • Rear: Get the last item from the queue.
    // C program for array implementation of queue
    #include <stdio.h>
    #include <stdlib.h>
    #include <limits.h>
      
    // A structure to represent a queue
    struct Queue
    {
        int front, rear, size;
        unsigned capacity;
        int* array;
    };
      
    // function to create a queue of given capacity. 
    // It initializes size of queue as 0
    struct Queue* createQueue(unsigned capacity)
    {
        struct Queue* queue = (struct Queue*) malloc(sizeof(struct Queue));
        queue->capacity = capacity;
        queue->front = queue->size = 0; 
        queue->rear = capacity - 1;  // This is important, see the enqueue
        queue->array = (int*) malloc(queue->capacity * sizeof(int));
        return queue;
    }
      
    // Queue is full when size becomes equal to the capacity 
    int isFull(struct Queue* queue)
    {  return (queue->size == queue->capacity);  }
      
    // Queue is empty when size is 0
    int isEmpty(struct Queue* queue)
    {  return (queue->size == 0); }
      
    // Function to add an item to the queue.  
    // It changes rear and size
    void enqueue(struct Queue* queue, int item)
    {
        if (isFull(queue))
            return;
        queue->rear = (queue->rear + 1)%queue->capacity;
        queue->array[queue->rear] = item;
        queue->size = queue->size + 1;
        printf("%d enqueued to queue\n", item);
    }
      
    // Function to remove an item from queue. 
    // It changes front and size
    int dequeue(struct Queue* queue)
    {
        if (isEmpty(queue))
            return INT_MIN;
        int item = queue->array[queue->front];
        queue->front = (queue->front + 1)%queue->capacity;
        queue->size = queue->size - 1;
        return item;
    }
      
    // Function to get front of queue
    int front(struct Queue* queue)
    {
        if (isEmpty(queue))
            return INT_MIN;
        return queue->array[queue->front];
    }
      
    // Function to get rear of queue
    int rear(struct Queue* queue)
    {
        if (isEmpty(queue))
            return INT_MIN;
        return queue->array[queue->rear];
    }
      
    // Driver program to test above functions./
    int main()
    {
        struct Queue* queue = createQueue(1000);
      
        enqueue(queue, 10);
        enqueue(queue, 20);
        enqueue(queue, 30);
        enqueue(queue, 40);
      
        printf("%d dequeued from queue\n\n", dequeue(queue));
      
        printf("Front item is %d\n", front(queue));
        printf("Rear item is %d\n", rear(queue));
      
        return 0;
    }
      Reference: https://www.geeksforgeeks.org/queue-set-1introduction-and-array-implementation/
                        https://www.geeksforgeeks.org/stack-data-structure-introduction-program/
                        BINUS MAYA Stack and Queue
      Hash Table
      Hash table is a data structure that stores data in an array format, where each data has a unique index value. With hashing, access to data will become faster.
      Hash Function
      Syntax of hash table:
      struct DataItem {
   int data;
   int key;
};
      Hash methods:

      int hashCode(int key){
   return key % SIZE;
}


      Binary Tree
      A binary tree is a tree whose elements have maximal 2 children. The binary tree contains:
      1. Data
      2. Pointer of the left child
      3. Pointer of the right child
      tree
      ----
       j    <-- root
     /   \
    f      k  
  /   \      \
 a     h      z    <-- leaves
      Syntax of a binary tree:
      struct node 
      {
        int data;
        struct node *left;
        struct node *right;
      };


      Comments

      Post a Comment