This is the 7th day of my participation in the August More Text Challenge

1. The stack

1.1 Heap and stack relationship

  • A heap is usually an array object that can be thought of as a tree. A heap always satisfies the following properties
    • The value of a node in the heap is always no greater than or less than its parent
    • The heap is always a complete binary tree
    • The data structure is binary tree
  • The heap claims a certain size of memory while the program is running, rather than when the program is compiled, that is, dynamically allocates memory
  • Application access to the heap is no different from access to regular memory.
  • The heap refers to the dynamic memory requested by the program while it is running, whereas the stack simply refers to a way of using the heap.

1.2 Stack Stack

  • A stack, also known as a stack, is a linear table.
  • Stack-first In Last Out (FILO
  • Implementation: Array Array or LinkedList
  • Common operation methods:
    • Push () into the stack
    • Pop () out of the stack
    • Peek () queries the top of the stack element

2. The queue

2.1 the Queue Queue

  • A special linear table structure
  • Queue-first In First Out (FIFO)
  • Add elements at the end of the team and remove elements at the head of the team
  • Implementation: Array Array or LinkedList
  • Common operation methods:
    • Push () into the queue
    • Pop () out of the queue

2.2 Priority Queue

  • PriorityQueue – indicates the PriorityQueue
  • Priority queues have all the characteristics of queues, including basic operations, with an internal sort added on top.
  • Features: Normal entry, according to the priority out
  • Priority queue implementation mechanism:
    • Heap (Binary, Binomial, Fibonacci)
    • Binary Search Tree

2.3 Heap Sort and priority queue

  • Heap sort is an algorithm implemented using a heap
  • Priority queues are implemented using a heap
  • Heap sort is just sort, priority queue can be taken at any time in the queue maximum, insert, manual implementation can also be a certain extent to achieve deletion

3. Complexity of common algorithms

Photo source:www.bigocheatsheet.com/

Refer to the address

  • Geek time – Algorithms 40 lecture – stacks and queues
  • bigocheatsheet.com
  • What are “heap “,” stack “,” stack “,” queue “, and the difference between them?
  • What are the similarities and differences between priority queue and heap sort?
  • Java stack _stacks and heaps in Java