目录
栈
1、概念
2、 栈的使用
3、 栈的模拟实现
相关概念区分
队列
1、 概念
2、队列的使用
3、队列模拟实现
4、 循环队列
为什么要有循环列队
如何区分空与满
5、双端队列 )
栈
1、概念
栈(Stack) :一种特殊的线性表,其 只允许在固定的一端进行插入和删除元素操作 。进行数据插入和删除操作的一端称为 栈顶 ,另一端称为栈底。栈中的数据元素遵守 后进先出 LIFO ( Last In First Out )的原则。
压栈:栈的插入操作叫做进栈 / 压栈 / 入栈, 入数据在栈顶 。
出栈:栈的删除操作叫做出栈。 出数据在栈顶 。
来道例题:
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入栈,并返回e |
E 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);//[40, 30, 20, 10]System.out.println(stack.search(new Integer(40)));//返回40下标4System.out.println(stack.pop());//删除栈顶元素10并返回System.out.println(stack.peek());//获取栈顶元素 20}
3、 栈的模拟实现
从上图中可以看到, Stack 继承了 Vector , Vector 和 ArrayList 类似,都是动态的顺序表,不同的是 Vector 是线程安全的。
代码实例:
public class Mystack {int []elem;int size;public Mystack(){elem=new int[10];}public int push(int e){ensureCapacity();elem[size++] = e;return e;}public int peek(){if(empty()){throw new RuntimeException("栈为空,无法获取栈顶元素");}return elem[size-1];}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 )
2、队列的使用
在 Java 中, Queue 是个接口,底层是通过链表实现 的。
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、 循环队列
实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。 环形队列通常使用数组实现。
为什么要有循环列队
用数组实现队列时:
用循环队列可以解决空间浪费的问题
如何用代码将数组是变为循环队列
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的对象。
在实际工程中,使用 Deque 接口是比较多的,栈和队列均可以使用该接口
Deque<Integer> stack = new ArrayDeque<>();// 双端队列的线性实现Deque<Integer> queue = new LinkedList<>();// 双端队列的链式实现
本篇文章到此结束,接下来会对二叉树相关知识进行讲解