- 一、栈
- 1.1栈的概念
- 1.2栈的使用
- 1.3栈的模拟实现
- 1.4栈的经典题目
- 1.5栈、虚拟机栈、栈帧
- 二、队列
- 2.1队列的概念
- 2.2队列的使用
- 2.3队列的模拟实现
- 2.3.1使用单链表实现模拟实现队列
- 2.3.2使用数组实现循环队列
- 2.4双端队列
- 2.5队列经典面试题
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据在栈顶。
public static void main(String[] args) {
Stack s = new Stack();
s.push(1);
s.push(2);
s.push(3);
s.push(4);
System.out.println(s.size());
System.out.println(s.peek());
s.pop();
System.out.println(s.pop());
if(s.empty()){
System.out.println("栈空");
}else{
System.out.println(s.size());
}
}
执行结果：
import java.util.Arrays;
public class MyStack {
int[] array;
int size;
public MyStack(){
this.array = new int[3];
}
public int push(int e){
ensureCapacity();
this.array[this.size++] = e;
return e;
}
public int pop(){
if(empty()){
throw new RuntimeException("栈为空，无法弹出栈顶元素");
}
int ret=this.array[this.size-1];
//this.arry[this.size-1]=null; 当栈中存储的数据类型是引用类型时，要将其置为null
this.size--;
return ret;
}
public int peek(){
if(empty()){
throw new RuntimeException("栈为空，无法获取栈顶元素");
}
return array[size-1];
}
public boolean empty(){
return 0 == this.size;
}
public int size(){
return this.size;
}
private void ensureCapacity(){
if(this.size == this.array.length){
this.array = Arrays.copyOf(array, size*2);
}
}
}
使用：
public class Test4 {
public static void main(String[] args) {
MyStack myStack=new MyStack();
myStack.push(1);
myStack.push(2);
myStack.push(3);
myStack.push(4);
int x= myStack.pop();
System.out.println(x);
x= myStack.pop();
System.out.println(x);
x= myStack.pop();
System.out.println(x);
x= myStack.peek();
System.out.println(x);
x= myStack.pop();
System.out.println(x);
}
}
执行结果：
（1）
答案：C
（2）使用栈逆序打印链表
源码：
Stacks = new Stack<>(); // 将链表中的结点保存在栈中 Node cur = head; while(null != cur){ s.push(cur); cur = cur.next; } // 将栈中的元素出栈 while(!s.empty()){ System.out.print(s.pop().val + " "); }
(3) 中缀表达式转后缀表达式
将中缀表达式转成后缀表达式的目的是什么呢？
便于使用栈来计算表达式的值
(4) 逆波兰表达式
OJ链接
思路：就是上面的使用栈求后缀表达式的值
源码：
public int evalRPN(String[] tokens) {
Stack stack=new Stack<>();
for (String str:tokens) {
if(str.equals("+")||str.equals("-")||str.equals("*")||str.equals("/")){
int s1=stack.pop();
int s2=stack.pop();
switch (str){
case "+":
stack.push(s2+s1);
break;
case "-":
stack.push(s2-s1);
break;
case "*":
stack.push(s2*s1);
break;
case "/":
stack.push(s2/s1);
break;
default:
break;
}
}else {
stack.push(Integer.parseInt(str));
}
}
return stack.pop();
}
(5) 有效的括号
OJ链接
源码：
public boolean isValid(String s) {
Stack stack=new Stack<>();
char[] str=s.toCharArray();
for(int i=0;i
if(str[i]=='('||str[i]=='{'||str[i]=='['){
stack.push(str[i]);
}else {
if(stack.empty()){
return false;
}
char tmp=stack.peek();
if(str[i]==')'&&tmp=='('||str[i]=='}'&&tmp=='{'||str[i]==']'&&tmp=='['){
stack.pop();
}else {
return false;
}
}
}
if(!stack.empty()){
return false;
}
return true;
}
(6)栈的压入、弹出序列
OJ链接
源码：
public boolean IsPopOrder(int [] pushA,int [] popA) {
if(pushA.length==0||popA.length==0){
return false;
}
Stack stack=new Stack<>();
int j=0;
for (int i = 0; i < pushA.length; i++) {
stack.push(pushA[i]);
while(!stack.empty()&&stack.peek()==popA[j]&&j< popA.length){
stack.pop();
j++;
}
}
return stack.empty();
}
【注意】：
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则
虚拟机栈： 主管Java程序的运行，它保存方法的局部变量（8 种基本数据类型、对象的引用地址）、部分结果，并参与方法的调用和返回。
二、队列 2.1队列的概念栈帧：函数调用时，系统为其分配的一块空间
队列：
2.2队列的使用只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)
入队列：进行插入操作的一端称为队尾（Tail/Rear）
出队列：进行删除操作的一端称为队头 （Head/Front）
在Java中，Queue只是一个接口，实现这个接口的类是LinkList，所以其底层是一个双向链表
Queue 接口中的方法
add ：入队列
offer：入队列
remove：出队列
poll：出队列
peek：获取队头元素
【注意】：
2.3队列的模拟实现 2.3.1使用单链表实现模拟实现队列
Queue是个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口。
LinkedList不仅可以当作链表来使用，也可以当作队列，又因为它实现了Deque(双端队列)，所以还可以当作栈来使用。
使用单向链表实现队列：
增加一个指向链表结尾的引用last
从链表的结尾入队，链表的头出队 （入队和出队的时间复杂度都是O(1)）
为什么不是从头入队，从尾巴出队呢？？
这样的话，出队的时间复杂度是O(N)
public class MyLinkedList {
class Node{
int val;
public Node next;
public Node(int val) {
this.val = val;
}
}
public Node head;
public Node last;
public int usedSize;//队列中元素个数
public void offer(int val){
Node node=new Node(val);
if(this.head==null){
this.head=this.last=node;
}else{
this.last.next=node;
this.last=node;
}
this.usedSize++;
}
public int poll(){
if(empty()){
throw new RuntimeException("队列为空，不能出队");
}
int val= this.head.val;
this.head=this.head.next;
//如果队列中只有一个节点，将last也要置为null;
if(this.head==null){
this.last=null;
}
this.usedSize--;
return val;
}
public int peek(){
if(empty()){
throw new RuntimeException("队列为空,无法获取队头元素");
}
int val= this.head.val;
return val;
}
public int size(){
return this.usedSize;
}
public boolean empty(){
return this.usedSize==0;
}
}
2.3.2使用数组实现循环队列
数组下标循环的技巧：
- 下标最后再往后(offset 小于 array.length): index = (index + offset) % array.length
- 下标最前再往前(offset 小于 array.length): index = (index + array.length - offset) % array.length
对于数组实现队列时，还需要解决下面这个问题：
（1）通过增加usedSize属性记录数据的个数
每增加一个数据usedSize++
每删除一个数据usedSize–
（2）空一个位置
该方法相对于第一种方法，浪费了一个空间
(3) 使用标记
下面使用空一格的方式实现循环对垒
循环队列的属性：
private int[] elem;
public int front;//标加队列的头
public int rear;//标记队列的尾
构造方法：用来初始化数组
public MyCircularQueue(int k) {
elem=new int[k];
}
普通方法：
（1）判断循环队列是否满
public boolean isFull() {
if((rear+1)% elem.length==front){
return true;
}
return false;
}
（2）入队
在入队之前需要判断队列是否满
将数据放在rear下标对应的位置
rear=(rear+1)%elem.length
【注意】:
不能是rear++，否则会发生数组越界
public boolean enQueue(int value) {
if(isFull()){
return false;
}
this.elem[this.rear]=value;
this.rear=(this.rear+1)% elem.length;
return true;
}
(3)判断队列是否为空
public boolean isEmpty() {
if(this.front==this.rear){
return true;
}
return false;
}
（4）出队
在出队前需要判断队列是否为空
front=(front+1)%elem.length
public boolean deQueue() {
if(isEmpty()){
return false;
}
this.front=(this.front+1)%this.elem.length;
return true;
}
(5)获取队头元素
public int Front() {
if(isEmpty()){
return -1 ;
}
return this.elem[front];
}
（6）获取队尾元素
当rear==0时需做特殊处理，返回elem.length-1位置的值
public int Rear() {
if(isEmpty()){
return -1 ;
}
int index=(rear==0)?this.elem.length-1:rear-1;
return this.elem[index];
}
2.4双端队列
双端队列（deque）是指允许两端都可以进行入队和出队操作的队列，deque 是 “double ended queue” 的简称。
那就说明元素可以从队头出队和入队，也可以从队尾出队和入队。
Deque是一个接口，使用时必须创建LinkedList的对象
(1) 用队列实现栈
OJ链接
思路：
源码：
class MyStack {
private Queue q1;
private Queue q2;
public MyStack() {
q1=new LinkedList<>();
q2=new LinkedList<>();
}
public void push(int x) {
if(!q1.isEmpty()){
q1.offer(x);
}else if(!q2.isEmpty()){
q2.offer(x);
}else{
q1.offer(x);
}
}
public int pop() {
if(empty()){
return -1;
}
if(!q1.isEmpty()){
int size=q1.size();
for(int i=0;i
q2.offer(q1.poll());
}
return q1.poll();
}else {
int size=q2.size();
for(int i=0;i
q1.offer(q2.poll());
}
return q2.poll();
}
}
public int top() {
if(empty()){
return -1;
}
int tmp=-1;
if(!q1.isEmpty()){
int size=q1.size();
for(int i=0;i
tmp=q1.poll();
q2.offer(tmp);
}
return tmp;
}else {
int size=q2.size();
for(int i=0;i
tmp=q2.poll();
q1.offer(tmp);
}
return tmp;
}
}
public boolean empty() {
if(q1.isEmpty()&&q2.isEmpty()){
return true;
}
return false;
}
}
（2）用栈实现队列
OJ链接
思路：
源码：
import java.util.Stack;
class MyQueue {
private Stack s1;
private Stack s2;
public MyQueue() {
s1=new Stack<>();
s2=new Stack<>();
}
public void push(int x) {
s1.add(x);
}
public int pop() {
if(empty()){
return -1;
}
if(s2.isEmpty()){
while (!s1.isEmpty()){
s2.add(s1.pop());
}
}
return s2.pop();
}
public int peek() {
if(empty()){
return -1;
}
if(s2.isEmpty()){
while (!s1.isEmpty()){
s2.add(s1.pop());
}
}
return s2.peek();
}
public boolean empty() {
if(s1.isEmpty()&&s2.empty()){
return true;
}
return false;
}
}
(3)实现一个最小栈
OJ链接
源码：
import java.util.Stack;
class MinStack {
private Stack s1;
private Stack minStack;
public MinStack() {
s1=new Stack<>();
minStack=new Stack<>();
}
public void push(int val) {
s1.push(val);
if(minStack.isEmpty()){
minStack.push(val);
}else{
int cur=minStack.peek();
if(val<=cur){
minStack.push(val);
}
}
}
public void pop() {
if(s1.isEmpty()){
return ;
}
int cur=s1.peek();
s1.pop();
if(cur==minStack.peek()){
minStack.pop();
}
}
public int top() {
if(s1.isEmpty()){
return -1 ;
}
return s1.peek();
}
public int getMin() {
return minStack.peek();
}
}
