Stack & Queue

Stack vs Queue

Stack and Queue are two important data structures in the programming world and have a variety of usage. They are a secondary data structure which can build using an array or linked list. They have their own functions. Stack can solve recursive problems while Queue can be used for ordered processing.


Stack

  • A stack is a container of objects that are inserted and removed in which elements use the Last-In-First-Out principle (LIFO).
  • The delete operation is known as POP, in relation to the physical idea of popping something from a stack
  • The LIFO structure also means we can only remove the item that was most recently added
  • The PUSH operation can be used to add items to a stack. which refers to the physical idea of pushing an item onto the top of a stack
  • The Stack data structure is a natural recursive data structure and suits well for recursive problems e.g. implementing pre-order, post-order, and in-order traversal of the binary tree, while Queue is a sequential data structure and can be used to provide ordering in processing.


Prefix, Postfix, Infix




  • Infix : Given two operands A and B and an operator  X , the infix notation implies that X will be placed in between A and B i.e . A X B
  • Prefix : An expression is called the prefix expression if the operator appears in the expression before the operands. Simply of the form (operator operand1 operand2). Example : *+AB-CD (Infix : (A+B) * (C-D) )
  • Postfix : An expression is called the postfix expression if the operator appears in the expression after the operands. Simply of the form (operand1 operand2 operator). Example : AB+CD-* (Infix : (A+B * (C-D) )

Queue

Queues are implemented using a First-In-Fist-Out (FIFO) principle, meaning that the items are removed from the list in exactly the same order in which they were added to it. For example, it simulates the physical approach of queuing systems used while waiting in line.  The first in line will be the first to leave, with new people being added to the back of the queue.
When we insert an item onto the queue this is known as the ENQUEUE function, whilst deleting an item is referred to as the DEQUEUE function.





Comments

Post a Comment

Popular posts from this blog

Binary Search Tree

Image
Binary Search Tree Binary search tree is a data structure that quickly allows us to maintain a sorted list of numbers.  It is called a Binary tree because each tree node has a maximum of 2 children It is called a search tree because it can be used to search for the presence of a number in O(log(n)) time. The properties that separates a binary search tree from a regular binary tree is All nodes of left subtree are less than root node All nodes of right subtree are more than root node Both subtrees of each node are also BSTs meaning they have the above two properties On the picture shown above, the right tree is not a binary search tree because on the right subtree of the root, there's a number with smaller value than the root.  Basic Operations Following are the basic operations of a tree − Search   − Searches an element in a tree. Insert  − Inserts an element in a tree. Pre-order Traversal  − Traverses a tree in a pre-order manner. In-order Traversa
Read more

AVL Tree & B - Tree

Image
AVL Tree AVL tree is a self-balancing binary search tree in which each node maintains extra information called a balance factor whose value is either -1, 0 or +1. AVL tree got its name after its inventor Georgy Adelson-Velsky and Landis.  Since AVL trees are height balance trees, operations like insertion and deletion have low time complexity. AVL tree checks the height of the left and the right sub-trees and assures that the difference is not more than 1. This difference is called the Balance Factor . Balance Factor Balance factor of a node in an AVL tree is the differenc e between the height of the l eft subtree  and that of the  right subtree  of that node Balance Factor = (Height of Left Subtree - Height of Right Subtree) or (Height of Right Subtree - Height of Left Subtree) The self balancing property of an avl tree is maintained by the balance factor. The value of balance factor should always be -1, 0 or +1. If the difference in the height of left and
Read more

Hashing Table & Binary Tree

Image
Hashing Table Hash Table is a data structure which stores data in an associative manner.  Data is stored in an array format, where each data value has its own unique index value.  Access of data becomes very fast if we know the index of the desired data. So,   Hash Table is a data structure in which insertion and search operations are very fast where the size of the data doesn't matter.   Hash Function  A hash function job is to store values in an array with a limited size It does it in a way that the array doesn't need to be searched through to find it. This allows us to enter values in any order and we can find them using a calculation instead of searching through the array So how does Hash Table & Hash Function work together? Key values are assigned to elements in a Hash Table using a Hash Function Hash function helps calculate the best index an item should go in Here are a few methods to hash  keys  from string: Mid-square Division Fol
Read more