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 (can also be implemented using linked lists)

Structure Definition#

• Requires continuous storage space
• Capacity
• Front and rear of the queue
• +Number of elements: used to determine if the queue is full, facilitates solving the problem of false overflow in circular queues
• Data type

Structure Operations#

• Dequeue
  • head - 1
  • count - 1
• Enqueue
  • tail + 1
  • count + 1
• ❗ False overflow
  • Unable to store elements
  • Actually may not be full: dequeue operation creates empty space at the front of the queue
  • Solution: Circular Queue
    • When the tail reaches the end, it returns to the front of the queue
    • Use modulo operation to determine the position: (tail + 1) % length
• Expansion: When encountering true overflow, see code demonstration for details

Stack#

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

Structure Definition#

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

Structure Operations#

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

Applications#

• 

• DFS and BFS see "Interview and Written Test Algorithms" - Topic 6: Search

• Learn about monotonic stacks and queues on your own

In-class Exercises#

LC-20: Valid Parentheses#

• The key is in the thinking: from a big problem to a small problem
  • How to solve the problem when it is simplified to only one type of parentheses? Can it be done without using a stack?
  • Idea: Only need to record the number of left parentheses and right parentheses
    • At any position, the number of left parentheses >= the number of right parentheses
    • At the last position, the number of left parentheses == the number of right parentheses
    • 
    • In fact, only one variable top is needed to record. Increase by 1 when encountering a left parenthesis, decrease by 1 when encountering a right parenthesis
      • At any position, top >= 0
      • At the last position, top == 0
  • Can you associate this +1 and -1 operation with stack push and pop?
  • Matching parentheses is equivalent to one push and one pop operation
  • Parentheses inside parentheses are completely contained
  • Also involves the concept of divide and conquer
• Stack: Can handle problems with complete containment
• Code
  • Refer to "Interview and Written Test Algorithms" - Topic 5: Use and Practice of STL "Containers" - Explanation of HZOJ-378
  • In C language, first implement the data structure - stack, and then use the stack to solve the problem

Code Demonstration#

Queue#

Partial results

• 

• There are two ways to define the tail

  • ① Points to the address of the last element
  • ② Points to the next address after the last element (chosen in this code)

• When using a circular queue, there is no longer a false overflow phenomenon

• But what about true overflow? 👇

+Expansion#

Expansion for circular queues

• 3 methods for dynamically allocating memory [malloc, calloc, realloc], which one to use?

• 🆒 Both malloc and calloc can be used, but

• ❗ realloc used before is not working well anymore

  • The tail of the circular queue may not be after the head, but the tail and head overlap
  • Example: When the queue is full, the head and tail (here the tail is defined as the position after the last element) are in the following positions. What will happen to the push and pop operations of the expanded queue?
  • 
  • At this time, many empty values are inserted between the head and tail because realloc moves the values in the original order, and the expanded part does not have values yet
  • So, whether it is dequeuing from head to tail [with many empty values in between], or enqueuing from tail [there are elements that have not been dequeued at the tail position], there are problems!

• After using malloc to allocate space, the original queue is migrated from head to tail in order, that is, manually adjust the head to index 0, as shown below, the key is to adjust the pointers of the head and tail!

  • 

• Code

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

Stack#

• 
• 
• 

• Line 72, the pop operation only needs top - 1

• Line 109, when there are commands to be executed in printf instead of simple value retrieval, pay attention to the order

  • The order of execution 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 vary with different compilers or machines
    • Involves low-level details, not delving into it for now
  • 【Conclusion】 When there are commands to be executed in printf parameters, it is better to write them separately

• Line 106, need to check if 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

  • However, most other operations have NULL checks, mainly for the convenience of program separation, no need to delve into it
  • It is also possible to write NULL checks for all operations

Additional Knowledge#

• System stack
  • It is also a stack with a size of 8MB
  • When using recursion, the system stack is used

Tips#

Course Notes#