Stacks and Queues in Java
I. Stack (Stack)
1.1 Introduction
The stack is a Last In First Out (LIFO) data structure. In a stack, insertion and deletion operations of elements are performed on the top of the stack.The Java
class implements the basic functions of a stack, including
push()
Into the stack,pop()
Out of the stack,peek()
Methods such as viewing the top element of the stack.Stacks are widely used in Java, for example, method call stacks, expression evaluation, undo operations, etc. can be realized using stacks. Stacks are characterized by simplicity and efficiency and are suitable for scenarios that require last-in-first-out.
1.2 Storage space
The storage space of a stack is contiguous, and a contiguous segment of address space is usually allocated in memory to store the elements of the stack. Stacks are characterized by high space utilization but limited capacity.
When using a stack, the size of the stack needs to be determined at the program writing stage, i.e. a fixed capacity needs to be specified when defining the stack. This means that the size of the stack is static and once the capacity of the stack is exceeded, a stack overflow () error results.
Second, the queue (Queue)
2.1 Introduction
A queue is a first-in-first-out (FIFO, First In First Out) data structure. In a queue, the insertion of an element (into the queue) takes place at the end of the queue, while the deletion of an element (out of the queue) takes place at the head of the queue.The Java
interface defines the basic operations of a queue, such as the
offer()
Make the team,poll()
Out of the team,peek()
View team header elements, etc.
2.2 Storage space
The storage space of a queue can be continuous or discontinuous, usually using a linked table or array to realize the queue. Queues are characterized by dynamic space expansion, but may cause space waste during frequent insertion and deletion operations.
Unlike the stack, the queue does not need to determine a fixed size of space in advance, you can dynamically adjust the size of the space as needed. This makes the queue more flexible, according to the actual demand to dynamically allocate memory space, avoiding the static space size limitations.
III. Distinctions
-
- Data structure characteristics: A stack is a LIFO data structure, while a queue is a FIFO data structure.
-
- operating position: The insertion and deletion operations of a stack are performed at the top of the stack, while the insertion operation of a queue is at the end of the queue and the deletion operation is at the head of the queue.
-
- storage space: The storage space of a stack is contiguous, whereas the storage space of a queue can be either contiguous or non-contiguous.
-
- Application for space when in use: Stacks require static allocation of a fixed-size space when in use, whereas queues can dynamically adjust the space size, avoiding the static space size constraints.