【数据结构】Java实现栈

目录

1. 概念

2. 栈的使用 

3. 自己动手实现栈（使用动态数组实现栈） 

1. 创建一个MyStack类

2. push入栈

3. pop出栈

4. 查看栈顶元素

5. 判断栈是否为空与获取栈长

6. toString方法

4. 整体实现

4.1 MyStack类

4.2 Test类

4.3 测试结果

---

1. 概念

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈 顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据在栈顶。

2. 栈的使用 

public static void main(String[] args) {Stack<Integer> stack = new Stack<>();
//        将e入栈，并返回estack.push(1);stack.push(2);stack.push(3);stack.push(4);stack.push(5);
//        将栈顶元素出栈并返回System.out.println(stack.pop());
//        获取栈顶元素System.out.println(stack.peek());
//        检测栈是否为空System.out.println(stack.empty());
//        获取栈中有效元素个数System.out.println(stack.size());System.out.println(stack);}

3. 自己动手实现栈（使用动态数组实现栈） 

1. 创建一个MyStack类

思路图：

import java.util.Arrays;
import java.util.NoSuchElementException;
//使用泛型
public class MyStack<E> {private Object[] data;private int size;public MyStack(int capacity){this.data = new Object[capacity];}public MyStack(){this.data = new Object[10];}}

2. push入栈

public E push(E val){data[size ++] = val;if(size == data.length){data = Arrays.copyOf(data,data.length<<1);}return val;}

3. pop出栈

public E pop(){if (isEmpty()){throw new NoSuchElementException("stack is empy,cannot pop!");}E oldVal = (E)data[size - 1];size --;return oldVal;}

4. 查看栈顶元素

public E peek(){if (isEmpty()){throw new NoSuchElementException("stack is empy,cannot peek!");}return (E)data[size - 1];}

5. 判断栈是否为空与获取栈长

public boolean isEmpty() {return size == 0;}public int size(){return size;}

6. toString方法

public String toString() {StringBuilder sb = new StringBuilder();sb.append("bottom [");for (int i = 0; i < size; i++) {sb.append(data[i]);if(i < size - 1){sb.append(",");}}sb.append("] top");return sb.toString();}

4. 整体实现

4.1 MyStack类

package seqlist.stack_queue;import java.util.Arrays;
import java.util.NoSuchElementException;public class MyStack<E> {private Object[] data;private int size;public MyStack(int capacity){this.data = new Object[capacity];}public MyStack(){this.data = new Object[10];}public E push(E val){data[size ++] = val;if(size == data.length){data = Arrays.copyOf(data,data.length<<1);}return val;}public boolean isEmpty() {return size == 0;}public int size(){return size;}public E pop(){if (isEmpty()){throw new NoSuchElementException("stack is empy,cannot pop!");}E oldVal = (E)data[size - 1];size --;return oldVal;}public E peek(){if (isEmpty()){throw new NoSuchElementException("stack is empy,cannot peek!");}return (E)data[size - 1];}@Overridepublic String toString() {StringBuilder sb = new StringBuilder();sb.append("bottom [");for (int i = 0; i < size; i++) {sb.append(data[i]);if(i < size - 1){sb.append(",");}}sb.append("] top");return sb.toString();}
}

4.2 Test类

public static void main(String[] args) {MyStack<Integer> stack = new MyStack<>();
//        将e入栈，并返回estack.push(1);stack.push(2);stack.push(3);stack.push(4);stack.push(5);System.out.println("将栈顶元素出栈并返回");System.out.println(stack.pop());System.out.println("获取栈顶元素");System.out.println(stack.peek());System.out.println("检测栈是否为空");System.out.println(stack.isEmpty());System.out.println("获取栈中有效元素个数");System.out.println(stack.size());System.out.println(stack);}

4.3 测试结果

 【例题】一个栈的入栈序列为ABCDE，则不可能的出栈序列为（ ）

        A. ABCDE

        B. EDCBA

        C. DCEBA

        D. ECDBA

稳妥的做法是画图逐个选项检测，大概率是不会出错的，

如果是E先出，说明ABCDE都已经全部入栈，E出栈之后，此时栈顶元素是D，如果再要出栈应该是D，而不应该是C。故应该选择D。