• 如果你学完链表的编写,今天的内容那就很搜一贼了,哈哈,如果你没有学过链表的编写,可以移步到我的链表学习的文章哈~(今天的内容很简单)

• 栈是一种线性结构,如果从数据的存储结构来进行进步不划分,栈结构可以分为

  • 顺序栈:即使用一块地址连续的内存单元依次保存栈内的数据
  • 线性栈:即使用链表形式保存栈内各个元素的值
• 栈结构图

• 如上,栈只能在一段进行操作,这一端称为栈顶,而反方向是栈底,栈结构遵循后入先出LIFO(last in first out)的原则处理数据节点的
• 如上现实生活中的图,我们只能从罐子顶部取出食物,而我们首先放入罐内的我们只能最后拿出来

• 在栈结构中,只有栈顶元素可以访问,一般栈结构的基本操作有两个

  • 入栈push:将数据放到栈顶的操作
  • 出栈pop:将栈顶元素取出的操作

顺序栈

• 顺序栈是有初始化大小的,这也是内部数组的大小,顺序栈有一个标识,即栈顶的标识,他是一个int值,只有有元素入栈就加一,出栈就减一,所以这个标识在等于0的情况下代表是空栈

  public class MyStack<T> { private int top ; private final Object[] elementData; private final int MAX_SIZE; public MyStack() { this.MAX_SIZE = 5; elementData = new Object[MAX_SIZE]; } public MyStack(int max_size) { this.MAX_SIZE = max_size; elementData = new Object[MAX_SIZE]; } //入栈 public void push (T element){ if (top == MAX_SIZE){ throw new RuntimeException("栈已满"); } elementData[top] = element; top ++; } //出栈 public T pop (){ if (top == 0){ return null; } top --; return (T) elementData[top]; } //peek public T peek(){ if (top == 0){ return null; } return (T) elementData[top]; } @Override public String toString() { return Arrays.toString(elementData); } }

• 程序编写还是很简单的,但是上面程序有一个诟病,就是没有达到函数式,就是说,上面直接返回元素的引用,我感觉应该是拷贝一下要返回的对象,避免栈内数据在外面通过引用修改掉,因为这样可能会引发其他引用此栈数据的程序出错

• 测试

  public static void main(String[] args) { MyStack<Integer> stack = new MyStack<>(); stack.push(1); stack.push(2); stack.push(3); stack.push(4); stack.push(5); System.out.println(stack); System.out.println(stack.pop()); System.out.println(stack.pop()); System.out.println(stack.pop()); System.out.println(stack.peek()); System.out.println(stack.pop()); System.out.println(stack.pop()); }

• 结果

  [1, 2, 3, 4, 5] 5 4 3 3 2 1

链式栈

• 如果是链式,那么就无需考虑栈大小了,它可以通过堆内存,来进行动态的扩充栈大小,如果你清楚链表怎么写,那么这个也就信手拈来了,好了下面就是代码实现了

  public class MyLinkedStack<T> { private int top; private Node<T> head; public MyLinkedStack() { this.head = new Node<>(null,null); } private class Node<T>{ private Node<T> next; private T element; public Node(Node<T> next, T element) { this.next = next; this.element = element; } @Override public String toString() { return String.valueOf(element); } } //入栈 public void push(T element){ Node<T> next = head.next; head.next = new Node<>(next,element); top ++; } //出栈 public T pop(){ Node<T> next = head.next; head.next = next.next; top --; return (T) next; } //peek public T peek(){ return (T) head.next; } @Override public String toString() { StringBuilder builder = new StringBuilder(); for (Node<T> node = head.next; node != null ; node = node.next){ builder.append(node.element+","); } return builder.toString(); } }

• 测试

  public static void main(String[] args) { MyLinkedStack<Integer> stack = new MyLinkedStack<>(); for (int i = 0; i < 10; i++) { stack.push(i); } System.out.println(stack); System.out.println(stack.pop()); System.out.println(stack.pop()); System.out.println(stack); System.out.println(stack.peek()); System.out.println(stack.peek()); System.out.println(stack); }

• 结果

  9,8,7,6,5,4,3,2,1,0, 9 8 7,6,5,4,3,2,1,0, 7 7 7,6,5,4,3,2,1,0,