栈
解决实际问题：
- 表达式的求职和转换（中缀表达式转后缀表达式）
- 二叉树的遍历
- 深度优先搜索
概念：
- 栈（stack）
- 先入后出
- 只能在栈顶进top行操作，固定的一段是栈底Bottom
- 基本操作：
- 出栈 pop
- 入栈 push
使用数组模拟栈：
image-20200714204633025.png
实现思路：
- 使用数组来模拟栈
- 定义一个top，初始化为-1
- 入栈操作，加入数据 stack[top++] = data;
- 出栈操作 return stack[top--];
数组模拟栈（ArrayStack）
public class ArrayStack {
private int maxSize;
private int top;
private int[] stack;
public ArrayStack(int maxSize) {
this.maxSize = maxSize;
this.top = -1;
this.stack = new int[this.maxSize];
}
//判断栈是否为空
public boolean isEmpty(){
return top==-1;
}
//判断栈是否满了
public boolean isFull(){
return top == maxSize-1;
}
//入栈 push
public void push(int value){
if (isFull()) {//判断栈是否为满
System.out.println("栈已满");
return;
}
top++;
stack[top] = value;
}
//出栈 pop
public int pop(){
if (isEmpty()){
throw new RuntimeException("栈为空");
}
return stack[top--];
}
//遍历数组 从栈顶往栈底遍历数据
public void show(){
if (isEmpty()){
System.out.println("没有数据");
return;
}
for (int i = top; i >= 0; i--) {
System.out.printf("stack[%d] = %d \n",i,stack[i]);
}
}
}
课后练习：
1. 使用链表来模拟一个栈
image-20200714212351473.png
思路分析：LinkStack（链表栈）
-
双向链表十分容易实现栈
-
节点结构
- data
- next
- pre
-
是否为空：bottom == top
-
是否为满。链表不可能满的
-
入栈：newNode.pre = top; top.next = newNode;top = top.next;
-
出栈：Node value = top; top = top.pre; return value;
StackNode
public class StackNode {
private int data;
private StackNode pre;
private StackNode next;
public StackNode(int data) {
this.data = data;
}
public int getData() {
return data;
}
public StackNode getPre() {
return pre;
}
public StackNode getNext() {
return next;
}
public void setData(int data) {
this.data = data;
}
public void setPre(StackNode pre) {
this.pre = pre;
}
public void setNext(StackNode next) {
this.next = next;
}
@Override
public String toString() {
return "StackNode{" +
"data=" + data +
'}';
}
}
LinkedStack
public class LinkedStack {
private StackNode head = new StackNode(-1);
private StackNode top = head;
// 判断链表是否为空
public boolean isEmpty(){
return top == head;
}
// 入栈
public void push(StackNode node){
node.setPre(top);
top.setNext(node);
top = node;
}
// 出栈
public StackNode pop(){
if (isEmpty()){
throw new RuntimeException("栈空无数据");
}
StackNode value = top;
top = top.getPre();
return value;
}
//遍历
public void show(){
if (isEmpty()){
System.out.println("栈空无数据");
return;
}
StackNode cur = top;
while (true){
System.out.println(cur);
if (cur.getPre()==head){
break;
}
cur = cur.getPre();
}
}
}
2. 合并两个升序的单链表，合并之后的链表仍然升序。
思路分析：
- 选择使用单链表
- 节点结构
- data
- next
image.png
- 准备两个辅助指针 cur1 cur2
Linked tempLinked = new Linked();
Node temp = tempLinked.getHead();
Node cur1 = this.head;
Node cur2 = linked.getHead();
- 进行循环(结束条件是cur1!=null && cur2!=null)
- 每次循环都对比一下cur1.data 和 cur2.data，
- 值小的节点就连接到temp尾部（temp.next = cur1 & temp.next = cur2），
- cur1（cur2） 和 temp 后移一位。
while (cur1!=null && cur2!=null){
if (cur1.getData()<cur2.getData()){//小于
temp.setNext(cur1);
temp = temp.getNext();
cur1 = cur1.getNext();
}else if (cur1.getData() > cur2.getData()){//大于
temp.setNext(cur2);
temp = temp.getNext();
cur2 = cur2.getNext();
}else if (cur1.getData() == cur2.getData()){//等于
temp.setNext(cur1);
temp = temp.getNext();
temp.setNext(cur2);
temp = temp.getNext();
}
}
- cur1 和 cur2 其中有一个指向null 就将temp.next 指向另一个没有指向null的指针
if (cur1==null){//cur1
temp.setNext(cur2);
}
if (cur2==null){//cur3
temp.setNext(cur1);
}
Node 节点
public class Node {
private int data;
private Node next;
public Node(int data) {
this.data = data;
}
public int getData() {
return data;
}
public Node getNext() {
return next;
}
public void setData(int data) {
this.data = data;
}
public void setNext(Node next) {
this.next = next;
}
@Override
public String toString() {
return "Node{" +
"data=" + data +
'}';
}
}
Linked链表
public class Linked {
private Node head = new Node(0);
public Node getHead() {
return head;
}
//添加(默认添加到链表尾部)
public void add(Node node){
Node temp = head;
while (temp.getNext()!=null){
temp = temp.getNext();
}
temp.setNext(node);
}
//打印链表
public void show(){
if (head.getNext()==null){
System.out.println("链表无数据");
return;
}
Node temp = head.getNext();
while (temp != null){
System.out.println(temp);
temp = temp.getNext();
}
}
//合并另外一个链表 相同值优先本链表
public Linked combine(Linked linked){
Linked tempLinked = new Linked();
Node temp = tempLinked.getHead();
Node cur1 = this.head;
Node cur2 = linked.getHead();
if (cur1 == null && cur2==null){return null;}
cur1 = cur1.getNext();
cur2 = cur2.getNext();
while (cur1!=null && cur2!=null){
if (cur1.getData()<cur2.getData()){//小于
temp.setNext(cur1);
temp = temp.getNext();
cur1 = cur1.getNext();
}else if (cur1.getData() > cur2.getData()){//大于
temp.setNext(cur2);
temp = temp.getNext();
cur2 = cur2.getNext();
}else if (cur1.getData() == cur2.getData()){//等于
temp.setNext(cur1);
temp = temp.getNext();
temp.setNext(cur2);
temp = temp.getNext();
}
}
//cur 指到最后没有值的情况
if (cur1==null){//cur1
temp.setNext(cur2);
}
if (cur2==null){//cur3
temp.setNext(cur1);
}
return tempLinked;
}
}
测试：
public class test {
public static void main(String[] args) {
Linked linked1 = new Linked();
Linked linked2 = new Linked();
for (int i = 0; i < 10; i = i + 2) {
linked1.add(new Node(i));
linked2.add(new Node(i+1));
}
System.out.println("=======linked1========");
linked1.show();
System.out.println("=======linked2========");
linked2.show();
Linked combine = linked1.combine(linked2);
System.out.println("=======combine========");
combine.show();
}
}
结果：
image-20200714224039818.png
网友评论