【数据布局】栈和队列
目次栈
1、概念
2、 栈的使用
3、 栈的模仿实现
相干概念区分
队列
1、 概念
2、队列的使用
3、队列模仿实现
4、 循环队列
为什么要有循环列队
怎样区分空与满
5、双端队列 )
栈
1、概念
栈(Stack) ：一种特殊的线性表，其 只答应在固定的一端举行插入和删除元素操纵 。举行数据插入和删除操纵的一端称为 栈顶 ，另一端称为栈底。栈中的数据元素服从 后进先出 LIFO （ Last In First Out ）的原则。 压栈：栈的插入操纵叫做进栈 / 压栈 / 入栈， 入数据在栈顶 。 出栈：栈的删除操纵叫做出栈。 出数据在栈顶 。 https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvN2RlZTJiOTQwOGRlNDEzZGJlY2NlOTRhMDNlYzYwZWIucG5n 来道例题：
1. 若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不大概的一个出栈序列是（） A: 1,4,3,2 B: 2,3,4,1 C: 3,1,4,2 D: 3,4,2,1 注意： 进栈过程中可以出栈，答案选C
2、 栈的使用
Stack是Java提供的类，此中包罗了可以对栈举行一系列操纵的常见方法
栈的方法：
方法功能Stack （ ）构造一个空的栈E push ( E e）将e入栈,并返回eE pop ( )将栈顶元素出栈并返回E peek ( )获取栈顶元素int size ( )获取栈中有效元素个数boolean empty ( )检测栈是否为空
代码示例：
public static void main(String[] args) {
Stack<Integer> stack=new Stack<>();
stack.push(40);
stack.push(30);
stack.push(20);
stack.push(10);
System.out.println(stack);//
System.out.println(stack.search(new Integer(40)));//返回40下标4
System.out.println(stack.pop());//删除栈顶元素10并返回
System.out.println(stack.peek());//获取栈顶元素 20
}3、 栈的模仿实现
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvYjhhYzk3Y2IxZGQ5NDcwMDhmODczMjgzNTYxMGQ5ZDkucG5n 从上图中可以看到， Stack 继续了 Vector ， Vector 和 ArrayList 类似，都是动态的序次表，差异的是 Vector 是线程安全的。 代码实例：
public class Mystack {
int []elem;
int size;
public Mystack(){
elem=new int;
}
public int push(int e){
ensureCapacity();
elem = e;
return e;
}
public int peek(){
if(empty()){
throw new RuntimeException("栈为空，无法获取栈顶元素");
}
return elem;
}
public boolean empty(){
return 0 == size;
}
public int pop(){
int e = peek();
size--;
return e;
}
//扩容
private void ensureCapacity(){
if(size==elem.length)
elem= Arrays.copyOf(elem,size*2);
}
} 相干概念区分
栈、假造机栈、函数栈帧；这里对这几个概念举行一个浅浅的区分
[*]栈是一种数据布局
[*]假造机栈是JVM的一块内存
[*]函数栈帧是调用方法时为方法开辟的一块内存
队列
1、 概念
队列(Queue)：只答应在一端举行插入数据操纵，在另一端举行删除数据操纵的特殊线性表，队列具有 先辈先出 FIFO(First In First Out) 入队列：举行插入操纵的一端称为 队尾（ Tail/Rear ） 出队列：举行删除操纵的一端称为 队头 （ Head/Front ） https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvYjFjNWE5ZDM5MDg3NGQ5OThmMzk3MmE5NDI0YTI4OTEucG5n 2、队列的使用
在 Java 中， Queue 是个接口，底层是通过链表实现 的。https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvYmFkYjAwMzA4Y2ZjNDE5MjhjNjk1NWQyYzdiOTA0YmMuanBlZw==
Queue方法：
方法功能boolean offer (E e )入队列E poll ( )出队列peek ( )获取队头元素int size ( )获取队列有效元素个数boolean isEmpty( )检测队列是否为空 注意： Queue是个接口，在实例化时必须实例化LinkedList的对象，由于LinkedList实现了Queue接口。 代码实例： public static void main(String[] args) {
Queue<Integer> q = new LinkedList<>();
q.offer(1);
q.offer(2);
q.offer(3);
q.offer(4);
q.offer(5); // 从队尾入队列
System.out.println(q.size());
System.out.println(q.peek()); // 获取队头元素
q.poll();
System.out.println(q.poll()); // 从队头出队列，并将删除的元素返回
if(q.isEmpty()){
System.out.println("队列空");
}else{
System.out.println(q.size());
}
}3、队列模仿实现
队列中既然可以存储元素，那底层肯定要有可以或许生存元素的空间，通过前面线性表的学习相识到常见的空间范例有两种：序次布局 和 链式布局。列的实现使用一样寻常使用链式布局 public class MyQueue {
// 双向链表节点
public static class ListNode{
ListNode next;
ListNode prev;
int value;
ListNode(int value){
this.value = value;
}
}
ListNode first; // 队头
ListNode last; // 队尾
int size = 0;
// 入队列---向双向链表位置插入新节点
public void offer(int e){
ListNode newNode = new ListNode(e);
if(first == null){
first = newNode;
// last = newNode;
}else{
last.next = newNode;
newNode.prev = last;
// last = newNode;
}
last = newNode;
size++;
}
// 出队列---将双向链表第一个节点删除掉
public int poll(){
// 1. 队列为空
// 2. 队列中只有一个元素----链表中只有一个节点---直接删除
// 3. 队列中有多个元素---链表中有多个节点----将第一个节点删除
int value = 0;
if(first == null){
return -1;
}else if(first == last){
last = null;
first = null;
}else{
value = first.value;
first = first.next;
first.prev.next = null;
first.prev = null;
}
--size;
return value;
}
// 获取队头元素---获取链表中第一个节点的值域
public int peek(){
if(first == null){
return -1;
}
return first.value;
}
public int size() {
return size;
}
public boolean isEmpty(){
return first == null;
}
} 4、 循环队列
现实中我们偶然还会使用一种队列叫循环队列。如操纵体系课程解说生产者消耗者模子时可以就会使用循环队列。 环形队列通常使用数组实现。 为什么要有循环列队
用数组实现队列时：
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvZmM2NDM2OTBiNjVjNDVlNGIyMzg4NzI4OGU1YzVjMTAucG5n
用循环队列可以办理空间浪费的标题
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvOGViNTE1ZjVkNzRjNDhlMWFiZmIwNDBkYWVhMWE5ZmYucG5n
怎样用代码将数组是变为循环队列
rear向后移动公式
rear =（ rear+1）% array.length
rear向前移动公式
rear =（ rear-1+ array.length）% array.length
怎样区分空与满
在未放元素时，rear=front，随着元素放满，rear与front相遇时，代表队列已满。那么，怎样用代码区分队列为空与队列为满呢
有三种办法：
[*]计数器：通过添加 count 属性记载
[*]使用标记，界说boolean 范例元素
[*]生存一个位置不放元素（判定rear下一个是否为 front ）
小搭档可以做道题练练手
操持循环队列
5、双端队列
双端队列（deque）是指答应两端都可以举行入队和出队操纵的队列， deque是“double ended queue”的简称。 那就分析元素可以从队头出队和入队，也可以从队尾出队和入队 Deque是一个接口，使用时必须创建LinkedList的对象。 https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvNDI2NjMwMzIwYmYzNDY2MWJkNWQxNjk1YTkyZDEzZmIuanBlZw== 在现实工程中，使用 Deque 接口是比力多的，栈和队列均可以使用该接口 Deque<Integer> stack = new ArrayDeque<>();// 双端队列的线性实现 Deque<Integer> queue = new LinkedList<>();// 双端队列的链式实现 本篇文章到此竣事，接下来会对二叉树相干知识举行解说
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！qidao123.com:ToB企服之家，中国第一个企服评测及软件市场,开放入驻,技术点评得现金
页:
[1]