Shulou(Shulou.com)05/31 Report--

This article mainly introduces the java stack and queue how to achieve the relevant knowledge, the content is detailed and easy to understand, the operation is simple and fast, with a certain reference value, I believe you will gain after reading this java stack and queue how to achieve the article, let's take a look at it.

Stack and queue

Stack is a last-in, first-out (last in first off,LIFO) data structure

Queue (Queue) is a first-in, first-out (fisrt in first out,FIFO) structure.

Stack (Stack)

The stack is a linear structure. Compared with the array, the operation corresponding to the stack is a subset of the array.

It can only add elements from one end, and can only pull elements from one end (this end is called the top of the stack).

Stack data structure has a wide range of uses, such as lexical analyzer in compiler, Java virtual machine, undo operation (Undo) in software, fallback operation in browser, function call implementation in compiler and so on.

Void push (E e) add elements O (1) to the stack E pop () pop up top element O (1) share E peek () look at the top element O (1) int getSize () get the number of elements in the stack O (1) boolean isEmpty () determine whether the stack is empty or not

Note: push and pop operations are carried out at the end, which may trigger resize, but the sharing can be regarded as O (1).

If you want to know more about the analysis of time complexity, you are welcome to follow the author's follow-up article: what does O (n) explain?

The stack can be implemented through an array or a linked list, where we use an array to implement the above interface.

In the design of the stack, the user only cares about the access of the elements at the top of the stack and the length of the stack, so the design code is as follows:

Readers can use the stack data structure to solve the No. 20 problem on LeetCode: valid parentheses, or you can check the daily calculation: Valid Parentheses.

Queue Queue

A queue is also a linear data structure. Compared with an array, the operation corresponding to a queue is a subset of the array.

Elements can only be added from one end (end of the line) and can only be taken out from the other end (head of the line).

The application of queues can be reflected in playlists, data flow objects, asynchronous data transfer structures (file IO, pipe communication, sockets, etc.) on the player. Of course, the most intuitive thing is queuing.

The implementation interface description of the queue complexity void enqueue (E e) join the queue O (1) share E dequeue () out of the queue O (n) E getFront () get the first element O (1) int getSize () get the number of queue elements O (1) boolean isEmpty () determine whether the queue is empty O (1)

Joining the team starts at the end of the team, and resize may be triggered, so it is shared equally as O (1). Getting out of the queue is at the head of the queue, and the array implementation moves all the elements each time, O (n).

This is the end of the article on "how to implement the java Stack and queue". Thank you for reading! I believe you all have a certain understanding of the knowledge of "how to implement java stack and queue". If you want to learn more, you are welcome to follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.