文章目录

栈什么是栈？栈的实现用顺序表来实现：用链表来实现 队列什么是队列？队列的实现顺序表实现用链表实现

栈

什么是栈？

栈是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。

压栈:栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。 出栈:栈的删除操作叫做出栈。出数据在栈顶。 我们可以把压栈和出栈这个过程想像成我们在地上放了一个箱子，这时候我们给箱子里面一本书，当我们再想给箱子里放一本书的时候，我们只能把新放的一本书放在之前那本的上面，这个过程就是入栈(也叫压栈)，而当我们想取书的时候我们也只能取最上面的那一本书，这个过程就叫做出栈。

栈的实现

用顺序表来实现用链表来实现

用顺序表来实现：

public class MyStack { private int[] array = new int[100]; private int size = 0; //压栈 public void push(int val) { array[size] = val; size++; } //出栈 public Integer pop() { //如果为栈为空，直接返回null if (size == 0) { return null; } int ret = array[size - 1]; size--; return ret; } //查看栈顶元素 public Integer peek() { //如果为栈为空，直接返回null if (size == 0) { return null; } return array[size - 1]; } //判断栈是否为空 public boolean isEmpty() { return size == 0; } //查看栈的大小 public int size() { return size; } }

用链表来实现

//先创建一个节点类 class ListNode { ListNode next; int val; public ListNode(int val) { this.val = val; } } public class MyStack2 { //头节点 ListNode head = null; //尾节点 ListNode tail = null; int size = 0; //入栈 public void push(int val) { ListNode node = new ListNode(val); //空栈的情况 if (size == 0) { head = node; tail = node; size++; return; } //非空栈的情况 tail.next = node; tail = tail.next; size++; return; } //出栈 public Integer pop() { //空栈的情况; if (size == 0) { return null; } Integer ret = tail.val; ListNode node = head; //寻找到tail节点的上一个节点 for (int i = 0; i < size - 2; i++) { node = node.next; } tail = node; size--; //如果最后一个节点也被删除了，那么我们需要将 tail 也指向 null if (size == 0) { head = null; tail = head; } return ret; } //查看栈顶元素 public Integer peek() { //空栈的情况; if (size == 0) { return null; } return tail.val; } //查看是否是空栈 public boolean isEmpty() { return size == 0; } //查看栈的大小 public int size() { return size; } }

队列

什么是队列？

队列:只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列:进行插入操作的一端称为队尾(Tail/Rear) 出队列:进行删除操作的一端称为队头 (Head/Front) 队列可以想象成我们在经过一座桥，这个桥只允许从右往左走，先上桥的人只能从左边出，后上桥的人只能从右边进，这就是一个队列。

队列的实现

用顺序表实现用链表实现

顺序表实现

public class MyQueue2 { private int[] array = new int[100]; private int head = 0; private int tail = 0; private int size = 0; //入队列 public void offer(int val) { //队列为空 if (size == array.length) { System.out.println("队列已满,插入失败"); return; } array[tail] = val; tail++; if (tail == array.length) { tail = 0; } size++; } //出队列 public Integer poll() { //队列为空 if (size == 0) { return null; } Integer ret = array[head]; head++; if (head == array.length) { head = 0; } size--; return ret; } //取队首元素 public Integer peek() { //队列为空 if (size == 0) { return null; } return array[head]; } //判断队列是否为空 public boolean isEmpty() { return size == 0; } //查看队列大小 public int size() { return size; } }

用链表实现

//先创建一个节点类 class ListNode { ListNode next; int val; public ListNode(int val) { this.val = val; } } public class MyQueue { //头节点 private ListNode head = null; //尾节点 private ListNode tail = null; private int size = 0; //入队列 public void offer(int val) { ListNode node = new ListNode(val); //队列为空 if (size == 0) { head = node; tail = node; size++; return; } tail.next = node; tail = tail.next; size++; } //出队列 public Integer poll() { //队列为空 if (size == 0) { return null; } Integer ret = head.val; head = head.next; //如果最后一个节点删除了，我们就需要将 tail 也指向 null if (head == null) { tail = head; } size--; return ret; } //队首元素 public Integer peek() { //队列为空 if (head == null) { return null; } Integer ret = head.val; return ret; } //判断队列是否为空 public boolean isEmpty() { return size == 0; } //查看队列大小 public int size() { return size; } }