【学点数据结构和算法】03-栈和队列
写在前面： 博主是一名大数据的初学者，昵称来源于《爱丽丝梦游仙境》中的Alice和自己的昵称。作为一名互联网小白，
写博客一方面是为了记录自己的学习历程，一方面是希望能够帮助到很多和自己一样处于起步阶段的萌新。由于水平有限，博客中难免会有一些错误，有纰漏之处恳请各位大佬不吝赐教！个人小站:http://alices.ibilibili.xyz/ , 博客主页:https://alice.blog.csdn.net/ 尽管当前水平可能不及各位大佬，但我还是希望自己能够做得更好，因为一天的生活就是一生的缩影。我希望在最美的年华，做最好的自己！
之前已经写过关于数组和链表的博客，按照学习的顺序，本篇我们来学习点关于栈和队列的知识。
栈
栈（stack）是一种线性数据结构，它就像一个上图所示的放入乒乓球的圆筒容器， 栈中的元素只能先入后出（First In Last Out，简称FILO）。最早进入的元素存放的位置 叫作栈底（bottom），最后进入的元素存放的位置叫作栈顶（top）。
栈这种数据结构既可以用数组来实现，也可以用链表来实现。
栈的数组实现如下
栈的链表实现如下
栈的基本操作
栈常用的操作包含入栈和出栈。
入栈
入栈操作（push）就是把新元素放入栈中，只允许从栈顶一侧放入元素，新元素的位置将会成为新的栈顶。
这里我们以数组实现为例。
出栈
出栈操作（pop）就是把元素从栈中弹出，只有栈顶元素才允许出栈，出栈元素的前一个元素将会成为新的栈顶。
这里我们以数组实现为例。
用数组实现简单栈
/**
* @Author: Alice菌
* @Date: 2020/6/20 20:24
* @Description:
* 用数组实现简单栈
*/
public class OwnArrayStack<T> {
private static final Integer DEFAULT_SIZE = 10;
/*** 栈 */
private T[] items;
/*** 栈顶所在角标 */
private int top = -1;
/*** 栈总容量 */
private int size;
public OwnArrayStack() {
this(DEFAULT_SIZE);
}
public OwnArrayStack(int len) {
if (len <= 0) {
throw new IndexOutOfBoundsException("new instance error, len need more than 0, size: " + len);
}
size = len;
items = (T[]) new Object[size];
}
/**
* 判断栈是否为控
*
* @return
*/
public boolean isEmpty() {
return top == -1;
}
/**
* 进栈
*
* @param t
* @return
*/
public boolean push(T t) {
if (top == size - 1) {
return false;
}
items[++top] = t;
return true;
}
/**
* 出栈
*
* @return
*/
public T pop() {
if (isEmpty()) {
return null;
}
T item = items[top];
items[top--] = null;
return item;
}
/**
* 获取栈顶元素
*
* @return
*/
public T top() {
if (isEmpty()) {
return null;
}
return items[top];
}
public static void main(String[] args) {
OwnArrayStack<Integer> stack = new OwnArrayStack<Integer>();
for (int i = 0; i < DEFAULT_SIZE + 1; i++) {
System.out.println("push: " + stack.push(i) + ", item: " + i);
}
for (int i = 0; i < DEFAULT_SIZE + 1; i++) {
System.out.println("top: " + stack.top() + ", pop: " + stack.pop());
}
}
}用链表实现简单栈
import lombok.AllArgsConstructor;
import lombok.Data;
/**
* @Author: Alice菌
* @Date: 2020/6/20 20:36
* @Description:
*/
public class OwnLinkedStack<T> {
private static final Integer DEFAULT_SIZE = 10;
/*** 栈顶元素 */
private Node top;
/*** 栈当前容量 */
private Integer index;
/*** 栈总容量 */
private Integer size;
public OwnLinkedStack() {
this(DEFAULT_SIZE);
}
public OwnLinkedStack(Integer len) {
if (len <= 0) {
throw new IndexOutOfBoundsException("new instance error, len need more than 0, size: " + len);
}
index = -1;
size = len;
}
/**
* 判断栈是否为空
*
* @return
*/
public Boolean isEmpty() {
return top == null;
}
/**
* 压栈
*
* @param t
* @return
*/
public boolean push(T t) {
if (index >= size - 1) {
return false;
}
Node old = top;
top = new Node(t, old);
index++;
return true;
}
/**
* 弹栈
*
* @return
*/
public Node pop() {
if (isEmpty()) {
return null;
}
Node result = top;
top = top.next;
index--;
return result;
}
/**
* 获取栈顶元素
*
* @return
*/
public Node top() {
return top;
}
@Data
@AllArgsConstructor
private class Node {
private T data;
private Node next;
}
public static void main(String[] args) {
OwnLinkedStack<String> stack = new OwnLinkedStack<String>();
for (int i = 0; i < DEFAULT_SIZE + 1; i++) {
System.out.println("push: " + stack.push(String.valueOf(i)) + ", item: " + i);
}
for (int i = 0; i < DEFAULT_SIZE + 1; i++) {
System.out.println("top: " + stack.top());
System.out.println("pop: " + stack.pop());
}
}
}小提示:
入栈和出栈只会影响到最后一个元素，不涉及其他元素的整体移动，所以无论是以数组还是以链表实现，入栈、出栈的时间复杂度都是O(1)
队列
队列（queue）是一种线性数据结构，它的特征和行驶车辆的单行隧道很相似。不同于栈的先入后出，队列中的元素只能先入先出（First In First Out，简称FIFO）。队列的出口端叫作队头（front），队列的入口端叫作队尾（rear）。
与栈类似，队列这种数据结构既可以用数组来实现，也可以用链表来实现。
队列的数组实现如下。
队列的链表实现如下。
队列基本操作
对于链表实现方式，队列的入队、出队操作和栈是大同小异的。但对于数组实现方式 来说，队列的入队和出队操作有了一些有趣的变化。
入队
入队（enqueue）就是把新元素放入队列中，只允许在队尾的位置放入元素，新元素 的下一个位置将会成为新的队尾。
出队
出队操作（dequeue）就是把元素移出队列，只允许在队头一侧移出元素，出队元素的后一个元素将会成为新的队头。
如果像这样不断出队，队头左边的空间失去作用，那队列的容量岂 不是越来越小了？例如像下面这样。
为了解决这个问题，我们可以用数组实现的队列可以采用循环队列的方式来维持队列容量的恒定。
假设一个队列经过反复的入队和出队操作，还剩下2个元素，在“物理”上分布于数组 的末尾位置。这时又有一个新元素将要入队。
在数组不做扩容的前提下，如何让新元素入队并确定新的队尾位置呢？我们可以利用 已出队元素留下的空间，让队尾指针重新指回数组的首位。
这样一来，整个队列的元素就“循环”起来了。在物理存储上，队尾的位置也可以在队 头之前。当再有元素入队时，将其放入数组的首位，队尾指针继续后移即可。
一直到（队尾下标+1）%数组长度 = 队头下标时，代表此队列真的已经满了。需要 注意的是，队尾指针指向的位置永远空出1位，所以队列最大容量比数组长度小1。
循环队列代码实现
public class OwnQueue {
private int[] array;
private int front;
private int rear;
public OwnQueue(int capacity){
this.array = new int[capacity];
}
/**
* 入队
* @param element 入队的元素
*/
public void enQueue(int element) throws Exception {
if((rear+1)%array.length == front){
throw new Exception("队列已满！");
}
array[rear] = element;
rear =(rear+1)%array.length;
}
/**
* 出队
*/
public int deQueue() throws Exception {
if(rear == front){
throw new Exception("队列已空！");
}
int deQueueElement = array[front];
front =(front+1)%array.length;
return deQueueElement;
}
/**
* 输出队列
*/
public void output(){
for(int i=front; i!=rear; i=(i+1)%array.length){
System.out.println(array[i]);
}
}
public static void main(String[] args) throws Exception {
OwnQueue myQueue = new OwnQueue(6);
myQueue.enQueue(3);
myQueue.enQueue(5);
myQueue.enQueue(6);
myQueue.enQueue(8);
myQueue.enQueue(1);
myQueue.deQueue();
myQueue.deQueue();
myQueue.deQueue();
myQueue.enQueue(2);
myQueue.enQueue(4);
myQueue.enQueue(9);
myQueue.output();
}
}循环队列不但充分利用了数组的空间，还避免了数组元素整体移动的麻烦，可以说是很巧妙了。
本篇博客中代码和彩图来源于《漫画算法》， 感兴趣的朋友可以去购买正版实体书，确实不错，非常适合小白入门。
小结
- 什么是栈
栈是一种线性逻辑结构，可以用数组实现，也可以用链表实现。栈包含入栈和出栈操 作，遵循先入后出的原则（FILO）。
- 什么是队列
队列也是一种线性逻辑结构，可以用数组实现，也可以用链表实现。队列包含入队和 出队操作，遵循先入先出的原则（FIFO）。
下一篇博客将为大家介绍散列表，敬请期待!!!
如果本文对您有所帮助，不妨点个赞支持一下博主?
希望我们都能在学习的道路上越走越远?