大气集团网站源码,深圳网站建设力荐上榜网络,外贸推广具体是做什么,嘉兴市建设局网站1. 简介
栈#xff08;Stack#xff09;是计算机科学中的一种抽象数据类型#xff0c;它遵循特定的操作顺序#xff0c;即后进先出#xff08;Last In First Out#xff0c;LIFO#xff09;。这意味着最后添加到栈中的元素将是第一个被移除的。栈的基本操作通常包括Stack是计算机科学中的一种抽象数据类型它遵循特定的操作顺序即后进先出Last In First OutLIFO。这意味着最后添加到栈中的元素将是第一个被移除的。栈的基本操作通常包括 压栈Push将一个元素添加到栈的顶部。 弹栈Pop移除栈顶部的元素并返回该元素的值。 查看栈顶Peek返回栈顶部的元素但不将其从栈中移除。 检查栈空IsEmpty检查栈是否为空通常用于在执行操作前确保栈中至少有一个元素。 获取栈大小Size返回栈中元素的数量。
栈可以用数组或链表来实现。数组实现的栈具有固定的大小而链表实现的栈可以动态调整大小。 2. 实例
2.1 基于数组实现
public class StackUsingArray {private int[] stack;private int top;private int capacity;public StackUsingArray(int capacity) {this.capacity capacity;stack new int[capacity];top -1;}// Push element onto the stackpublic void push(int item) {if (top capacity - 1) {System.out.println(Stack is full!);} else {stack[top] item;}}// Pop element from the stackpublic int pop() {if (top -1) {System.out.println(Stack is empty!);return -1;} else {return stack[top--];}}// Peek the top element of the stackpublic int peek() {if (top -1) {System.out.println(Stack is empty!);return -1;} else {return stack[top];}}// Check if stack is emptypublic boolean isEmpty() {return top -1;}// Get the size of the stackpublic int size() {return top 1;}public static void main(String[] args) {StackUsingArray stack new StackUsingArray(5);stack.push(10);stack.push(20);stack.push(30);System.out.println(Top element: stack.peek()); // Output: 30System.out.println(Popped element: stack.pop()); // Output: 30System.out.println(Stack size: stack.size()); // Output: 2}
}可以增加扩容机制---》ArrayDeque源码中扩容规则如果数小则翻倍否则增加50%。
private void grow(int needed) {// overflow-conscious codefinal int oldCapacity elements.length;int newCapacity;// Double capacity if small; else grow by 50%int jump (oldCapacity 64) ? (oldCapacity 2) : (oldCapacity 1);if (jump needed|| (newCapacity (oldCapacity jump)) - MAX_ARRAY_SIZE 0)newCapacity newCapacity(needed, jump);final Object[] es elements Arrays.copyOf(elements, newCapacity);// Exceptionally, here tail head needs to be disambiguatedif (tail head || (tail head es[head] ! null)) {// wrap around; slide first leg forward to end of arrayint newSpace newCapacity - oldCapacity;System.arraycopy(es, head,es, head newSpace,oldCapacity - head);for (int i head, to (head newSpace); i to; i)es[i] null;}
} 2.2 基于链表实现
public class StackUsingLinkedList {private Node top;private class Node {int data;Node next;Node(int data) {this.data data;this.next null;}}// Push element onto the stackpublic void push(int item) {Node newNode new Node(item);newNode.next top;top newNode;}// Pop element from the stackpublic int pop() {if (top null) {System.out.println(Stack is empty!);return -1;} else {int poppedData top.data;top top.next;return poppedData;}}// Peek the top element of the stackpublic int peek() {if (top null) {System.out.println(Stack is empty!);return -1;} else {return top.data;}}// Check if stack is emptypublic boolean isEmpty() {return top null;}// Get the size of the stackpublic int size() {int size 0;Node current top;while (current ! null) {size;current current.next;}return size;}public static void main(String[] args) {StackUsingLinkedList stack new StackUsingLinkedList();stack.push(10);stack.push(20);stack.push(30);System.out.println(Top element: stack.peek()); // Output: 30System.out.println(Popped element: stack.pop()); // Output: 30System.out.println(Stack size: stack.size()); // Output: 2}
} 2.3 基于Deque实现类实现
Java中的Deque接口提供了一个双端队列实现可以非常方便地用来实现栈。
import java.util.Deque;
import java.util.LinkedList;public class StackUsingDeque {private DequeInteger stack;public StackUsingDeque() {stack new LinkedList();}// Push element onto the stackpublic void push(int item) {stack.push(item);}// Pop element from the stackpublic int pop() {if (stack.isEmpty()) {System.out.println(Stack is empty!);return -1;} else {return stack.pop();}}// Peek the top element of the stackpublic int peek() {if (stack.isEmpty()) {System.out.println(Stack is empty!);return -1;} else {return stack.peek();}}// Check if stack is emptypublic boolean isEmpty() {return stack.isEmpty();}// Get the size of the stackpublic int size() {return stack.size();}public static void main(String[] args) {StackUsingDeque stack new StackUsingDeque();stack.push(10);stack.push(20);stack.push(30);System.out.println(Top element: stack.peek()); // Output: 30System.out.println(Popped element: stack.pop()); // Output: 30System.out.println(Stack size: stack.size()); // Output: 2}
}2.4 总结 数组实现适用于栈大小已知且不频繁改变大小的情况。push和pop操作的时间复杂度为O(1)但如果栈满时扩展数组会带来一定的性能开销。 链表实现适用于栈大小不固定的情况。链表实现的栈无需考虑容量问题但每次操作时需要额外的内存空间来存储节点指针。 Deque实现这是最推荐的实现方式因为它提供了高效的push和pop操作并且实现简洁。
Deque接口可以通过LinkedList或ArrayDeque来实现。如果追求性能ArrayDeque通常是更好的选择因为它的底层是基于数组的避免了链表的节点分配开销。 相关笔试题基于栈stack的部分笔试题 不积跬步无以至千里 --- xiaokai
