Stack and Queue

 Stack

    A stack is a linear data structure that 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). Stack has two fundamental operations which are push and pop.
     A real-life example of a stack is when you stack a plate on top of each other. The plate which is at the top is the first one to be removed and the plate which has been placed at the bottommost position remains in the stack for the longest time. So, it can be seen to follow LIFO(Last In First Out) or FILO(First In Last Out) order.

Stacks are widely used to:

  • Reverse the order of data
  • Convert infix expression into postfix
  • Convert postfix expression into infix
  • Backtracking problem
  • System stack is used in every recursive function
  • Converting a decimal number into its binary equivalent

Stack operations

  • push(x): add item x to the top of the stack
  • pop(): remove an item from the top of the stack
  • top() [peek]: reveal or return the top item from the stack

Infix, Postfix, and Prefix Notation

  • prefix: operator is written before operands
  • infix: operator is written between operands
  • postfix: operator is written after operands
  • Postfix should be scanned from left to right while prefix scanned oppositely

Conversion

Algorithm:
  1. Search for the operator which has the highest precedence
  2. Put that operator behind the operands
  3. Repeat until finish

Depth First Search (DFS)

     DFS is an algorithm for traversing or searching in a tree or graph. We start at the root of the tree and explore as far as possible along each branch before backtracking.
DFS applications:
  • Finding articulation point and bridge in a graph
  • Finding connected component
  • Topological sorting
  • etc.

Queue

     A Queue is a linear structure that follows a particular order in which the operations are performed. The order is First In First Out (FIFO). A queue has two fundamental operations which are push and pop (similar to stack). A good example of a queue is any queue of consumers for a resource where the consumer that came first is served first. The difference between stacks and queues is in removing. In a stack we remove the item the most recently added; in a queue, we remove the item the least recently added.

Queue operations

  • push(x): add item x to the back of the queue
  • pop(): remove an item from the front of the queue
  • front() [peek]: reveal or return the frontest item from the queue

Circular Queue

Deques

     A deque is a list in which elements can be inserted or deleted at either end. It is also known as a head-tail linked list because elements can be added to or removed from the front (head) or back (tail).

Priority Queue

     A priority queue is an abstract data type in which each element is assigned a priority. The general rule of processing elements of a priority queue can be given as:
  • An element with higher priority is processed before an element with lower priority
  • Two elements with the same priority are processed on a first come first served basis

Breadth-First Search (BFS)

             BFS like DFS is also an algorithm for traversing or searching in a tree or graph. We start at the root of the tree (or some arbitrary node in graph) and explore all neighboring nodes level per level until we find the goal. BFS has many applications, such as: 

             - Finding connected component in a graph
             - Finding the shortest path in an unweighted graph
             - Ford-Fulkerson method for computing maximum flow
             - etc.


Comments

Post a Comment

Popular posts from this blog

Hasing and Hash Table

Image
Hashing      Hashing is an important Data Structure that is designed to use a special function called the Hash function which is used to map a given value with a particular key for faster access of elements. The efficiency of mapping depends on the efficiency of the hash function used.      In hashing, a string of characters is transformed into a shorter length value or key that represents the original string. Hash Table      Hash table is a table (array) where we store the original string. The index of the table is the hashed key while the value is the original string.  Hash Function      A hash function is any function that can be used to map data of arbitrary size to fixed-size values. The values returned by a hash function are called hash values, hash codes, digests, or simply hashes. The values are used to index a fixed-size table called a hash table.      A good hash function shoul...
Read more

Summary

Image
Linked List      A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers as shown in the below image: A linked list consists of nodes where each node contains a data field and a reference to the next node in the list. Types of linked list 1.  Single Linked List 2.  Double/Doubly Linked List 3.  Circular Single Linked List 4.  Circular Doubly Linked List Stack and Queue Stack      A stack  is a linear data structure that 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). Stack has two fundamental operations which are push and pop.      A real-life example of a stack is when you stack a plate on top of each other.  The plate which is at the top is the first one to be removed and  the ...
Read more