栈的实现


栈的实现

        • 功能
        • 代码
            • 顺序栈
            • 链式栈

栈 一种的线性表,只能按序列在固定的一端进行入栈和出栈等操作。
功能 入栈:存入数据
出栈:输出最后一个存入的数据并删除
peek:输出最后一个存入的数据
isfull:判断栈是否满了
代码 顺序栈 【栈的实现】利用数组来实现栈:顺序栈
class MineStack { public int[] array; public int size = 0; public MineStack() { this.array = new int[10]; }public void push(int v) { if (this.size >= this.array.length){ System.out.println("栈满了"); return ; } this.array[this.size] = v; size++; } public int pop() { int ret =array[size-1]; this.size--; return ret; } public int peek() { return array[size-1]; } public boolean isFull() { if (this.size >= this.array.length) { return true; }else { return false; } } } public class Demo03 {//测试类 public static void main(String[] args) { MineStack sta = new MineStack(); sta.push(0); sta.push(1); sta.push(2); sta.push(3); sta.push(4); sta.push(5); sta.push(6); sta.push(7); sta.push(8); sta.push(9); System.out.println(sta.isFull()); System.out.println(Arrays.toString(sta.array)); System.out.println(sta.peek()); System.out.println(sta.pop()); System.out.println(sta.pop()); System.out.println(Arrays.toString(sta.array)); } }

链式栈 利用链表来实现栈:链式栈
==因为如果用尾插来实现栈的话,每次的出栈的时间复杂度都将是O(n),则推荐采用头插。
class Node{ public int val; public Node next; public Node(int val) { this.val = val; } } class MyStack { public Node head; public int size = 0; public MyStack() { this.size = size; }public void push(int v) { Node node = new Node(v); if (size >= 10){ System.out.println("栈满了"); return ; } if (this.head == null) { this.head = node; }else { node.next = this.head; this.head = node; } this.size++; } public int pop() { int ret =this.head.val; this.head = this.head.next; this.size--; return ret; } public int peek() { return this.head.val; } public boolean isFull() { if (this.size >= 10) { return true; }else { return false; } } public void show(){ Node cur = this.head; System.out.print("["); for (int i = 0; i < size-1; i++) { System.out.print(cur.val+","); cur = cur.next; } System.out.println(cur.val+"]"); } } public class Demo02 {//测试类 public static void main(String[] args) { MyStack stack = new MyStack(); stack.push(1); stack.push(2); stack.push(3); stack.push(4); stack.push(5); stack.push(6); stack.push(7); stack.push(8); stack.push(9); stack.push(0); System.out.println(stack.isFull()); System.out.println(stack.peek()); stack.show(); System.out.println(stack.pop()); System.out.println(stack.pop()); stack.show(); } }

    推荐阅读