【Java数据结构】手动实现——栈 和 队列
栈（Stack）
概念
实现
队列（Queue）
概念
实现
双端队列
概念
Java中的栈和队列
栈（Stack）
概念
栈： 一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈： 栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈： 栈的删除操作叫做出栈。出数据在栈顶。
实现
- 利用顺序表实现，即使用尾插 + 尾删的方式实现
- 利用链表实现，则头尾皆可
相对来说，顺序表的实现上要更为简单一些，所以优先用顺序表实现栈。
import java.util.Arrays; public class MyStack<T> { private T[]stack;//数组 private int top;//当前可以存放数据元素的下标——>栈顶指针 //用构造函数给定一个初始容量10的数组 public MyStack( ){ this.stack = (T[])new Object[10];//泛型不能实例化对象，但是可以类型转换 } //判断栈是否满了 public boolean isFull(){ return (stack.length == this.top); } //判断栈是否为空 public boolean empty(){ return this.top == 0; } //入栈操作 public void push(T value) { //判断栈是否已经满了 if (isFull()){ this.stack = Arrays.copyOf(stack,2*stack.length);//满了就扩容成原来容量的两倍 } this.stack[this.top] = value;//给top位置添加元素 this.top++;//top指针指向下一可用空间 } //出栈操作，并返回弹出（删除）栈顶元素 public T pop() { //先判断栈是否为空 if (empty()) { throw new IllegalStateException("栈为空！"); } //弹出元素 T ret = this.stack[this.top-1]; this.top--; return ret;//返回删除的元素 } //得到栈顶元素，但是不删除 public T peek() { //判断是否为空 if (empty()){ throw new IllegalStateException("栈为空！"); } //返回栈顶元素，不删除 return this.stack[top-1]; } //展示栈元素 public void show() { for (int i = top-1; i>=0 ; i--){ System.out.print(stack[i]+" "); } System.out.println(); } }
代码测试：
队列（Queue）
概念
队列： 只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(FirstIn First Out)
入队列： 进行插入操作的一端称为队尾（Tail/Rear）
出队列： 进行删除操作的一端称为队头（Head/Front）
实现
队列也可以 数组 和 链表 的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。
public class MyQueue { private Node first; private Node last; //队列是否为空 public boolean isEmpty() { return this.first == null; } //入队 public void offer(int value){ Node node = new Node(value); //尾插法，要判断是否第一次插入 if (this.first == null){ this.first = node; this.last = node; }else{ this.last.setNext(node); this.last = node; } } //出队 public int poll(){ //判断是否为空 if (isEmpty()){ throw new IllegalStateException("队列为空"); } int ret = this.first.getVal(); this.first = this.first.getNext(); return ret;//返回出队元素 } //得到队头元素但是不删除 public int peek() { //不要移动first if(isEmpty()) { throw new UnsupportedOperationException("队列为空！"); } return this.first.getVal(); } //展示队列 public void show() { Node cur = this.first; while(cur != null) { System.out.print(cur.getVal()+" "); cur = cur.getNext(); } System.out.println(); } }
代码测试：
双端队列
后边会专门出一篇双端队列的博客，有兴趣的小伙伴们可以关注一下
概念
双端队列（deque）是指允许两端都可以进行入队和出队操作的队列，deque 是 “double ended queue” 的简称。
那就说明元素可以从队头出队和入队，也可以从队尾出队和入队
Java中的栈和队列
又是这张图！这张图很重要，请务必记住
Stack
Queue
Deque
