Bo2SS

Course Content#

Queue#

• FIFO (First In First Out), LILO. Similar to queuing, distinguishing first come first served
• Also a sequential structure, requires continuous storage space (but can also be implemented with a linked list)

Structure Definition#

• Requires continuous storage space
• Capacity
• Front of the queue, rear of the queue
• +Number of elements: used to determine if the queue is full, convenient for circular queue to solve the false overflow problem
• Data type

Structure Operations#

• Dequeue
  • head - 1
  • count - 1
• Enqueue
  • tail + 1
  • count + 1
• ❗False Overflow
  • Cannot store elements anymore
  • In fact, it may not be full: dequeue operation leaves space at the front of the queue
  • Solution: Circular Queue
    • tail goes to the front of the queue after reaching the end
    • Use modulo operation to determine position: (tail + 1) % length
• Capacity Expansion: When encountering true overflow, see code demonstration

Stack#

• FILO (First In Last Out), LIFO. Analogous to a box of books, one end is blocked
• Also a sequential structure

Structure Definition#

• Requires continuous storage space (with size limitations)
• Capacity
• Top pointer [top]: for an empty stack, top = -1, 0 may not be suitable
• Data type

Structure Operations#

• Pop: top - 1 // Needs to check for empty
• Push: top + 1, store value // Needs to check for full

Applications#

• 

• For DFS and BFS, see "Interview and Written Test Algorithms I" - 6 Search Topics

• Monotonic stack, monotonic queue for self-study

In-Class Exercises#

LC-20: Valid Parentheses#

• The key is in the thinking: turn big problems into small problems
  • How to simplify the problem to only one type of bracket? Can it be done without using a stack?
  • Idea: Only need to record the number of left brackets and right brackets
    • At any position, left count >= right count
    • At the last position, left count == right count
    • 
    • In fact, you can just use one number top to record, +1 for left bracket, -1 for right bracket
      • At any position, top >= 0
      • At the last position, top == 0
  • Can this +1, -1 operation be related to stack push and pop?
  • One matching of brackets is equivalent to one push and pop
  • Brackets within brackets represent a complete containment relationship
  • There is also a divide and conquer idea
• Stack: Can handle problems with complete containment relationships
• Code
  • Refer to "Interview and Written Test Algorithms I" - 5 STL "Containers" Usage and Practice - HZOJ-378 Explanation
  • In C language, first implement the data structure - stack, then use the stack to solve the problem

Code Demonstration#

Queue#

Partial Results

• 

• There are two ways to define tail

  • ① Point to the address of the last element
  • ② Point to the address after the last element (the choice of this code)

• Using a circular queue, the phenomenon of false overflow no longer exists

• But what about true overflow? 👇

+Capacity Expansion#

For the capacity expansion of the circular queue

• Which of the 3 methods for dynamically allocating memory [malloc, calloc, realloc] should be used?

• 🆒 Both malloc and calloc can be used, but

• ❗ The previously used realloc is not effective

  • The tail of the circular queue may not be right after the head, but rather the tail and head overlap
  • Example: When the queue is full, head and tail (here tail is defined as the position after the last element) are in the following positions, what will happen to push and pop after doubling the capacity?
  • 
  • At this time, many empty values are inserted between head and tail, because realloc moves values in the original order, while the expanded part has no values yet
  • Therefore, whether dequeuing from head to tail [with many empty values in between] or enqueuing from tail [with un-dequeued elements at the tail position], there are problems!

• Using malloc to allocate space, then migrate the original queue from head to tail in order, manually adjusting head to index 0, as shown, the key is in the adjustment of head and tail pointers!

  • 

• Code

  • 
  • The key is to adjust the pointers to the normal order

Stack#

• 
• 
• 

• In line 72, the pop operation only needs top - 1

• In line 109, if there are commands to be executed in printf instead of simply retrieving values, attention should be paid to the order

  • Its calling order is related to the design of the system stack
  • Refer to printf function parameters are pushed onto the stack from right to left-CSDN; printf stack push and pop-CSDN
    • This right to left method does not change with different compilers or machines
    • Involves the underlying, not to delve into
  • 【Conclusion】 When printf's parameters have commands to be executed, try to write them separately

• In line 106, it is necessary to check for empty before popping, otherwise top = -1 will cause problems

  • The first pop result is safe
  • 

• ❓ It should be determined whether the stack exists before calling empty and top, rather than writing NULL checks in the function

  • Other operations basically have NULL checks, mainly related to the convenience of program splitting, no need to delve into
  • It is also possible to write NULL checks for all operations

Additional Knowledge Points#

• System Stack
  • Also a stack, size: 8MB
  • When using recursion, the system stack is used

Tips#

Course Notes#