目录

• 栈
• 栈的模拟实现
• • 栈的顺序实现
  • • 接口实现
    • 成员变量
    • 默认构造方法
    • 入栈
    • 判满
    • 获取栈元素个数
    • 出栈
    • 获取栈顶元素 但是不删除
    • 判空
  • 栈的链式实现
  • • 接口实现
    • 内部类
    • 入栈
    • 出栈
    • 判空
    • 获取栈顶元素 但是不删除
    • 获取栈元素个数
• Java中的Stack
• • 实现的接口
  • 常用方法
• 栈练习

栈

栈是限定仅在表尾进行插入和删除操作的线性表，一种**先进后出**的数据结构。

栈顶： 允许插入和删除的一端。
栈底：不允许插入和删除的一端。
压栈：栈的插入操作。
出栈：栈的删除操作。

栈的模拟实现

栈的底层可以是顺序表，可以是链表实现。

栈的顺序实现

栈的顺序实现就是使用顺序表为底层实现。

接口实现

实现的接口（成员方法）如下：
顺序表可以多实现一个判满接口。

public class MyStack { 	//默认构造方法 	public MyStack() {} 	//入栈     public void push(int val) {} 	//判满     public boolean isFull() { } 	//出栈     public int pop() {}     //获取栈顶元素 但是不删除     public int peek() { }      //获取栈元素个数     public int size(){}      //判空     public boolean isEmpty() { }        } 

成员变量

我们使用一个数组，和一个int类型usedSize来表示栈中元素个数。

	public int[] elem;     public int usedSize; 

默认构造方法

在构造方法中我们将数组申请10个int空间。

 public MyStack() {         this.elem = new int[10];     } 

入栈

注意事项：

• 先判断栈是否是满的，满的就要先扩容。
• 入栈时usedSize也要跟着加1。

public void push(int val) {         if (isFull()) {             this.elem = Arrays.copyOf(elem, 2 * elem.length);         }         elem[usedSize++] = val;     } 

判满

直接判断usedSize是否等于数组长度。

public boolean isFull() {         return usedSize == elem.length;     } 

获取栈元素个数

直接返回usedSize即可。

    public int size(){     	return usedSize；     }  

出栈

注意事项：

• 要先判断栈是不是空，是空抛一个异常。
• 栈不为空，返回数组最后一个元素，同时usedSize要减1。

  public int pop() throws IndexIllegalException{         try {             if (isEmpty()) {                 throw new IndexIllegalException("栈为空");             }         }catch (IndexIllegalException e){             e.printStackTrace();         }         return elem[--usedSize];     } 

获取栈顶元素 但是不删除

注意事项：

• 要先判断栈是不是空，是空抛一个异常。
• 栈不为空，返回数组最后一个元素，同时usedSize不动。

public int peek() throws IndexIllegalException{         try {             if (isEmpty()) {                 throw new IndexIllegalException("栈为空");             }         }catch (IndexIllegalException e){             e.printStackTrace();         }         return elem[usedSize - 1];     } 

判空

直接返回usedSize等不等于0。

public boolean isEmpty() {         return usedSize == 0;     } 

栈的链式实现

在实现栈前我们先思考使用什么样的链表来实现？
由于栈的特性是先入后出，如果使用单链表我们出栈时要拿到最后一个节点前一个节点，使复杂度为O(N)，所以我们使用双向链表。

接口实现

实现的接口如下：

public class MyStack { 	//入栈     public void push(int val) {} 	//出栈     public int pop() {}     //获取栈顶元素 但是不删除     public int peek() { }     //判空     public boolean isEmpty() { }            //获取栈元素个数     public int size(){}   } 

内部类

跟双向链表的内部类实现差不多。

static class ListNode{         public int val;         public ListNode prev;         public ListNode next;          public ListNode(int val) {             this.val = val;         }     }     public ListNode head;     public ListNode last; 

入栈

实现思路：

1. 先判断栈是否为空，空就头尾直接指向入栈节点。
2. 不为空就将尾节点的next指向入栈节点，入栈节点的prev指向尾节点，尾节点修改为入栈节点。

public void push(int val){ 	ListNode cur = new ListNode(val); 	if(isEmpty()){ 		head = last = cur; 		return; 	} 	last.next = cur; 	cur.prev = last; 	last = cur; } 

出栈

实现思路：

1. 先判断栈是否为空，栈为空抛异常。
2. 栈不为空，将尾节点记录下来，尾节点变为前一个节点，并将next置空。

public int pop() throws NullPointerException{ 	try{ 		if(isEmpty()){ 			throw new NullPointerException; 		} 	}catch(NullPointerException e){ 		 e.printStackTrace(); 	} 	ListNode cur = last; 	last = last.prev; 	last.next = null; 	return cur.val; } 

判空

直接返回头是否为空就行。

public boolean isEmpty(){ 	return head == null; } 

获取栈顶元素 但是不删除

实现思路：

1. 先判断栈是否为空，栈为空抛异常。
2. 栈不为空，返回尾节点。

public int peek(){ 	try{ 		if(isEmpty()){ 			throw new NullPointerException; 		} 	}catch(NullPointerException e){ 		 e.printStackTrace(); 	} 	return last.val; } 

获取栈元素个数

直接循环遍历即可。

    public int size(){     	ListNode cur = head;     	int size = 0; 		while(cur != null){ 			cur = cur.next; 			size++; 		} 		return size; 	}  

Java中的Stack

实现的接口

接口说明：

• 继承了Vector，Vector和ArrayList类似，都是动态的顺序表，不同的是Vector是线程安全的。
• 实现了Cloneable接口，可克隆。
• 实现了RandomAccess接口，支持随机访问。
• Serializable接口表示支持序列化。

常用方法

提供的常用方法如下：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-FhLLHxMB-1720973208640)(https://i-blog.csdnimg.cn/direct/f414e542bd80432095def0a48671fd3f.png)]

栈练习

有效的括号

逆波兰表达式求值

栈的压入 弹出序列

最小栈