前言:
如今咱们对“出栈过程”大体比较看重,咱们都需要知道一些“出栈过程”的相关知识。那么小编也在网摘上网罗了一些有关“出栈过程””的相关知识,希望朋友们能喜欢,同学们一起来学习一下吧!栈是用来存储逻辑关系为 "一对一" 数据的线性存储结构
后进去先出来。
栈的存储结构中关键的在于:存与取。
栈只能从表的一端存取数据,另一端是封闭的
在栈中,无论是存数据还是取数据,都必须遵循"先进后出(LIFO)"的原则,即最先进栈的元素最后出栈。上图 的栈来说,从图中数据的存储状态可判断出,元素 1 是最先进的栈。因此,当需要从栈中取出元素 1 时,根据"先进后出"的原则,需提前将元素 3 和元素 2 从栈中取出,然后才能成功取出元素 1。
把上图的栈立起来就是这样子的(这样或许更好理解)。
实现一个栈的数据结构,使其具有以下方法:压栈、弹栈、取栈顶元素、判断栈是否为空以及获取栈中元素个数。下面是一个栈的入栈和出栈整个过程
栈的实现有两种方法,分别为采用数组来实现和采用链表来实现。下面分别详细介绍这两种方法。
数组实现分析
在采用数组来实现栈的时候,栈空间是一段连续的空间。实现思路如下图所示
从上图中可以看出,可以把数组的首元素当作栈底,同时记录栈中元素的个数size,假设数组首地址为arr,压栈的操作其实是把待压栈的元素放到数组arr[size]中,然后执行size++操作;同理,弹栈操作其实是取数组arr[size-1]元素,然后执行size--操作。根据这个原理可以非常容易实现栈。
代码实现
/*** 数组使用栈** @author tian* @date 2020/4/26*/public class MyStackDemo { public static void main(String[] args) { ArrayStack<Integer> stackDemo = new ArrayStack(); //入栈两个元素 stackDemo.push(1); stackDemo.push(2); System.out.println("栈顶元素:" + stackDemo.top()); System.out.println("栈大小:" + stackDemo.size()); stackDemo.pop(); System.out.println("栈第一次弹出元素"); stackDemo.pop(); System.out.println("栈第二次弹出元素"); stackDemo.pop(); }}class ArrayStack<T> { private ArrayList<T> arrayList; private int stackSize; public ArrayStack() { this.stackSize = 0; this.arrayList = new ArrayList<>(); } int size() { return stackSize; } boolean isEmpty() { return this.stackSize == 0; } //返回栈顶元素 T top() { if (isEmpty()) { return null; } return arrayList.get(stackSize - 1); } //元素出栈 T pop() { if (stackSize > 0) { return arrayList.get(--stackSize); } else { System.out.println("栈中无元素了"); return null; } } //元素入栈 void push(T item) { arrayList.add(item); stackSize++; }}
运行输出
链表实现
分析
在创建链表的时候经常采用一种从头结点插入新结点的方法,可以采用这种方法来实现栈,最好使用带头结点的链表,这样可以保证对每个结点的操作都是相同的,实现思路如下图所示。
在上图中,在进行压栈操作时,首先需要创建新的结点,把待压栈的元素放到新结点的数据域中,然后只需要(1)和(2)两步就实现了压栈操作(把新结点加到了链表首部)。同理,在弹栈的时候,只需要进行步骤(3)的操作就可以删除链表的第一个元素,从而实现弹栈操作。
代码实现
/*** 数组实现栈** @author tian* @date 2020/4/26*/public class NodeStackDemo<T> { private MyNode<T> head; public NodeStackDemo() { this.head = new MyNode<>(); head.data = null; head.next = null; } //判断栈是否为空 boolean isEmpty() { return head == null; } //栈的大小 int size() { int size = 0; MyNode<T> p = head.next; while (p != null) { p = p.next; size++; } return size; } void push(T e) { MyNode<T> temp = new MyNode<>(); temp.data = e; temp.next = head.next; head.next = temp; } //出栈,同时返回栈顶元素 T pop() { MyNode<T> temp = head.next; if (temp != null) { head.next = temp.next; return temp.data; } System.out.println("占中已经不存元素了"); return null; } //获取栈顶元素 T top() { if (head.next != null) { return head.next.data; } System.out.println("栈中不存在元素"); return null; } public static void main(String[] args) { NodeStackDemo<Integer> stackDemo = new NodeStackDemo(); stackDemo.push(1); stackDemo.push(3); stackDemo.push(5); System.out.println("栈顶元素:" + stackDemo.top()); System.out.println("栈大小:" + stackDemo.size()); stackDemo.pop(); System.out.println("栈第一次弹出元素"); stackDemo.pop(); System.out.println("栈第二次弹出元素"); stackDemo.pop(); System.out.println("栈第二次弹出元素"); stackDemo.pop(); }}class MyNode<T> { T data; MyNode<T> next;}
运行结果
两种方法的对比
采用数组实现栈的优点:一个元素值占用一个存储空间;它的缺点:如果初始化申请的存储空间太大,会造成空间的浪费,如果申请的存储空间太小,后期会经常需要扩充存储空间,扩充存储空间是个费时的操作,这样会造成性能的下降。采用链表实现栈的优点:使用灵活方便,只有在需要的时候才会申请空间。它的缺点:除了要存储元素外,还需要额外的存储空间存储指针信息。
算法性能分析:这两种方法压栈与弹栈的时间复杂度都为O(1)。
标签: #出栈过程