目录
栈LIFO:
队列:
循环队列:
双端队列:
线性表:一次保存单个同类型元素,多个元素之间逻辑上连续
数组,链表,栈,队列,字符串(内部是char[])
栈LIFO:栈和队列是 *** 作受限的线性表
数组,链表既可以头插也可以删除,也能在尾部插入删除
"栈和队列"只能在一端插入元素和删除元素
只能从一端插入元素,也只能从这一端取出元素(栈顶)
栈的特点:先进后出,后进先出
将12345依次添加到栈中
最先添加的元素就在栈的最低端,最后添加的元素在最顶端
添加元素就在栈的最顶端
取出栈元素:54321
栈在现实生活中的应用:
1.undo撤销 *** 作:
在任何一个编辑器中输错了一个内容按CTRL+Z就返回到了上次输入的内容
在任何一个浏览器点击按钮就能返回上次浏览的网页
*** 作系统栈:程序在执行的过程中,A函数调用B函数,从B函数调用C函数,返回执行时
如何得知从哪开始继续执行的哪,背后就是栈结构
栈会记录执行的行数,执行完毕会d栈,回到行数继续向下执行.
基于动态数组实现的顺序栈:
//基于动态数组实现的顺序栈
public class MyStack {
//记录当前栈中的元素个数
private int size ;
//实际存储数据的动态数组,此时在栈中只能在数组末尾添加和删除元素
private List list = new ArrayList<>();
//向栈中添加元素
public void push(E val){
list.add(val);
size++;
}
//d出栈顶元素,返回当前元素值
public E pop(){
if(isEmpty()){
throw new NoSuchElementException("stack is empty!cannot peek");
}
E val = list.remove(size - 1 );
size--;
return val;
}
//查看当前栈顶元素,不d出
public E peek(){
if(isEmpty()){
throw new NoSuchElementException("stack is empty!cannot peek");
}
return list.get(size - 1);
}
public String toString(){
StringBuilder sb = new StringBuilder();
sb.append("[");
for (int i = 0; i < size; i++) {
sb.append(list.get(i));
if(i != size-1){
sb.append(",");
}
}
sb.append("] top");
return sb.toString();
}
//判断栈是否为空
private boolean isEmpty(){
return size == 0;
}
} LeetCode20:判断当前字符串是否是满足条件正确闭合的字符串
思路:首先我们要把字符串转换为字符数组,遍历字符串,使用charAt()取出元素转换为char,如果取出的第一个元素为'('或'{'或'['就把它入栈,如果为,},],),没有左括号那么栈就为空返回false即可,不为空就要取出栈顶元素并比较如果不同就返回false,如果左括号比右括号多,最后就要在判一次空,return stack.isEmpty();
//判断当前字符串是否是一个满足条件正确闭合的字符串
public class Num20 {
public boolean isValid(String s) {
Stack stack = new Stack();
for (int i = 0; i LeetCode155:双栈思路
//双栈实现最小栈
public class Num155 {
// s1永远保存实际元素
private Stack s1 = new Stack<>();
// s2栈顶永远保存当前数据的最小值
private Stack s2 = new Stack<>();
public void push(int val) {
s1.push(val);
if (s2.isEmpty()) {
s2.push(val);
}else {
int peek = s2.peek();
s2.push(Math.min(val,peek));
}
}
public void pop() {
s1.pop();
s2.pop();
}
public int top() {
return s1.peek();
}
public int getMin() {
return s2.peek();
}
} 给大家推荐两本好书,有时间可以康康
其实栈和队列是一码事,都是对线性表的一端进行插入和删除.
因此,栈和队列可以相互转换
队列:FIFO,先进先出的数据结构,元素从''队尾"添加到队列中,元素从"队首"出队列(元素的出队顺序和入队顺序保持一致)
队列也有基于数组实现的队列和基于链表实现的队列
出队 *** 作只能在队列的头部进行,若使用数组的方法,每次出队一个元素就要搬移剩下的所有元素向前移动一个单位.
使用链表的方案更加适合队列的结构
出队列:删除头节点
添加元素:在链表的尾部添加
基于链表实现的队列:
class Node{
E val;
Node next;
public Node(E val) {
this.val = val;
}
}
//基于链表实现的普通队列
public class LinkedQueue implements Queue{
//记录元素有效个数
private int size;
//首元素
private Node head;
//尾节点
Node tial ;
//入队
@Override
public void offer(E val) {
Node node = new Node<>(val);
if(head == null){
head = tial = node;
}else {
tial.next = node;
tial = node;
}
size++;
}
//删除队首元素
@Override
public E poll() {
if(isEmpty()){
throw new NoSuchElementException("空元素");
}
E val = head.val;
Node node = head;
head = head.next;
node.next = node = null;
size--;
return val;
}
//查看队首第一个元素
@Override
public E peek() {
if(isEmpty()){
throw new NoSuchElementException("空数组");
}
return head.val;
}
@Override
public boolean isEmpty() {
return size == 0 ;
}
public String toString(){
StringBuilder sb = new StringBuilder();
sb.append("[");
for (Node x = head; x != null; x = x.next) {
sb.append(x.val);
if(x.next != null){
sb.append(",");
}
}
sb.append("]");
return sb.toString();
}
}
用队列实现栈:
//单队列实现栈
public class Num225 {
Queue queue = new LinkedList<>();
public void push(int x) {
//记录当前元素的个数
int size = queue.size();
//新元素之间入栈
queue.offer(x);
// 3.将原先的前n个元素依次出队再入队，新元素就变成了队首元素
for (int i = 0; i < size; i++) {
queue.offer(queue.poll());
}
}
public int pop() {
return queue.poll();
}
public int top() {
return queue.peek();
}
public boolean empty() {
return queue.isEmpty();
}
} 使用双栈实现队列:
public class Num232_StackImplQueue {
// s1永远是保存元素的栈，就对应队列
private Stack s1 = new Stack<>();
// s2作为辅助，s1的栈顶元素就会d出压入s2的栈底 => 交换顺序
private Stack s2 = new Stack<>();
public void push(int x) {
// 1.先让s1的所有元素d出压入s2中，交换先后顺序
while (!s1.isEmpty()) {
s2.push(s1.pop());
}
// 2.s1为空，新元素直接入s1，就变为了栈底元素，就是队尾
s1.push(x);
// 3.再把s2中的所有元素依次d回s1
while (!s2.isEmpty()) {
s1.push(s2.pop());
}
}
public int pop() {
return s1.pop();
}
public int peek() {
return s1.peek();
}
public boolean empty() {
return s1.isEmpty();
}
} 是使用长度固定的数组来实现的,数组在实现队列时,若从数组头部删除元素需要频繁移动后面的元素,效率比较低.
思路: 出队和入队 *** 作使用两个引用,一个head(数组头部),一个tial(数组尾部),添加元素在数组尾部添加.数组[head...tial)之间的元素是循环队列的有效元素,head永远指向循环队列的第一个元素,tail永远指向循环队列有效元素的最后一个位置.
1.数组为下图情况的话,数组为null或者数组已满都是head == tail
此时,数组为满就没办法判断!!!因为数组为满也是head == tail
解决:我们可以在数组长度在加一个空间,判断队列是否已满
tail = (tail +1)%n
解释:tail为索引,n为长度,head和tail走到数组最后一个索引位置,下一次要返回数组头部就必须使用+n对数组取模
2.若此时(tail + 1) % n == headl; 我们就认为此时循环队列以满
3.head和tail的移动不能简单的+1,要使用去摸 *** 作,取数组长度
实现:
//基于整形的循环队列
public class LoopQueue implements Queue{
//整形数组
private Integer[] data;
//指向队首元素
private int head;
//指向队尾元素的下一个索引
private int tail;
public LoopQueue(Integer size){
// 因为循环队列中要浪费一个空间判断是否已满
data = new Integer[size + 1];
}
@Override
public void offer(Integer val) {
if (isFull()) {
throw new ArrayIndexOutOfBoundsException("loopQueue is full,cannot offer");
}
data[tail] = val;
tail = (tail + 1)%data.length;
}
private boolean isFull() {
return (tail + 1 ) % data.length == head;
}
@Override
public Integer poll() {
if (isEmpty()) {
throw new NoSuchElementException("loopQueue is empty!cannot poll");
}
//移动队首元素
int val = data[head];
head = (head + 1)% data.length;
return val;
}
@Override
public Integer peek() {
if(isEmpty()){
throw new NoSuchElementException("loopQueue is empty!cannot peek");
}
return data[head];
}
@Override
public boolean isEmpty() {
return head == tail;
}
public String toString(){
StringBuilder sb = new StringBuilder();
sb.append("[");
int lastIndex = tail == 0 ? data.length - 1 : tail - 1;
for (int i = head; i != tail ; ) {
sb.append(data[i]);
if(i != lastIndex){
sb.append(",");
}
i = (i +1) % data.length;
}
sb.append("]");
return sb.toString();
}
} public static void main(String[] args) {
Queue queue = new LoopQueue(4);
queue.offer(1);
queue.offer(2);
queue.offer(3);
System.out.println(queue);[1,2,3]
System.out.println(queue.peek());1
System.out.println(queue.poll());1
System.out.println(queue);[2,3]
} Deque->Queue的子接口
这个队列即可以尾插,头出
也可以头插,尾出
推荐大家无论使用栈还是接口,统一使用双端队列接口
不推荐使用Stack这个类,效率低,都是同步 *** 作
双端队列常用子类就是LinkedList
public static void main(String[] args) {
//现在需要一个栈
Deque stack = new LinkedList<>();
stack.push(1);
stack.pop();
//现在需要一个队列
Deque queue = new LinkedList<>();
queue.offer(2);
queue.peek();
}
Scanner引用的特殊说明:
double price = scanner.nextDouble();//输入一个小数然后按回车结束
本次输入:10.0\n
这个\n是本次获取小数的结束标注
nextLine();\\一次读取一行输入,也是以\n为结束标记.
在每次小数输入结束后,在单独使用一次nextLine吃掉这个换行符即可
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）