Stack And Queu

Stack and Queue

Stack: Elements can be inserted and deleted only from one side of the list, called the top. The insertion of an element is called push operation and the deletion of an element is called pop operation.

Queue: Elements can be inserted only from one side of the list called Rear, and the elements can be deleted only from the other side called the Front. It’s the insertion of an element in a queue is called an Enqueue operation and the deletion of an element is called a Dequeue operation.

• There are several types of queues such as : Simple Queue, Circular Queue, Priority Queue and Double Ended Queue
• We can implement a stack and queue using both array and linked list.
• Stack Applications: During Function Calls and Recursive Algorithms, Expression Evaluation, Undo feature in computer keyboard, Converting an Infix to Postfix, During Depth First Search (DFS) and Backtracking Algorithms etc.
• Queues Applications: Simulation, Scheduling, Shared Resource Management, Keyboard Buffer, Breadth-First Search, To handle congestion in the network etc.

Hashing Table and Binary Tree

Hashing Table

Hash Table: Hash table is a method/mechanism of finding a record in a table/list using a key. Suppose we have n record and m key values where m >= n then it for every key if there exist a record n then it a hash table where m is a hash key.

Hash key: Hash key is a unique number which can be converted to a record in a record in a hash table. Here there is a mapping function h(m) which maps each hash key to corresponding records. This function is called hash function.

Hash function: Hash function is a mapping function of hash table which takes the key number as input and gives out the index of the record.
n = h(m) (where m >=n)
Here is a very simple hash function like mod. Suppose we have maximum 10 records. Then we can easily map key to index of record n by mod(m). It directly gives us the record number.
n = mod 10 (m)

In a perfect hash table where m >=n there is always record index for a key. When m > n then more than one key may map to a same record. This situation is called hash collision.

Hash collision: If more than one hash key can be mapped to a single record in a hash table then it is called has collision. Example: Say in our example key values ranges from 0 to 9. If we take 10 or more as key then say key m=1 corresponds to record n=1. Now key m=11 also maps to the same record as mod10(11)=1.

There are three popular techniques to avoid collision

• Linear probing,
• Chaining,
• Re-hashing

Linear probing
In linear probing records are placed to the next neighborhood of the colliding record.

Chaining
Chaining is the technique to remap colliding record to a new linked list chain.

Re-hashing
Re-hashing is the second level of hash table with these new colliding records.

Binary Tree

A binary tree is a method of placing and locating files (called records or keys) in a database, especially when all the data is known to be in random access memory (RAM). The algorithm finds data by repeatedly dividing the number of ultimately accessible records in half until only one remains.

In a tree, records are stored in locations called leaves. This name derives from the fact that records always exist at end points; there is nothing beyond them. Branch points are called nodes. The order of a tree is the number of branches (called children) per node. In a binary tree, there are always two children per node, so the order is 2. The number of leaves in a binary tree is always a power of 2. The number of access operations required to reach the desired record is called the depth of the tree. The image to the left shows a binary tree for locating a particular record among seven records in a set of eight leaves. The depth of this tree is 4.

In a practical tree, there can be thousands, millions, or billions of records. Not all leaves necessarily contain a record, but more than half do. A leaf that does not contain a record is called a null. In the example shown here, the eighth leaf is a null, indicated by an open circle.

Binary trees are used when all the data is in random-access memory (RAM). The search algorithm is simple, but it does not minimize the number of database accesses required to reach a desired record. When the entire tree is contained in RAM, which is a fast-read, fast-write medium, the number of required accesses is of little concern. But when some or all of the data is on disk, which is slow-read, slow-write, it is advantageous to minimize the number of accesses (the tree depth). Alternative algorithms such as the B-tree accomplish this.

Perbedaan Array Dan Linked List

Perbedaan Array Dan Linked List

Program stack menggunakan array.

• Proses inisialisasi dimana proses ini untuk stack yang menggunakan array adalah dengan mengisi nilai field top dengan 0 (nol), jika elemen pertama diawali dengan nomor 1. Kalau elemen pertama array dimulai dengan 0 (contoh bahasa c), maka top di isi dengan nilai -1.
• Top yang menunjuk posisi data terakhir (top).
• Elemen yang berisi data yang ada dalam stack. Bagian ini lah yang berbentuk array.
• Maks-elemen yaitu variabel yang menunjuk maksimal banyaknya elemen dalam stack.

Program stack menggunakan linked list.
Adapun stack yang menggunakan linked list, hanya memerlukan suatu pointer yang menunjuk ke data terakhir (perhatikan proses dihalaman sebelumnya), setiap elemen linked list mempunyai 2 field yaitu elemen datanya dan pointer bawah yang menunjuk posisi terakhir sebelum proses push