Skip to main content

Stack & Queue

Stack

Stack is type of data structure that store it's data in an orderly manner. Data in stack can only be removed and added from one end of the data. This is called LIFO (Last in First Out) Meaning that the last data that enter will be the first one to be removed. Stack can be implemented with array or linked list. Stack is usually used in backtracking algorithm and also used when making a recursive function (Depth First Search).

Queue

Queue is also a type of data structure but it's main difference from stack is that in queue data can only be added from behind and data can only be removed from the front of the queue just like a real life queue. This is called FIFO (First In First Out) meaning that the first data that is inserted will be the one that is removed first. Also like stack queue can be implemented with array or linked list. Now queue is used in an algorithm called Breath First Search.
Image result for queue data structure
Queue also have another type called Circular Queue

Circular Queue

A circular queue is a queue but it's front and rear is connected making it looked like a circle
Image result for circular queue data structure
Why did we use circular queue because in a normal queue we cannot insert a new data into the queue when the last place of the queue is used even when the front is empty because in queue you can only insert the data in the back of the queue. Because of this we use circular queue so that we could still insert data even if the rear data is full.

Priority Queue

A priority queue is a queue but all element of the queue is assigned a priority. This queue have some general rule :
  1. An element that have a higher priority will be served first before an element with a lower priority.
  2. If two or more element have the same priority they will be served based on the First Come First Served (FCFS) basis.

Prefix, Infix, and Postfix

Prefix, Infix, Postfix is how we write a mathematical equation. Why we have to use Prefix and Postfix because using these two we do not need bracket to prioritize operator precedence and Prefix and Postfix is easier to evaluate by the computer.

Infix

Infix is written with the operator sandwiched by the operand 
operand operator operand
example ; 

operand >> 74 or 8 or 14
operator >> + or - or ^ 
  • 17 + 8
  • 17 / 5 * 8 + 78
  • 78 * (15 + 75) ^ 2
So Infix is how we usually write mathematical equation

Prefix

Prefix is written with the operator on the left of both the operand
operator operand operand
example : 
  • + 17 8 from 17 + 8
  • / 17 + * 5 8 78 from 17 / 5 * 8 + 78
  • * 78 ^ 15 75 2 from 78 * (15 + 75) ^ 2
So as we could see when we convert infix to prefix the bracket will disappear.

Postfix

Postfix is written with the operator in the right of the both operand
operand operand operator
example : 
  • 17 8 + from 17 + 8
  • 17 5 8 * / 78 + from 17 / 5 * 8 + 78
  • 78 15 5 + 2 ^ * from 78 * (15 + 75) ^ 2
Same with prefix the bracket will disappear when converted to postfix from infix

Comments

Post a Comment

Popular posts from this blog

Linked List Linked List a sequence of data structure connected together via links. In C a list is usually composed of multiple type of data so we usually use struct so that we can insert multiple amount of data into a single list, also our list also contain a reference(pointer in C) to the next list. So because of this reference our list linked to one another and that is also why this is called linked list. Also in linked list there is another reference that is Head and Tail . Head point to the first list in our linked list and Tail point to the last of our list in the linked list. Now Linked List usually have 2 type that is : 1. Single Linked List 2. Double/Doubly Linked List Single Linked List A single linked list have only one reference that is a reference to the next list. So we could think that a single linked list is like an array.  As seen a single linked list only contain one reference that point to the next list. Also in our tail the next poin...
Post a Comment
Read more

AVL dan B-Tree

AVL TREE In Computer Science term an AVL tree is a type of self-balancing binary tree. The word AVL come from it's inventor  A delson- V elsky and  L andis. It's the first of such Data Structure. The term self-balancing mean that an AVL tree will maintain both of it's subtree height so that their height diffenrence will be 1, -1, or 0. This is called the balance facotr of an AVL tree. Basically an AVL tree is like an Binary Search Tree but with an self-balancing function built into it.  Why Use an AVL Tree The reasoning to why we must balance the tree if it's not balanced is so that the time complexity for the operation (Search, Insert, Delete) will always be at O(log n) instead of the usual O(h) (where h is the height of the tree ) for the worst case scenario.  Example of a skewed tree For the tree above say that we want to search for the node 74 that we have to traverse the entire tree to find said note but if it's an AVL tree then We on...
Post a Comment
Read more