Skip to main content

Stack vs Heap – Difference between Stack and Heap in Data Structure

In this tutorial you will learn about stack vs heap data structures.

Stack

Stack is a simple data structure used for storing data. In stack, the order in which the data arrives is important. A suitable example for stack is, a pile of plates in kitchen. When we want a plate we will take which was last placed in that pile. This is the main property of stack we say Last in first Out (LIFO) or First in Last out (FILO). So stack is a ordered list in which insertion and deletion are done at one end, called top.

Stack Operations:

Push: When an element inserted into the stack, we call it as push operation.

Top: When we want to know what is the top element of the stack we get it by top operation.

Pop: When we remove an element from the top of the stack, we call it as pop operation.

IsEmptyStack(): To check whether stack is empty or not.

IsFullStack(): To check stack is full or not.

And some other properties are,

Stack underflow: When we want to pop an element from the empty stack, that situation is called stack underflow.

Stack overflow: When we want to push an element to a full stack (i.e stack elements equal to stack size), that situation is called stack overflow.

Stack Data Structure

Also Read: Difference Between Stack and Queue

Heap

Heap is a tree with some special property. That special property of the heap is, the value of a node must be >= or <= to its children. And one most important property of heap is all leaves must be at level h or at h-1. (where h is the height of the tree). This also called heap must be a complete binary tree.

Types of Heaps:

Min Heap: The value of the node must be less than or equal to the values of its children.

Max Heap: The value of the node must be greater than or equal to the values of its children.

Finding minimum element, deleting minimum element, are easy operations in min heap.

Finding maximum element, deleting maximum element, are easy operations in max heap.

Binary Min Heap

Binary Min Heap

Binary Max HeapBinary Max Heap

Stack vs Heap – Difference between Stack and Heap

Stack Heap
1) Stack is a linear data structure. 1) Heap is a hierarchical data structure.
2) Elements in stack follow LIFO or FILO property. 2) Elements in heap follow heap property (mentioned above).
3) Push, Pop, Top are the only allowed operations on the stack. 3) Almost all tree operations can be applied on heaps. Heapifying an element, find minimum, find maximum are some examples.
4) All mentioned operations, push, pop, top, IsEmptyStack(), IsFullStack(), Size(), takes O(1) time in stack. 4) In heap, insertion takes O(log n) time. And finding min, deleting min (in min – heap), finding max, deleting max (in max – heap) takes O(1) time.
5) Stack can be implemented in 3 ways that, simple array based, dynamic array based and Linked list based implementation. 5) Heap can be implemented using arrays, and trees.
6) We can limit stack size, so that stack overflow, stack underflow conditions will occur. 6) There is no case of overflow and underflow in heap.
7) Balancing of symbols, infix – to – postfix conversions, undo sequence in a text editor, implementing function calls (especially recursion) are some applications of stacks. 7) Heaps can be useful for heapsort (best performance), selection algorithms (finding min, finding max, finding median, kth largest/smallest, etc), Graph algorithms.

Comment below if you have queries related to above tutorial for stack vs heap.

The post Stack vs Heap – Difference between Stack and Heap in Data Structure appeared first on The Crazy Programmer.



from The Crazy Programmer https://www.thecrazyprogrammer.com/2018/01/stack-vs-heap.html
Labels:

Comments

Post a Comment

Popular posts from this blog

Rail Fence Cipher Program in C and C++[Encryption & Decryption]

Here you will get rail fence cipher program in C and C++ for encryption and decryption. It is a kind of transposition cipher which is also known as zigzag cipher. Below is an example. Here Key = 3. For encryption we write the message diagonally in zigzag form in a matrix having total rows = key and total columns = message length. Then read the matrix row wise horizontally to get encrypted message. Rail Fence Cipher Program in C #include<stdio.h> #include<string.h> void encryptMsg(char msg[], int key){ int msgLen = strlen(msg), i, j, k = -1, row = 0, col = 0; char railMatrix[key][msgLen]; for(i = 0; i < key; ++i) for(j = 0; j < msgLen; ++j) railMatrix[i][j] = '\n'; for(i = 0; i < msgLen; ++i){ railMatrix[row][col++] = msg[i]; if(row == 0 || row == key-1) k= k * (-1); row = row + k; } printf("\nEncrypted Message: "); for(i = 0; i < key; ++i) f...
3 comments
Read more

Data Encryption Standard (DES) Algorithm

Data Encryption Standard is a symmetric-key algorithm for the encrypting the data. It comes under block cipher algorithm which follows Feistel structure. Here is the block diagram of Data Encryption Standard. Fig1: DES Algorithm Block Diagram [Image Source: Cryptography and Network Security Principles and Practices 4 th Ed by William Stallings] Explanation for above diagram: Each character of plain text converted into binary format. Every time we take 64 bits from that and give as input to DES algorithm, then it processed through 16 rounds and then converted to cipher text. Initial Permutation: 64 bit plain text goes under initial permutation and then given to round 1. Since initial permutation step receiving 64 bits, it contains an 1×64 matrix which contains numbers from 1 to 64 but in shuffled order. After that, we arrange our original 64 bit text in the order mentioned in that matrix. [You can see the matrix in below code] After initial permutation, 64 bit text passed throug...
Post a Comment
Read more

Experimental: Reducing the size of .NET Core applications with Mono's Linker

The .NET team has built a linker to reduce the size of .NET Core applications. It is built on top of the excellent and battle-tested mono linker . The Xamarin tools also use this linker so it makes sense to try it out and perhaps use it everywhere! "In trivial cases, the linker can reduce the size of applications by 50%. The size wins may be more favorable or more moderate for larger applications. The linker removes code in your application and dependent libraries that are not reached by any code paths. It is effectively an application-specific dead code analysis ." - Using the .NET IL Linker I recently updated a 15 year old .NET 1.1 application to cross-platform .NET Core 2.0 so I thought I'd try this experimental linker on it and see the results. The linker is a tool one can use to only ship the minimal possible IL code and metadata that a set of programs might require to run as opposed to the full libraries. It is used by the various Xamarin products to extract...
Post a Comment
Read more