栈和队列
文章目录
1、栈(Stack)
1.1概念
栈是一种特殊的线性表，只允许在固定的一段端进行数据的插入和删除。进行数据插入和删除的一端称为栈的栈顶，另一端称为栈底。栈中的数据遵循先进后出的原则。
1.2栈的使用
public static void main(String[] args) { Stack<Integer>stack=new Stack<>(); stack.push(1); stack.push(2); stack.push(3); stack.push(4); stack.push(5); System.out.println("栈中元素个数"+stack.size()); System.out.println("栈顶元素"+stack.peek()); System.out.println(stack.pop());//出栈 if (stack.isEmpty()){ System.out.println("栈为空"); }else { System.out.println(stack.size()); } }
1.3栈的模拟实现
从集合框架中，Stack继承了Vector，Vector和ArrayList类似，都是动态顺序表。
public class MyStack { // 用一个数组去组织数据 private int[] elementData; // 有效元素的个数 private int size; // 定义一个数组默认的大小 private final int DEFAULT_CAPACITY = 5; public MyStack() { this.elementData = new int[DEFAULT_CAPACITY]; } public MyStack(int capacity) { if (capacity < 0) { throw new RuntimeException("数组容量不能小于0."); } else if (capacity > 0) { this.elementData = new int[capacity]; } else { this.elementData = new int[DEFAULT_CAPACITY]; } } public void push(int data) { // 数组是否需要扩容 ensureCapacity(); // 在size位置加入元素 elementData[size++] = data; // size++ } //取出栈顶元素 public int pop(){ int e = peek(); size--; return e; } //获得栈顶元素 public int peek(){ if(empty()){ throw new RuntimeException("栈为空，无法获取栈顶元素"); } return elementData[size-1]; } public int size(){ return size; } //扩容 private void ensureCapacity() { if (size == elementData.length) { this.elementData = Arrays.copyOf(elementData, elementData.length * 2); } } public boolean empty(){ return 0 == size; } }
1.4相关OJ
1.5注意
栈、虚拟机栈、栈帧有什么区别呢？
简单的理解：
栈是一种数据结构。
虚拟机栈：具有特殊作用的一块内存空间。jvm为了对数据进行更好的管理，将内存按照不同的需求划分出来的一种结构
栈帧：一种结构，这种结构与函数调用相关的，内部：局部变量表、操作数栈…
每个方法在运行时，jvm都会创建一个栈帧，然后将栈帧压入到虚拟机栈中
当方法调用结束时，该方法对应的栈帧会从虚拟机栈中出栈
2、队列(Queue)
2.1概念
与栈的概念相似。而队列是在一端进行插入数据，另一端进行删除数据操作的特殊线性表，队列遵循先进先出原则。
2.2队列的使用
在Java中，Queue是个接口，底层是通过链表实现的
public static void main(String[] args) { //Queue是个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口 Queue<Integer>queue=new LinkedList<>(); queue.offer(1); queue.offer(2); queue.offer(3); queue.offer(4); queue.offer(5); System.out.println(queue.size()); System.out.println("队头元素"+queue.peek()); System.out.println("出队"+queue.poll()); if (queue.isEmpty()){ System.out.println("队空"); }else { System.out.println(queue.size()); } }
2.3队列的实现(链表实现)
public class MyQueue { //1、定义一个静态双向链表节点的类 public static class ListNode{ int val; ListNode prev; ListNode next; public ListNode(int val) { this.val = val; } } //头节点 public ListNode head; //尾节点 public ListNode tail; //对列 public int size; /** * 入队 从对尾入 * @param e */ public void offer(int e){ ListNode node=new ListNode(e); if (head==null){ //空链表 head=node; }else{ tail.next=node; node.prev=tail; } tail=node; size++; } /** * 出栈 ，从队头出 */ public int poll(){ if (isEmpty()){ throw new RuntimeException("队列为空."); } //获取对头元素 int headVal= head.val; head=head.next; if (head==null){ tail=null; }else { //处理前驱节点 head.prev.next=null; head.prev=null; } size--; return headVal; } /** * 获取队头元素 * @return */ public int peek(){ if (isEmpty()){ throw new RuntimeException("队列为空."); } return head.val; } public boolean isEmpty(){ return size==0; } }
2.4循环队列
在使用中我们还会用到一种队列叫循环队列。
循环队列通常使用数组实现。
相关OJ
2.5 OJ
参考代码
