How to implement java stack and queue

Stack and Queue

1. Stack is a last in first off (LIFO) data structure

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

Stack

Stack is a linear structure , compared with arrays, the operations corresponding to stacks are a subset of arrays.

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

Stack is a data structure that is widely used. In the use of computers, stacks are widely used, such as lexical analyzers in compilers, Java virtual machines, undo operations (Undo) in software, and browsing. The rollback operation in the compiler, the function call implementation in the compiler, etc.

Stack implementation

Interface	Description	Complexity
void push(E e)	Add elements to the stack	O(1) Split evenly
E pop()	Pop the top element of the stack	O(1) evenly spread
E peek( )	View the top element of the stack	O(1)
int getSize()	Get the number of elements in the stack	O(1)
boolean isEmpty()	Determine whether the stack is empty	O(1)

Note: The push and pop operations are performed at the end, which may trigger resize, but it is considered O(1) evenly.
If you want to know more about the analysis of time complexity, please pay attention to the article that the author will update later: What problem does O(n) explain?

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

In the design of the stack, the user only pays attention to the access of the top element of the stack and the stack length, so the design code is as follows:

Readers can use Stack This data structure is used to solve problem No. 20 on LeetCode: Valid Parentheses. You can also check out Daily Calculation: Valid Parentheses.

Queue

Queue is also a linear data structure. Compared with arrays, the operations corresponding to queues are a subset of arrays.

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

The application of queue can be reflected in the playlist on the player, data stream object, asynchronous data transmission structure (file IO, pipe communication, socket, etc.). Of course, the most intuitive one is queuing. .

Queue implementation

##E getFront()Get the first element of the teamO(1)int getSize()Get the number of queue elementsO(1)boolean isEmpty()Judge whether the queue is emptyO(1)

Interface	Description	Complexity
void enqueue(E e)	Enqueue	O(1) evenly distributed
E dequeue()	Dequeue	O(n)

Enter the queue Starting from the end of the queue, resize may be triggered, so evenly distributed it is O(1). Dequeuing is at the head of the queue, and array implementation requires moving all elements every time, O(n).

The above is the detailed content of How to implement java stack and queue. For more information, please follow other related articles on the PHP Chinese website!