目录
栈和队列的概念
栈：具有特殊限制的线性表，压栈和出栈操作只会在栈顶发生。 ??????????????????????
队列：有特殊限制的线性表，只可以在表的前端进行删除操作，表的后端进行插入操作。
栈：先进后出（搭积木：最上方插入和删除）
队列：先进先出?表头删除，表尾插入（排队买饭）
栈
栈：具有特殊限制的线性表，删除和插入操作只会在一端发生
表尾称为栈顶，表头称为栈底。
插入一个元素到表尾，称为压栈，删除一个元素称为出栈。
一对一的逻辑结构，存储结构：链式和顺序式
java中栈的方法
构造方法?
?Stack继承了父类Vector，实例化子类对象时调用了子类的构造方法，子类的构造方法默认调用父类没有参数的构造方法，在父类Vector无参数的构造方法中通过this关键字调用Vector中一个参数为int类型的构造方法?
?通过this关键字的调用，最终实现的是Vector类（int，int）类型的构造方法
?总结：当创建Stack对象时，JVM底层创建时，栈数组的初始空间默认为10
创建Vector对象时，如果没有传入大小，JVM底层处理空间为10
如果传入了大小，数组空间为传入大小
?push（）---元素压栈
public static void main(String[] args) {
Stack<Integer> stack = new Stack();
stack.push(1);//元素压栈
System.out.println(stack);
System.out.println(stack.peek());//弹出元素，但是不删除（只获取栈顶元素）
System.out.println(stack);
stack.pop();//元素出栈
System.out.println(stack);
}
?总结：如果初始化时，没有规定数组的扩容大小或者规定的扩容大小<=0，那么默认2倍扩容
如果规定的扩容大小>0,那么数组每次扩容长度为规定长度
顺序栈的模拟实现
class Mystack {
private int[] elem;
private int sz;//数组大小
private int usedsz;//数组占用大小
public Mystack(int sz) {
InitElem(sz);
this.sz = sz;
usedsz = 0;
}
public Mystack() {
this(10);
}
public void InitElem(int sz) {
if (sz <= 0)
throw new RuntimeException();
else {
this.elem = new int[sz];
}
}
public void Push(int x) {
ensureCapacity();
elem[usedsz++] = x;
}
public void ensureCapacity() {
if (usedsz == sz) {//数组满了
sz += sz;
}
elem = Arrays.copyOf(elem, sz);
}
public void print() {
for (int i = 0; i < usedsz; i++) {
System.out.print(elem[i] + " ");
}
System.out.println();
}
public boolean isEmpty(){
if(usedsz==0)
return true;
return false;
}
public int peek(){//获取栈顶元素
if(isEmpty()){//栈空
throw new RuntimeException();
}else{
return elem[usedsz-1];
}
}
public void pop(){//删除元素
if(isEmpty()){//栈空
throw new RuntimeException();
}else{
elem[--usedsz]=0;
}
}
@Override
public String toString() {
return "Mystack{" +
"elem=" + Arrays.toString(elem) +
'}';
}
}
public class MyArrayStack {
public static void main(String[] args) {
Mystack stack = new Mystack();
stack.Push(1);
System.out.println(stack);
System.out.println(stack.isEmpty());
stack.pop();
System.out.println(stack.isEmpty());
stack.print();
System.out.println(stack);
System.out.println(stack.peek());
stack.print();
System.out.println(stack);
}
}
链栈的模拟实现
如果使用单链表---头插法和尾插法
头插法：压栈和出栈的时间复杂度 o（1)
尾插法：使用尾结点可以将压栈的时间复杂度控制在o（1），但是出栈时间复杂度O（n）（找到前驱节点）
可以使用双向链表
class LinkNode {
int val;
LinkNode next;
LinkNode prev;
public LinkNode(int val, LinkNode prev, LinkNode next) {
this.val = val;
this.next = next;
this.prev = prev;
}
}
class Stack{
private LinkNode head=null;
private LinkNode tail=null;
public void push(int x){
if(head==null){
LinkNode newnode =new LinkNode(x,null,null);
head=newnode;tail=newnode;
}else{
LinkNode newnode =new LinkNode(x,tail,null);
tail.next=newnode;
tail=newnode;
}
}
public void pop(){
if(head==null)
throw new RuntimeException("栈空");
else if(head.next==null){//有一个元素
tail=head=null;
}
else{
tail.prev.next=null;
}
}
public int peek(){
if(head==null)
throw new RuntimeException("栈空");
else
return tail.val;
}
public void print(){
LinkNode p=head;
while(p!=null){
System.out.print(p.val+" ");
p=p.next;
}
System.out.println();
}
}
public class MyLinkedStack {
public static void main(String[] args) {
Stack stack=new Stack();
stack.push(1);
stack.push(4);
stack.push(1);
stack.print();
// System.out.println(stack.peek());
//stack.print();
stack.pop();
stack.print();
}
}
判断出栈顺序
比如有六个元素6，5，4，3，2，1的顺序进栈，问下列哪一个不是合法的出栈序列？（ ）。
A? 543612? B 453126? C 346521?? D? 234156
牛客--- JZ31?栈的压入、弹出序列
import java.util.*;
public class Solution {
public static boolean IsPopOrder(int [] pushA,int [] popA) {
Stack<Integer> stack = new Stack<>();
int j = 0;
for (int i = 0; i < pushA.length; i++) {
stack.push(pushA[i]);
while (!stack.isEmpty()&&j<pushA.length&&stack.peek() == popA[j]) {//找到了第一个弹出元素
stack.pop();
j++;
}
}
if(stack.isEmpty())
return true;
return false;
}
}?后缀中缀表达式
leetcode---150. 逆波兰表达式求值
借用栈将后缀表达式转化为中缀表达式
class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack=new Stack();
for (int i = 0; i < tokens.length; i++) {
if(ischaracter(tokens[i])==false){
stack.push(Integer.parseInt(tokens[i]));
}else{
int num2=stack.pop();
int num1=stack.pop();
switch(tokens[i]){
case "+":stack.push(num1+num2);break;
case "-":stack.push(num1-num2);break;
case "*":stack.push(num1*num2);break;
case "/":stack.push(num1/num2);break;
}
}
}
return stack.pop();
}
public boolean ischaracter(String s){
if(s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/"))
return true;
return false;
}
}leetcode---20. 有效的括号
class Solution {
public boolean isValid(String s) {
Stack <Character> stack=new Stack<>();
for (int i = 0; i <s.length() ; i++) {
char ch=s.charAt(i);//获取字符
if(ch=='('||ch=='{'||ch=='[')
stack.push(ch);//左括号入栈
else{
if(stack.isEmpty())
return false;
char a= stack.peek();
if(ch==')'&&a=='('||ch=='}'&&a=='{'||ch==']'&&a=='[')
stack.pop();
else
return false;
}
}
if(stack.isEmpty())
return true;
return false;
}
}