栈属于数据结构的一种,也是比较常用的一种数据结构。下面文章,将通过Java的数组和链表的形式模拟栈结构的实现,来帮助大家对于栈的理解。 一、何为栈?栈(stack)又名堆栈,它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。
二、用数组实现栈用数组模拟栈的思路分析如图: 1.定义一个top变量(指针)表示栈顶初始化为-1. 下面看完整代码示例: class Stack{ public int maxsize;//栈的大小 public int top=-1;//栈顶 public int[] arr; public Stack(int maxsize) { this.maxsize = maxsize; arr=new int[maxsize]; } //判断栈是否为空 public boolean isEmpty(){ return top==-1; } //判断栈是否满 public boolean isFull(){ return top==maxsize-1; } //添加一个元素 public void push(int value){ if(isFull()){ throw new RuntimeException("栈满"); } top++; arr[top]=value; } //弹出一个元素 public int pop(){ if(isEmpty()) throw new RuntimeException("栈空"); int value=arr[top]; top--; return value; } //遍历栈中的元素 public void traverse(){ if (isEmpty()){ return; } //需要从栈顶开始显示数据 for(int i = top; i >= 0 ; i--) { System.out.printf("stack[%d]=%d ", i, arr[i]); } } } 入栈操作 top++;arr[top]=value;其实可以直接改写为arr[++top]=value; 三、链表实现栈思路分析:
public class LinkedListStack<V> { static class Node<V>{ private V data; private Node<V> next; public V getData() { return data; } public void setData(V data) { this.data = data; } public Node<V> getNext() { return next; } public void setNext(Node<V> next) { this.next = next; } } public int stackSize;//栈内元素的个数 public Node<V> top;//栈顶元素 public LinkedListStack() { stackSize = 0; top = null; } //入栈 public void push(V element){ Node<V> temp=top; top=new Node<>(); top.setData(element); top.setNext(temp); stackSize++; } //出栈 public V pop(){ if (isEmpty()) throw new RuntimeException("empty stack"); V value=top.getData(); //栈顶指向下一个元素 top=top.getNext(); stackSize--; return value; } //查看栈顶元素 public V peek(){ return top.getData(); } //判断是否为空 public boolean isEmpty(){ return stackSize==0; } //查看栈内元素个数 public int getStackSize(){ return stackSize; } } 四、测试public class Test { public static void main(String[] args) { LinkedListStack<String> stack = new LinkedListStack<>(); stack.push("a"); stack.push("b"); stack.push("c"); System.out.println(stack.pop()); System.out.println(stack.peek()); System.out.println(stack.getStackSize()); } } 测试结果: c b 2 |
|