- 栈和队列
- 栈:
- 栈完整代码
- 队列
- 队列完整代码
栈和队列也是线性表
线性表:一次保存单个同类型元素,多个元素之间逻辑上连续
数组,链表,栈,队列,字符串(内部是字符数组 char[]),这些都是线性表。
栈和队列其实是操作受限的线性表
之前的数组和链表,可以在任意位置插入和删除
“栈和队列”,只能在一端插入和删除元素
栈:(Last In First Out)简称(LIFO),就是"后进先出"的原则
栈只能在一段插入元素,且只能在这一段取出元素,这一端称之为栈顶
栈在生活中的应用有很多
如:无处不在的undo操作,即你按ctrl+z就返回了上次一输入的内容,这其就是栈的应用
普通栈基本就是包含下面三种方法
public class MyStack{ //记录当前栈中的元素个数 private int size; //实际存储数据的动态数组,在栈中,只能在数组末尾添加和删除元素 private List date = new ArrayList<>(); public void push(E val){ date.add(val); size++; } }
首先是push(E val),将元素添加到栈中的操作(压栈、入栈),
非常简单,只需要使用动态数组的add方法默认在数组末尾插入元素即可
其次是pop(),弹出栈顶元素的操作
public E pop(){
if(date.isEmpty()){
throw new NoSuchElementException("stack is empty cant pop");
}
E val = date.remove(size-1);
size--;
return val;
}
边界条件是栈是否为空,栈为空就抛出一个异常,返回被删除元素的值
最后就是peek()操作,取出当前栈顶元素但并不删除
public E peek(){
if(date.isEmpty()){
throw new NoSuchElementException("stack is empty cant peek");
}
return date.get(size-1);
}
利用动态数组的get的方法就能取出当前栈的栈顶元素
栈完整代码public class MyStack队列{ //记录当前栈中的元素个数 private int size; //实际存储数据的动态数组,在栈中,只能在数组末尾添加和删除元素 private List date = new ArrayList<>(); public void push(E val){ date.add(val); size++; } public E pop(){ if(date.isEmpty()){ throw new NoSuchElementException("stack is empty cant pop"); } E val = date.remove(size-1); size--; return val; } public E peek(){ if(date.isEmpty()){ throw new NoSuchElementException("stack is empty cant peek"); } return date.get(size-1); } @Override public String toString() { StringBuilder sb = new StringBuilder(); sb.append("["); for (int i = 0; i < size; i++) { sb.append(date.get(i)); if(i != size-1){ sb.append(", "); } } sb.append("] top"); return sb.toString(); } }
相对于栈来说队列实现的子类是比较多的,比如FIFO队列,双端队列Deque,循环队列LoopQueue,优先级队列PriorityQueue等,所以采用接口来定义队列,具体实现由子类决定
队列:(FIFO、First In First Out)
先进先出的数据结构,元素从”队尾“添加到对队列中,元素从”队首“出队列
队列在现实生活中也是非常常见,当你在排队的时候,就是一个队列,先排的人先离开,排在最前面的叫队首,排在最后面的叫队尾
一样是只有三个方法
首先是要有Queue这个接口
public interface Queue{ //入队 void offer(E e); //出队 E poll(); //查看队首元素 E peek(); boolean isEmpty(); }
普通的基于链表实现的队列,首先是定义一个链表,一样是保存一个值,然后保存下一个元素的地址
class ListNode{ E val; ListNode next; public ListNode(E val) { this.val = val; } }
首先是offer(E val)方法,将元素从队尾插入
public class LinkedQueueimplements Queue { private int size; private ListNode head; private ListNode tail; @Override public void offer(E e) { ListNode listNode = new ListNode<>(e); if(head == null){ head = tail = listNode; }else{ tail.next = listNode; tail = listNode; } size++; } }
当head为空时,就是头和尾都等于新插入的节点,否则,就是尾插让tail.next先指向新插入的元素,再更新tail为新的队尾即可。
其次时poll()方法,将队首元素弹出
边界条件是当队列为空的情况,抛出一个异常即可,当队列不为空,就只需要更新队首即可,然后将先的队首删除
public E poll() {
if(isEmpty()){
throw new NoSuchElementException("queue is empty cant poll");
}
E e = head.val;
ListNode listNode = head;
head = head.next;
listNode.next = listNode = null;
size--;
return e;
}
最后就是peek()方法,取出当前队首元素但不删除
public E peek() {
if(isEmpty()){
throw new NoSuchElementException("queue is empty cant peek!");
}
return head.val;
}
队列完整代码
class ListNode{ E val; ListNode next; public ListNode(E val) { this.val = val; } } public class LinkedQueue implements Queue { private int size; private ListNode head; private ListNode tail; @Override public void offer(E e) { ListNode listNode = new ListNode<>(e); if(head == null){ head = tail = listNode; }else{ tail.next = listNode; tail = listNode; } size++; } @Override public E poll() { if(isEmpty()){ throw new NoSuchElementException("queue is empty cant poll"); } E e = head.val; ListNode listNode = head; head = head.next; listNode.next = listNode = null; size--; return e; } @Override public E peek() { if(isEmpty()){ throw new NoSuchElementException("queue is empty cant peek!"); } return head.val; } @Override public boolean isEmpty() { return size == 0; } }



