利用数组实现栈（Java实现）

利用数组实现栈（Java实现）

栈介绍

栈是一个先入后出的有序列表。

栈是限制线性表中元素的插入和删除只能在线性表中同一端进行的一种特殊的线性表，允许插入和删除的一端，为变化的一端，称为栈顶，另一端为固定的一端，称为栈底。

最先放入栈中的元素在栈底，最后放入的元素在栈顶。

最先出栈的元素在栈顶，最后出栈的元素在栈底。

分析

使用数组来模拟栈的实现，首先考虑到数组的长度是固定的，所以使用栈就必须给一个特定的长度，即最大长度MaxSize。自定义一个栈顶指针， 初始化数据为-1，因为数组的索引值是从0开始的，为了不引起冲突，从-1开始。

栈为空：当top=-1时，即等于初始化数据，没有任何元素存在数组中，则说明栈为空。

栈满：随着添加元素，栈顶指针将会往后移动，但是要考虑到数组的长度是固定的，就存在一个满的情况。判断条件是当top=MaxSize-1时，栈就满了。比如定义3个大小的数组，放入一个数据1，top从-1变为0，再放入一个数据2，top从0变成1，再放入一个数据3，top从1变成2.这时候数组已经满了，判断条件即为top =MaxSize，为栈满。

进栈：进栈前先判断栈是否满了，否则不能进栈。将top+1，在将数组索引为top的元素赋值为添加进来的数据。

出栈：出栈前先判断栈是否为空，否则不能出栈。如果不为空，先取栈顶的元素，即索引值为top的元素，然后在将top-1。

遍历栈：遍历时也要判断栈中是否为空，遍历数据也是从栈顶元素开始遍历， 一直遍历到栈底就结束了。

代码实现

package cn.mrlij.stack;

import java.util.Arrays;

import java.util.Scanner;

/**

* 使用数组实现栈

*

* @author dreamer

*

*/

public class ArrayStackDemo {

public static void main(String[] args) {

// 测试

ArrayStack a = new ArrayStack(5);

boolean flag = true;// 用于判断循环结束的标志

Scanner sc = new Scanner(System.in);

String key = "";// 用于接受菜单的选项

while (flag) {

System.out.println("show：显示栈");

System.out.println("exit：退出程序");

System.out.println("push：进栈");

System.out.println("pop：出栈");

key = sc.nextLine();

switch (key) {

case "show":

a.show();

break;

case "exit":

flag = false;

System.out.println("程序结束！");

break;

case "push":

System.out.println("请输入要进栈的数据：");

int val = sc.nextInt();

a.push(val);

break;

case "pop":

try {

int pop = a.pop();

System.out.println("出栈的值是：" + pop);

} catch (Exception e) {

// TODO: handle exception

System.out.println(e.getMessage());

}

break;

default:

break;

}

}

}

}

class ArrayStack {

private int MaxSize;// 定义数组的最大长度

private int[] arr;// 定义数组，数据就放在该数组

private int top = -1;// 定义栈顶，初始化数据为-1

public ArrayStack(int maxSize) {

this.MaxSize = maxSize;

arr = new int[MaxSize];

}

// 判断数组是否为空

public boolean isEmpty() {

return top == -1;

}

// 判断数组是否满了

public boolean isFull() {

System.out.println("栈顶：" + top + "最大长度：" + MaxSize);

return top == MaxSize - 1;

}

// 进栈

public void push(int val) {

// 先判断栈是否满了，满了就不能添加进去

if (isFull()) {

System.out.println("栈已经满了~~");

return;

}

top++;

arr[top] = val;

}

// 出栈

public int pop() {

// 先判断栈是否为空

if (isEmpty()) {

throw new RuntimeException("栈为空，无法出栈！");

}

int val = arr[top];

top--;

return val;

}

public void show() {

if (isEmpty()) {

System.out.println("没有数据");

return;

}

for (int i = top; i >= 0; i--) {

System.out.print(arr[i] + "\t");

}

System.out.println();

}

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。