栈和队列
一、栈
栈又称为堆栈，是一种运算受限的线性表，这是因为它仅允许在线性表的固定一端（表尾）进行插入、删除和读取元素等运算，不允许在其他任何位置进行运算。
相关名词：栈顶、栈顶元素、栈底、进栈（压栈）、出栈（退栈）
特点：后进先出
时间复杂度：O(1)
1. 顺序存储结构
需要一个数组和整型变量，利用数组来存储元素，利用整型变量存储栈顶元素的下标，通常用top表示，也叫栈顶指针。
top=-1时表示栈空；
压栈时，首先将top增1，用来指代新的栈顶位置，然后把新元素赋值到栈顶位置上；
退栈时，先取出栈顶元素，然后top减1；
top指向最后一个下标位置时，栈满。若再添加元素时，需要重新分配更大的数组空间
/*** 栈的基本基本功能** @author root*/public interface Stack {// 向栈顶插入一个元素void push(Object obj);// 删除栈顶元素并返回Object pop();// 返回栈顶元素Object peek();// 是否为空boolean isEmpty();// 清空栈内元素void clean();}/*** 栈基本功能实现** @author root*/public class SequenceStack implements Stack {// 栈的一维数组初始长度final int minSize = 10;// 栈保存元素依赖于数组private Object[] stackArray;// 栈顶元素位置下标（相当于数组下标），栈顶指针private int top;/*** 构造函数*/SequenceStack() {top = -1;// -1表示初始化时栈顶没有元素stackArray = new Object[minSize];}SequenceStack(int n) {// 指定元素存储空间if (n < minSize) {n = minSize;}top = -1;stackArray = new Object[n];}/*** 往栈中压入元素*/@Overridepublic void push(Object obj) {// 1.判断数组空间，若已满，则创建2倍空间数组，复制到新空间// 2.栈顶指针+1// 3.新元素写到新栈顶位置if (top == this.stackArray.length - 1) {Object[] b = new Object[2 * top];for (int i = 0; i <= top; i++) {b[i] = this.stackArray[i];}stackArray = b;}top++;stackArray[top] = obj;}/*** 弹出栈顶元素*/@Overridepublic Object pop() {// 1.判断栈是否为空，空时返回null// 2.栈顶指针-1// 3.返回栈顶元素if (top == -1) {return null;}top--;return this.stackArray[top + 1];}/*** 查看栈顶元素*/@Overridepublic Object peek() {if (top == -1) {return null;}return stackArray[top];}/*** 栈是否为空*/@Overridepublic boolean isEmpty() {return top == -1;}/*** 清空栈*/@Overridepublic void clean() {this.top = -1;}}/*** 测试栈的基本功能** @author root*/public class SequenceStackTest {public static void main(String[] args) {Stack stack = new SequenceStack();int[] a = { 2, 4, 23, 3, 5 };for (int i = 0; i < a.length; i++) {stack.push(a[i]);}System.out.println("stack.pop:" + stack.pop());// 5stack.push(1);System.out.println(stack.peek());// 1stack.clean();System.out.println(stack.isEmpty());// true}}
2. 链式存储结构
由结点构成的单链表实现，也成为链栈，即链接存储的栈。表头指针成为栈顶指针，由栈顶节点指向的元素结点称为栈顶结点。
压栈时，使新元素的结点指针域指向原先的栈顶结点，栈顶指针指向新元素结点；
退栈时，栈顶指针指向后继结点；
空栈：top为null
/*** 节点类** @author root*/public class Node {Object element;// 值域Node next;// 指针域Node(Node next) {this.next = next;}Node(Object element, Node next) {this.element = element;this.next = next;}}/*** 链表结构的栈** @author root**/public class LinkStack implements Stack {private Node top;// 栈顶指针LinkStack() {this.top = null;// 初始化为空栈}@Overridepublic void push(Object obj) {top = new Node(obj, top);// 相当于在单链表表头插入结点}/*** 弹出栈顶元素*/@Overridepublic Object pop() {if (top == null) {return null;}Node p = top; // 将栈顶引用保存到p中top = top.next;// 栈顶指针指向下一个结点return p.element;// 弹出原先栈顶元素}@Overridepublic Object peek() {if (top == null) {return null;}return top.element;// 返回栈顶元素的值}@Overridepublic boolean isEmpty() {return top == null;}@Overridepublic void clean() {top = null;}}
三、队列
Stack类：栈类 过时 public class Stack<E> extends Vector<E>Queue：队列类Deque：双端队列（栈操作建议使用）public class LinkedList<E>extends AbstractSequentialList<E>implements List<E>, Deque<E>, Cloneable, java.io.Serializablepublic interface Deque<E> extends Queue<E> 扩展了java.util.Collection接口
/**** 队列的基本功能*@author root**/public interface Queue {// 进队，在队尾部插入新元素void enter(Object obj);// 出队，从队首删除并返回对首元素Object leave();// 返回队首元素Object peek();// 队列是否为空boolean isEmpty();// 清空队列void clean();}/*** 顺序队列** @author root**/public class SequenceQueue implements Queue {// 存储队列的一维数组最小空间final int minSize = 10;// 存储队列的数组空间private Object[] queueArray;private int front;// 队首指针private int rear;// 队尾指针/*** 构造函数*/SequenceQueue() {this.front = 0;this.rear = 0;queueArray = new Object[minSize];}SequenceQueue(int n) {this.front = 0;this.rear = 0;if (n <= minSize) {n = minSize;}queueArray = new Object[n];}@Overridepublic void enter(Object obj) {// 队列已满（有两种情形），分配双倍空间，并复制到新空间数组内if ((this.rear + 1) % this.queueArray.length == this.front) {Object[] p = new Object[2 * this.queueArray.length];// 已满，队尾指针在后if (this.rear == this.queueArray.length - 1) {for (int i = 1; i <= this.rear; i++) {p[i] = this.queueArray[i];}} else {// 已满，队尾指针在前// 先复制队列前面元素，后复制队列后部分元素int k = 1;for (int i = this.front + 1; i < this.queueArray.length - 1; i++, k++) {p[k] = this.queueArray[i];}for (int j = 0; j <= this.rear; j++, k++) {p[k] = this.queueArray[j];}this.front = 0;this.rear = this.queueArray.length - 1;}queueArray = p;}this.queueArray[(this.rear + 1) % this.queueArray.length] = obj;}@Overridepublic Object leave() {if (this.front == this.rear) {return null;}this.front = (this.front + 1) % this.queueArray.length;// 将队首指针指向下一个队首元素位置return queueArray[this.front];}@Overridepublic Object peek() {if (this.front == this.rear) {return null;}return queueArray[(this.front + 1) % this.queueArray.length];}@Overridepublic boolean isEmpty() {return this.front == this.rear;}@Overridepublic void clean() {this.front = this.rear = 0;}}//链式存储结构/*** 节点类** @author root*/public class Node {Object element;// 值域Node next;// 指针域Node(Node next) {this.next = next;}Node(Object element, Node next) {this.element = element;this.next = next;}}/*** 链式队列** @author root*/public class LinkQueue implements Queue {private Node front;private Node rear;LinkQueue() {this.front = this.rear = null;}@Overridepublic void enter(Object obj) {if (this.rear == null) {this.front = this.rear = new Node(obj, null);} else {this.rear = this.rear.next = new Node(obj, null);}}@Overridepublic Object leave() {if (this.front == null) {return null;}Node x = this.front;this.front = this.front.next;if (this.front == null) {this.rear = null;}return x.element;}@Overridepublic Object peek() {if (this.front == null) {return null;}return this.front.element;}@Overridepublic boolean isEmpty() {// TODO Auto-generated method stubreturn this.front == null;}@Overridepublic void clean() {this.front = this.rear = null;}}
1. 双端队列
public interface Queue extends Collection
扩展了java.util.Collection接口
Queue使用时要尽量避免Collection的add()和remove()方法，而是要使用offer()来加入元素，使用poll()来获取并移出元素。它们的优点是通过返回值可以判断成功与否，add()和remove()方法在失败的时候会抛出异常。 如果要使用前端而不移出该元素，使用element()或者peek()方法。
所以Java中实现栈和队列操作都可以通过使用LinkedList类实现，当然底层使用的链表。
public class ArrayDeque<E> extends AbstractCollection<E>
implements Deque<E>, Cloneable, Serializable
ArrayDeque是Deque 接口的大小可变数组的实现
/**
* 功能：模拟生活中罗盘子案例
* 技能：LinkedList
*
* LinkedList既可以当做线性表处理，也可以当做栈、队列使用
* @author Administrator*
*/
public class TestDeque {
public static void main(String[] args) {
//创建一个栈
Deque deque = new LinkedList();
//罗盘子:入栈
// deque.addFirst("盘子1");
// deque.addFirst("盘子2");
// deque.addFirst("盘子3");
deque.push("盘子1");
deque.push("盘子2");
deque.push("盘子3");
//获取最上面的盘子：获取栈顶元素
// System.out.println(deque.getFirst());
// System.out.println(deque.getFirst());
// System.out.println(deque.getFirst());
System.out.println(deque.peek());
System.out.println(deque.peek());
System.out.println(deque.peek());
//拿走盘子：出栈
// System.out.println(deque.removeFirst());
// System.out.println(deque.removeFirst());
// System.out.println(deque.removeFirst());
System.out.println(deque.pop());
System.out.println(deque.pop());
System.out.println(deque.pop());
}
}
总之：
1、深入理解pop的深层含义
2、分清是栈还是堆，以及二者的区别：
①：栈是后进先出，使用的关键词是：pop，push和peek
②：堆是先进先出，使用的关键词是：enqueue、dequeue和peek
Java中Queue有一些常用的方法：
offer、add
poll、remove
peek、element
add(),remove(),element() 方法是抛出异常让你处理，
而poll(),offer(),peek()方法比较友好，直接返回false。
2. 优先级队列(Priority Queue)
注：队列是一种特征为FIFO的数据结构，每次从队列中取出的是最早加入队列中的元素。但是，许多应用需要另一种队列，每次从队列中取出的应是具有最高优先权的元素，这种队列就是优先级队列(Priority Queue)，也称为优先权队列。
- 优先级队列的概念
- 优先级队列的定义
- 优先级队列是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素。
2. 优先级队列的特点
- 优先级队列是0个或多个元素的集合，每个元素都有一个优先权或值。
- 当给每个元素分配一个数字来标记其优先级时，可设较小的数字具有较高的优先级，这样更方便地在一个集合中访问优先级最高的元素，并对其进行查找和删除操作。
- 对优先级队列，执行的操作主要有：(1)查找，(2)插入，(3)删除。
- 在最小优先级队列(min Priority Queue)中，查找操作用来搜索优先权最小的元素，删除操作用来删除该元素。
- 在最大优先级队列(max Priority Queue)中，查找操作用来搜索优先权最大的元素，删除操作用来删除该元素。
- 插入操作均只是简单地把一个新的元素加入到队列中。
- 注：每个元素的优先级根据问题的要求而定。当从优先级队列中删除一个元素时，可能出现多个元素具有相同的优先权。在这种情况下，把这些具有相同优先权的元素视为一个先来先服务的队列，按他们的入队顺序进行先后处理。
public static class MyComparator implements Comparator<Integer> {
// 负，第一个参数在前
// 正，第二个参数在前
// 0, 谁放前都行
@Override
public int compare(Integer o1, Integer o2) {
if (o1 < o2) {
return 1;
} else if (o1 > o2) {
return -1;
} else {
return 0;
}
}
}
public static class Student {
public String name;
public int id;
public int age;
public Student(String name, int id, int age) {
this.name = name;
this.id = id;
this.age = age;
}
}
// 谁id大，谁放前！
public static class IdComparator implements Comparator<Student> {
// 如果返回负数，认为第一个参数应该排在前面
// 如果返回正数，认为第二个参数应该排在前面
// 如果返回0，认为谁放前面无所谓
@Override
public int compare(Student o1, Student o2) {
if (o1.id < o2.id) {
return 1;
} else if (o2.id < o1.id) {
return -1;
} else {
return 0;
}
}
}
public static void main(String[] args) {
String str1 = "abc";
String str2 = "b";
System.out.println(str1.compareTo(str2)); //字典序
PriorityQueue<Student> heap = new PriorityQueue<>(new IdComparator());
Student s1 = new Student("张三", 5, 27);
Student s2 = new Student("李四", 1, 17);
Student s3 = new Student("王五", 4, 29);
Student s4 = new Student("赵六", 3, 9);
Student s5 = new Student("左七", 2, 34);
heap.add(s1);
heap.add(s2);
heap.add(s3);
heap.add(s4);
heap.add(s5);
System.out.println("=========");
while (!heap.isEmpty()) {
Student s = heap.poll();
System.out.println(s.name + ", " + s.id + ", " + s.age);
}
}
跟有序有关的结构都可以排序
字符串的compareTo()是 字典序:
1. 如果两个字符串是等长的ascll码比较
1. 如果两个字符串不是等长 短的补成跟长的一样长 用最小的ascll码来补
23. 合并K个升序链表
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null) {
return null;
}
PriorityQueue<ListNode> heap = new PriorityQueue<>(new ListNodeComparator());
for (int i = 0; i < lists.length; i++) {
if (lists[i] != null) {
heap.add(lists[i]);
}
}
if (heap.isEmpty()) {
return null;
}
ListNode head = heap.poll();
ListNode pre = head;
if (pre.next != null) {
heap.add(pre.next);
}
while (!heap.isEmpty()) {
ListNode cur = heap.poll();
pre.next = cur;
pre = cur;
if (cur.next != null) {
heap.add(cur.next);
}
}
return head;
}
public static class ListNodeComparator implements Comparator<ListNode> {
@Override
public int compare(ListNode o1, ListNode o2) {
return o1.val - o2.val;
}
}
}
四. 双链表实现队列和栈
public static class DoubleEndsQueue<T> {
public Node<T> head;
public Node<T> tail;
/**
* 从头部加节点
*/
public void addFromHead(T value) {
Node<T> cur = new Node<T>(value);
if (head == null) {
head = cur;
tail = cur;
} else {
cur.next = head;
head.last = cur;
head = cur;
}
}
/**
* 从尾部加节点
*/
public void addFromBottom(T value) {
Node<T> cur = new Node<T>(value);
if (head == null) {
head = cur;
tail = cur;
} else {
cur.last = tail;
tail.next = cur;
tail = cur;
}
}
public T popFromHead() {
if (head == null) {
return null;
}
Node<T> cur = head;
if (head == tail) {
head = null;
tail = null;
} else {
head = head.next;
cur.next = null;
head.last = null;
}
return cur.value;
}
public T popFromBottom() {
if (head == null) {
return null;
}
Node<T> cur = tail;
if (head == tail) {
head = null;
tail = null;
} else {
tail = tail.last;
tail.next = null;
cur.last = null;
}
return cur.value;
}
public boolean isEmpty() {
return head == null;
}
}
1. 双链表实现栈
public static class MyStack<T> {
private DoubleEndsQueue<T> queue;
public MyStack() {
queue = new DoubleEndsQueue<T>();
}
public void push(T value) {
queue.addFromHead(value);
}
public T pop() {
return queue.popFromHead();
}
public boolean isEmpty() {
return queue.isEmpty();
}
}
2. 双链表实现队列
public static class MyQueue<T> {
private DoubleEndsQueue<T> queue;
public MyQueue() {
queue = new DoubleEndsQueue<T>();
}
public void push(T value) {
queue.addFromHead(value);
}
public T poll() {
return queue.popFromBottom();
}
public boolean isEmpty() {
return queue.isEmpty();
}
}
五、数组实现队列:环形数组
public class RingArray {
public static class MyQueue {
private int[] arr;
private int pushi;// end
private int polli;// begin
private int size;
private final int limit;
public MyQueue(int limit) {
arr = new int[limit];
pushi = 0;
polli = 0;
size = 0;
this.limit = limit;
}
public void push(int value) {
if (size == limit) {
throw new RuntimeException("队列满了，不能再加了");
}
size++;
arr[pushi] = value;
pushi = nextIndex(pushi);
}
public int pop() {
if (size == 0) {
throw new RuntimeException("队列空了，不能再拿了");
}
size--;
int ans = arr[polli];
polli = nextIndex(polli);
return ans;
}
public boolean isEmpty() {
return size == 0;
}
// 如果现在的下标是i，返回下一个位置
private int nextIndex(int i) {
return i < limit - 1 ? i + 1 : 0;
}
}
}
六、 队列和栈的转换
1. 如何用栈结构实现队列
原则:
- pop栈为空的时候才能将push栈倒到pop栈
- push要一次性全部倒过去
public static class TwoStacksQueue {
public Stack<Integer> stackPush;
public Stack<Integer> stackPop;
public TwoStacksQueue() {
stackPush = new Stack<Integer>();
stackPop = new Stack<Integer>();
}
// push向pop转入
private void pushToPop() {
if (stackPop.empty()) {
while (!stackPush.empty()) {
stackPop.push(stackPush.pop());
}
}
}
public void push(int pushInt) {
stackPush.push(pushInt);
pushToPop();
}
public int pop() {
if (stackPop.empty() && stackPush.empty()) {
throw new RuntimeException("Queue is empty!");
}
pushToPop();
return stackPop.pop();
}
public int peek() {
if (stackPop.empty() && stackPush.empty()) {
throw new RuntimeException("Queue is empty!");
}
pushToPop();
return stackPop.peek();
}
public boolean empty() {
return stackPop.isEmpty() && stackPush.isEmpty();
}
}
2. 如何用队列结构实现栈结构
方法1:
class MyStack {
public Queue<Integer> queue;
public MyStack() {
queue = new LinkedList<Integer>();
}
public void push(int x) {
int n = queue.size();
queue.offer(x);
for (int i = 0; i < n; i++) {
queue.offer(queue.poll());
}
}
public int pop() {
return queue.poll();
}
public int top() {
return queue.peek();
}
public boolean empty() {
return queue.isEmpty();
}
}
public static class TwoQueueStack<T> {
public Queue<Integer> queue;
public Queue<Integer> help;
public TwoQueueStack() {
queue = new LinkedList<>();
help = new LinkedList<>();
}
public void push(int value) {
queue.offer(value);
}
public int top() {
while (queue.size() > 1) {
help.offer(queue.poll());
}
int ans = queue.poll();
help.offer(ans);
Queue<Integer> tmp = queue;
queue = help;
help = tmp;
return ans;
}
public int pop() {
while (queue.size() > 1) {
help.offer(queue.poll());
}
int ans = queue.poll();
Queue<Integer> tmp = queue;
queue = help;
help = tmp;
return ans;
}
public boolean empty() {
return queue.isEmpty();
}
}
方法2:
class MyStack2 {
public Queue<Integer> queue;
public Queue<Integer> help;
public MyStack2() {
queue = new LinkedList<Integer>();
help = new LinkedList<Integer>();
}
public void push(int x) {
help.offer(x);
while (!queue.isEmpty()) {
help.offer(queue.poll());
}
Queue<Integer> temp = queue;
queue = help;
help = temp;
}
public int pop() {
return queue.poll();
}
public int top() {
return queue.peek();
}
public boolean empty() {
return queue.isEmpty();
}
}
若有收获，就点个赞吧
0 人点赞
