Preliminary understanding of stack and queue

One 、 The definition and characteristics of stack

1、 Definition ： Stack (stack) It's a special linear table , It's limited at one end ( It's usually the tail of the table ) A linear table that performs insert and delete operations . Also known as Last in, first out The linear table , abbreviation LIFO structure .

2、 Stack related concepts ：

① The stack is inserted only at the end of the table 、 Linear table of delete operations

② The end of the table is called the top of the stack Top, The header is called the bottom of the stack Base.

③ Insert the element to the top of the stack ( End of table ) The operation of , be called Push .

④ From the top of the stack ( End of table ) Operation to delete the last element , be called Out of the stack .

3、 Common applications of stack ： Because stack operations have Last in, first out Inherent characteristics of , Make the stack a useful tool in programming . in addition , If the problem solving process has " Last in, first out ” If the natural characteristics of , Then the solution algorithm must also use " Stack ”. For example, the following questions may involve ： Number conversion 、 Expression evaluation 、 The test of bracket matching 、 Eight queens question 、 Line editor 、 Function call 、 Maze solution 、 Implementation of recursive call .

4、 The basic operation of stack is shown in the figure below ：

Two 、 The definition and characteristics of queues

1、 Definition ： A queue is a special linear table , The insertion operation can only be performed at one end of the table , A linear table that performs a deletion operation at the other end of the table ( Cut the head and insert the tail ). Can only be calculated at the head and tail of the team , And access the node according to fifo (FIFO) Principles .

2、 Application of queues ： Because the operation of the queue has fifo Characteristics of , Make queue become a useful tool to solve similar queuing problems in programming . The following is an example of queue application ：

① Offline printout : Output in the order of application .

② In a multiuser system , Multiple users line up , Recycle in time CPU And main memory .

③ Queue up according to the priority of users , One queue per priority .

④ In real-time control system , The signal is processed in the order of reception .

⑤ Network message transmission , According to the order of arrival .

3、 Terms related to queues ：① The tail of the watch is called the tail of the team , The header is called the head of the team .

                                  ② Inserting elements is called joining the team , Deleting an element is called dequeue .

                                  ③ The storage structure of queue is chain queue or sequential queue ( Commonly used cyclic order ).

4、 The common basic operations of queues are shown in the following figure ：

  3、 ... and 、 The linear table 、 Stack and queue comparison

1、 Stacks and queues are two commonly used 、 Important data structures , Stack and queue are restricted to insert and delete only in the table " Endpoint " On going The linear table . Therefore, it can be understood that both stack and queue are a special case of linear table .

2、 The following figure shows the comparison of the three ：