This series of articles are recorded in the form of notes, and the main content is referred to The Beauty of Data Structures and Algorithms by Professor Wang Zheng.
The stack
The stack is an “operation-constrained” linear table that allows only insertion and deletion of data complexity at one end: the stack can be implemented either through arrays or linked lists. Whether based on array or linked list, the time complexity of loading and unloading is O(1). Application scenarios: browser browsing address record, temporary variable storage of function call, expression evaluation \
The queue
What is a queue: First come first served, this is the typical “queue” structure.
The operation characteristics of queuesA queue is also an “operation-constrained” linear table data structure with one end in and one end out.
The complexity of the: Stacks can be implemented using arrays or linked lists. Whether based on arrays or linked lists, the time complexity of loading and unloading is O(1).
Application scenariosDisruptor and Linux ring caches, for example, use circular concurrent queues. MQ and so on are queue structures
A special queue: circular queue
Normal condition:
Full queue:
When using queues or writing queues, you need to determine whether queues are empty or full. Tail =6, head=7, n=8; (6+7)%8=4; (6+7)%8=4; Draw a few more full lines, and you’ll see that when the line is full, (tail+1)%n=head.
Extended queues: blocking queues, concurrent queues (locks can be used, or lockless concurrency can be achieved using CAS)
The CAS implementation is as follows: Before joining the team, obtain the tail position and check whether tail is changed during joining the team. If not, join the team. Otherwise, join the team fails. Out of the queue is to get the head position, cas.
Other articles in this series: Table of contents for Data Structures and Algorithms