数据结构 -- 栈的实现

一、栈的概念及结构 --  先进后出！

栈就是一种特殊线性表，只允许再固定的一端进行元素的插入和删除操作。进行数据的插入和删除操作的一端称为栈顶，另一端为栈底。栈中的数据元素遵守后进先出LIFO（Last in First Out）的原则。压栈：栈的插入操作叫做进栈/压栈/入栈，进去的数据在栈顶。出栈：栈的删除操作。出数据也在栈顶。结构如下：

二、栈的特点分析

从栈的操作特性来看，栈是一种“操作受限”的线性表，只允许在一端插入和删除数据。他的操作再数组和链表中都可以实现。但是特定的数据结构是对特定场景的抽象，数组和链表有太多的操作接口，操作上可能会更灵活，但使用的时候不可控情况会出现较多，自然出错也就比较多了。当某个数据集合只涉及在一端插入和删除数据，并且满足先进后出，后出先进的特性，我们就应该首先选“栈”这种数据结构。

三、栈的实现

栈接口声明： public interface MyStack<T> { /** * 向栈中添加元素/压栈 * @param t */ void push(T t); /** * 取出栈顶元素 */ T pop(); /** * 查看栈顶元素 * @return 返回栈顶元素 */ T peek(); /** * 返回当前栈的元素个数 * @return */ int size(); /** * 判断当前栈是否为空 * @return 为空返回true，否则返回false */ boolean isEmpty(); }

2.数组的动态扩容

以前基于数组实现的栈，是一个固定大小的栈，在初始化时就要指定栈的大小。当栈满之后，就无法再继续添加数据了。想要实现一个支持动态扩容的栈，我们只需要底层依赖一个支持动态扩容的数组就可以了。当栈满以后，我们就申请一个更大的数组，将原来的数据搬移到新数组中。代码如下：

 

import java.util.Arrays; public class ArrayStack { private String[] items; //数组 private int maxSize; //存放的最大数量 private int currentSize; //当前元素的个数 //初始化数组 public ArrayStack(int maxSize){ this.items = new String[maxSize]; this.maxSize = maxSize; this.currentSize = 0; } //入栈 public boolean push(String item){ if(currentSize == maxSize) { //判断 int oldCurrent = maxSize; int newCurrent = oldCurrent << 1; //栈大小已经超过int的最大值 if (((newCurrent + 8) - Integer.MAX_VALUE) > 0) { return false; } //数组扩容 maxSize = newCurrent; items = Arrays.copyOf(items, newCurrent); } items[currentSize] = item; ++currentSize; return true; } //出栈 public String pop(){ if(currentSize == 0){ System.out.println("栈为空"); return null; }else{ String temp = items[currentSize-1]; --currentSize; return temp; } } public int getSize(){ return this.currentSize; } //测试 public static void main(String[] args) { ArrayStack arrayStack = new ArrayStack(4); arrayStack.push("1"); arrayStack.push("2"); arrayStack.push("3"); arrayStack.push("4"); arrayStack.push("5"); System.out.println(arrayStack.getSize()); System.out.println(arrayStack.pop()); System.out.println(arrayStack.getSize()); System.out.println(arrayStack.pop()); } }

3.链表的实现：

 

/** * 基于链表实现的栈 * @param <T> */ class LinkedStack<T> implements MyStack<T>{ private class ListNode{ T data; ListNode next; public ListNode(T data, ListNode next) { this.data = data; this.next = next; } } //栈顶元素 private ListNode top; //栈中元素个数 private static int currentSize; @Override public void push(T t) { ListNode newNode = new ListNode(t,null); if (top == null){ top = newNode; }else{ newNode.next = top; top = newNode; } currentSize++; } @Override public T pop() { if (currentSize == 0){ System.out.println("栈为空。"); return null; } T value = top.data; top = top.next; currentSize--; return value; } @Override public T peek() { if (currentSize == 0){ System.out.println("栈为空"); return null; } return top.data; } @Override public int size() { return currentSize; } @Override public boolean isEmpty() { return currentSize == 0; } }

 

四、栈的应用

 

栈在函数调用中的应用

操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成“栈”这种结构，用来存储函数调用时的临时变量。每进入一个函数，就会将其中的临时作为栈帧入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈。

      2.栈在表达式求值中的应用

利用两个栈，其中一个用来保存操作数，另一个用来保存运算符。我们从左向右遍历表达式，当遇到数字，我们就直接压入操作数栈；当遇到运算符，就与运算符栈的栈顶元素进行比较，若比运算符栈顶元素优先级高，就将当前运算符压入栈，若比运算符栈顶元素的优先级低或者相同，从运算符栈中取出栈顶运算符，从操作数栈顶取出2个操作数，然后进行计算，把计算完的结果压入操作数栈，继续比较。

     3.栈在括号匹配中的应用

用栈保存为匹配的左括号，从左到右一次扫描字符串，当扫描到左括号时，则将其压入栈中；当扫描到右括号时，从栈顶取出一个左括号，如果能匹配上，则继续扫描剩下的字符串。如果扫描过程中，遇到不能配对的右括号，或者栈中没有数据，则说明为非法格式。 当所有的括号都扫描完成之后，如果栈为空，则说明字符串为合法格式；否则，说明未匹配的左括号为非法格式。（括号匹配的具体代码在上一篇博客中）。