Using array stack (Java implementation)

Stack introduction

The stack is a first in, then out ordered list.

Stack is a special linear table that restricts the insertion and deletion of elements in a linear table to the same end in the linear table. The end that allows insertion and deletion is the changing end, which is called the top of the stack, and the other end is the fixed end, which is called the bottom of the stack.

The first element in the stack is at the bottom of the stack, and the last element is at the top of the stack.

The first element out of the stack is at the top of the stack, and the last element out of the stack is at the bottom of the stack.

analysis

Using array to simulate the implementation of stack, first of all, considering that the length of array is fixed, a specific length must be given to use stack, that is, the maximum length maxsize. Customize a stack top pointer. The initialization data is - 1, because the index value of the array starts from 0. In order not to cause conflict, start from - 1.

Stack is empty: when top = - 1, it is equal to the initialization data. If no element exists in the array, it indicates that the stack is empty.

Stack full: with the addition of elements, the stack top pointer will move back, but considering that the length of the array is fixed, there is a full case. The judgment condition is that when top = maxsize-1, the stack is full. For example, define an array of three sizes, put in a data 1, top changes from - 1 to 0, then put in a data 2, top changes from 0 to 1, and then put in a data 3, top changes from 1 to 2 At this time, the array is full, the judgment condition is top = maxsize, and the stack is full.

Stack entry: judge whether the stack is full before entering the stack, otherwise you can't enter the stack. Assign Top + 1 to the element whose array index is top as the added data.

Out of stack: judge whether the stack is empty before out of stack, otherwise it cannot be out of stack. If it is not empty, first take the element at the top of the stack, that is, the element with the index value of top, and then set top-1.

Traversing the stack: when traversing, it is also necessary to judge whether the stack is empty. The traversal data is also traversed from the top element of the stack to the bottom of the stack.

code implementation

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();
 }

}

The above is the whole content of this article. I hope it will help you in your study, and I hope you will support us a lot.