栈的认识
========
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
????????
出栈：栈的删除操作叫做出栈,出数据在栈顶
? ? ? ? ?
栈是一种先进后出的数据结构
栈的功能
========
由于栈是一种特殊的数据结构,一次出栈的元素只能出最后入栈的元素,所以不能通过下标进行随机查询,也不能通过下标进行随机取元素操作,以下是栈涉及到的操作
public boolean empty() // 返回栈是否为空。
public int peek() // 返回栈顶部的对象，而不从栈中删除它。
public int pop() // 删除栈顶部的对象，并将该对象作为此函数的值返回。
public void push() // 入栈操作
接下来,就使用 Java 实现以上的方法,在实现功能前,先创建一个数组用来储存数据,再创建一个变量 top 记录当前栈顶的元素.
class MyStack{
private int[] elem;//数组存放元素
private int top;// 栈顶指针
public MyStack() {
this.elem = new int[10];// 初始容量为10
this.top = 0;
}
}
实现
======
入栈
从图中,可以知道,每次入栈操作,都在 top 指针处插入数据,且 top 指针自增一次,所以可以写成在数组的top位置进行插入数据.
public void push(int item) {
// 可以分为两步操作
/*
this.elem[top] = item;
this.top++;
*/
// 也可以一步到位
this.elem[top++] = item;
}
取栈顶元素
这个操作,是不会把栈中的元素进行删除,所以根据图片可以看到,要想得到栈顶的元素,top 指针要往下走一步,且不能改变 top 的位置,否则下次插入会改变当前栈首元素的值,所以可以直接取 top - 1 位置处的元素,既不改变 top,也能拿到栈顶元素,不过在 top 为 0 的情况下,也就是栈为空的情况下,我们需要进行处理,否则会产生数组越界异常.
??public int peek() {
if (this.top == 0) {
throw new UnsupportedOperationException("栈中元素为空!");// 手动抛一个异常 提示
}
return this.elem[this.top - 1]; // 返回top - 1 的元素,不改变 top 本身
}
出栈
出栈操作,使用的是覆盖方法,将当前 top 指针往下一位,等下次 添加元素的时候就能覆盖当前要删除的元素,即使没有要添加的元素,由于 top 指针变了,当前其它操作也访问不到删除的元素,所以移动 top 指针既可达到我们逻辑上的删除.
public int pop() {
if (this.top == 0) {
throw new UnsupportedOperationException("栈顶元素为空");
}
return this.elem[--this.top];// 将 top 指针下移一位,切返回当前的要删除的元素
}
栈是否为空
判断当前 top 是否等于 0 即可
public boolean empty() {
return this.top == 0;
}
栈的使用
====
实现完方法之后,接下来简单了解一下栈的使用方法
public static void main(String[] args) {
MyStack myStack = new MyStack();
Stack<Integer> stack = new Stack<>();
myStack.push(1);
myStack.push(2);
myStack.push(3);
myStack.push(4);
myStack.push(5);
while (!myStack.empty()){
System.out.print(myStack.pop() + " ");
}
}
由于添加的顺序是 1 -> 2 -> 3 -> 4 -> 5 , 根据后进先出的特性,输出 应该为 5 -> 4 -> 3 -> 2 -> 1
ze_20,color_FFFFFF,t_70,g_se,x_16)
以上就是关于如何使用 JAVA 实现 栈 的所有内容,接下来我们去学习一下 另外一种数据结构 <队列>
队列的认识
=========
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表
入队列：进行插入操作的一端称为队尾（Tail）
出队列：进行删除操作的一端称为队头（Head）
?
队列是一个具有先进先出特性的数据结构
队列的功能
=========
队列这种特殊的数据结构的特性,在现实生活中很多也很常见,拿火车站买票来说,先到售票窗口前的人能先买到票,后到购票窗口的人只能排队等先到的人买完才能买,队列也是,只有先入队列的元素出队列之后,后面入队列的元素才能出队列,不允许随机访问元素
public boolean isEmpty() // 判断队列是否为空
public void offer(E e) // 入队列,则将指定的元素插入到此队列中。
public int peek() // 返回队头元素
public int poll() // 出队列,删除队头元素,并返回改值
上面就是队列的常用方法,在实现功能前,我们先考虑是用数组来实现队列,还是用链表来实现比较好?我们可以比较一下两种结构的时间复杂度
- 入队列:入队列的时候使用的是尾插法
1. 数组:用数组实现尾插法 , 使用一个指针记录尾部 , 进行插入时直接通过尾部指针进行插入 , 不需要格外的遍历 , 时间复杂度为 O(1).
2. 链表:用链表实现尾插法 , 使用一个尾节点记录尾部 , 进行插入时直接通过尾节点进行插入,不需要格外的遍历 , 时间复杂度为 O(1)
- 出队列:出队列的时候使用的是头删法
1. 数组:用数组实现头删法 , 需要将后面的数据覆盖前面的数据 , 时间复杂度是O(N)
2. 链表:用链表实现头删法,只需要使用一个头节点记录对头位置 , 删除时 将头节点指向当前对头的下一个节点即可
由此得出,在实现队列使用的存储方式时,使用链表的时间复杂度更低,那就先创建一个节点类,用来存储数据及下一个节点的地址
public class MyQueue {
// 可以使用内部类,定义在实现类里面
private static class Node {
public int val;
public Node next;
public Node(int val) {
this.val = val;
}
}
private Node head;// 记录头节点
private Node tail; // 记录尾节点
}
实现
======
入队列
入队列分为两种情况
- 第一次入队列,队列是为空的,需要先将头节点和尾节点都指向当前的节点
- 非第一次队列,需要将 tail 的 next 指针指向 当前插入的节点,且 tail 节点 也要更新成当前节点
public void offer(int val) {
// 创建新节点
Node node = new Node(val);
//尾插法 需要判断是不是第一次插入
if (isEmpty()) {
this.head = node;
this.tail = node;
return;
}
this.tail.next = node;
this.tail = node;
}
出队列
出队列也分两种情况
-
队列为空:如果队列为空,调用出队列的方法时,我们应该抛出一个异常提示
-
队列不为空:队列不为空,采用头删法,将 head 节点 更新成 head.next 的节点,此时就能达到删除队头元素的效果了.
public int poll() {
//判断是否为空队列的
if (isEmpty()) {
throw new UnsupportedOperationException("队列为空");
}
// 记录要删除对头的元素
int ret = this.head.val;
// 更改 head 指向
this.head = this.head.next;
return ret;
}
取对头元素
我们在前面使用了 head 引用,记录了 队头,所以只需要放回 head 引用的值即可,需要判断队列是否为空,为空的话需要抛出异常提示
public int peek() {
//不要移动first
if (isEmpty()) {
throw new UnsupportedOperationException("链表为空");
}
return this.head.val;
标签：Java,队列,top,元素,节点,int,数据结构,public From： https://blog.51cto.com/u_15767198/5899853