jvm 【数据结构】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 stack = new Stack<>();

// 将e入栈，并返回e

stack.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 {

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 {

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];

}

@Override

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.2 Test类

public static void main(String[] args) {

MyStack stack = new MyStack<>();

// 将e入栈，并返回e

stack.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。

推荐文章

 您阅读本篇文章共花了：