二、栈的应用

栈是一个重要的数据结构，其特性简而言之就是“后进先出”，这种特性在计算机中有着广泛的运用。其实程序员无时无刻不在使用者栈，函数的调用是我们间接使用栈的最好的例子，但是栈在实际中的运用远不止这些，比较经典的应用还包括括号匹配、逆波兰表达式的求值等，下面就介绍这两个对栈的简单应用：

1、括号匹配问题

1）括号匹配问题的四种结果： 

（1）左右括号匹配正确 

（2）左右括号匹配错误 

（3）左括号多于右括号 

（4）右括号多于左括号 

2）算法基本思想 

（1）顺序扫描算数表达式（表现为一个字符串），当遇到三种类型的左括号时候让该括号进栈； 

（2）当扫描到某一种类型的右括号时，比较当前栈顶元素是否与之匹配，若匹配，退栈继续判断；若当前栈顶元素与当前扫描的括号不匹配，则左右括号配对次序不正确； 

（3）若字符串当前为某种类型的右括号而堆栈已经空，则右括号多于左括号； 

（4）字符串循环扫描结束时，若堆栈非空（即堆栈尚有某种类型的左括号），则说明左括号多于右括号； 

（5）否则，括号配对正确。 

 

剑指Offer——栈的java实现和栈的应用举例

     栈是一种先进后出的数据结构, 栈的实现如下：

     首先定义了栈需要实现的接口:

 

public interface MyStack<T> {
    /**
     * 判断栈是否为空
     */  
    boolean isEmpty();  
    /**
     * 清空栈
     */  
    void clear();  
    /**
     * 栈的长度
     */  
    int length();  
    /**
     * 数据入栈
     */  
    boolean push(T data);  
    /**
     * 数据出栈
     */  
    T pop();
}

 

     接下来定义了栈的数组实现：

 

package cn.edu.ujn.stack;
/**
 * 栈的数组实现, 底层使用数组
 * @author SHQ
 *
 * @param <T>
 */
public class MyArrayStack<T> implements MyStack<T> {
// 定义初始栈的大小
private Object[] objs = new Object[16];
// 栈的大小
    private int size = 0;  
  
    @Override  
    public boolean isEmpty() {
        return size == 0;
    }  
  
    @Override  
    public void clear() {  
        // 将数组中的数据置为null, 方便GC进行回收  
        for (int i = 0; i < size; i++) {  
            objs[size] = null;  
        }  
        size = 0;  
    }  
  
    @Override  
    public int length() {  
        return size;  
    }  
  
    @Override  
    public boolean push(T data) {  
        // 判断是否需要进行数组扩容  
        if (size >= objs.length) {  
            resize();  
        }  
        objs[size++] = data;  
        return true;  
    }  
  
    /**
     * 数组扩容
     */  
    private void resize() {  
        Object[] temp = new Object[objs.length * 3 / 2 + 1];
        // 复制
        for (int i = 0; i < size; i++) {  
            temp[i] = objs[i];  
            objs[i] = null;  
        }  
        // 将objs重新设置为栈空间
        objs = temp;
    }  
  
    @SuppressWarnings("unchecked")  
    @Override  
    public T pop() {  
        if (size == 0) {  
            return null;  
        }  
        return (T) objs[--size];  
    }  
  
    @Override  
    public String toString() {  
        StringBuilder sb = new StringBuilder();  
        sb.append("MyArrayStack: [");  
        for (int i = 0; i < size; i++) {  
            sb.append(objs[i].toString());  
            if (i != size - 1) {  
                sb.append(", ");  
            }  
        }  
        sb.append("]");  
        return sb.toString();  
    }  
}

 

     然后定义了栈的链表实现：

 

package cn.edu.ujn.stack;
/**
 * 栈的链表实现, 底层使用链表
 * @author SHQ
 *
 * @param <T>
 */
public class MyLinkedStack<T> implements MyStack<T> {
    /**
     * 栈顶指针
     */  
    private Node top;  
    /**
     * 栈的长度
     */  
    private int size;
      
    public MyLinkedStack() {
        top = null;
        size = 0;
    }
      
    @Override
    public boolean isEmpty() {
        return size == 0;
    }  
      
    @Override  
    public void clear() {  
        top = null;  
        size = 0;
    }  
      
    @Override  
    public int length() {  
        return size;  
    }  
      
    @Override  
    public boolean push(T data) {  
        Node node = new Node();  
        node.data = data;  
        node.pre = top;  
        // 改变栈顶指针  
        top = node;  
        size++;  
        return true;  
    }  
      
    @Override  
    public T pop() {  
        if (top != null) {  
            Node node = top;  
            // 改变栈顶指针
            top = top.pre;  
            size--;  
            return node.data;  
        }  
        return null;  
    }  
      
    /**
     * 将数据封装成结点
     */  
    private final class Node {  
        private Node pre;  
        private T data;  
    }  
}

 

     两种实现的比较, 主要比较数据入栈和出栈的速度:

 

package cn.edu.ujn.stack;
 
public class Test {
public static void main(String[] args) {
testSpeed();
}
 
private static void testSpeed() {
// 测试数组实现
//MyStack<Person> stack = new MyArrayStack<Person>();
// 测试链表实现
MyStack<Person> stack = new MyLinkedStack<Person>();
int num = 1000000;
long start = System.currentTimeMillis();
for (int i = 0; i < num; i++) {
stack.push(new Person("xing", 25));
}
long temp = System.currentTimeMillis();
System.out.println("push time: " + (temp - start));
while (stack.pop() != null)
;
System.out.println("pop time: " + (System.currentTimeMillis() - temp));
}
}

 

     运行结果如下:

   

     可见入栈、出栈速度MyArrayStack则有明显的优势.

     为什么测试结果是这样的? 可能有些朋友的想法是：数组实现的栈应该具有更快的遍历速度, 但增删速度应该比不上链表实现的栈才对。但是栈中数据的增删具有特殊性: 只在栈顶入栈和出栈。也就是说数组实现的栈在增加和删除元素时并不需要移动大量的元素, 只是在数组扩容时需要进行复制。而链表实现的栈入栈和出栈时都需要将数据包装成Node或者从Node中取出数据, 还需要维护栈顶指针和前驱指针。

栈的应用举例

1.将10进制正整数num转换为n进制

 

package cn.edu.ujn.stack;
 
public class StackApp {
 
/**
 * @param args
 */
public static void main(String[] args) {
//System.out.println(conversion4D2X(22, 2));
//System.out.println(isMatch("[()]"));
System.out.println(lineEdit("Hello  #world"));
}
/**
 *栈的应用举例-将10进制正整数num转换为n进制
 * @param num 待转化十进制数
 * @param n 转化进制
 * @return
 */
private static String conversion4D2X(int num, int n) {  
    MyStack<Integer> myStack = new MyArrayStack<Integer>();  
    Integer result = num;  
    while (true) {  
        // 将余数入栈  
        myStack.push(result % n);  
        result = result / n;  
        if (result == 0) {  
            break;  
        }  
    }  
    StringBuilder sb = new StringBuilder();  
    // 按出栈的顺序倒序排列即可  
    while ((result = myStack.pop()) != null) {  
        sb.append(result);  
    }  
    return sb.toString();  
}
}

 

2.检验符号是否匹配.

      '['和']', '('和')'成对出现时字符串合法. 例如"[][]()", "[[([]([])()[])]]"是合法的; "([(])", "[())"是不合法的.

     遍历字符串的每一个char, 将char与栈顶元素比较. 如果char和栈顶元素配对, 则char不入栈, 否则将char入栈. 当遍历完成时栈为空说明字符串是合法的.

 

/**
 * 栈的应用举例-检验符号是否匹配:
 * '['和']', '('和')'成对出现时字符串合法. 例如"[][]()", "[[([]([])()[])]]"是合法的; "([(])", "[())"是不合法的.
 * @param str
 * @return boolean
 */
private static boolean isMatch(String str) {  
    MyStack<Character> myStack = new MyArrayStack<Character>();  
    char[] arr = str.toCharArray();  
    for (char c : arr) {  
        Character temp = myStack.pop();  
        // 栈为空时只将c入栈  
        if (temp == null) {  
            myStack.push(c);  
        }  
        // 配对时c不入栈  
        else if (temp == '[' && c == ']') {  
        }   
        // 配对时c不入栈  
        else if (temp == '(' && c == ')') {  
        }   
        // 不配对时c入栈  
        else {  
            myStack.push(temp);  
            myStack.push(c);  
        }  
    }  
    return myStack.isEmpty();  
}

 

3.行编辑

   输入行中字符'#'表示退格, '@'表示之前的输入全都无效.

   使用栈保存输入的字符, 如果遇到'#'就将栈顶出栈, 如果遇到@就清空栈. 输入完成时将栈中所有字符出栈后反转就是输入的结果:

 

/**
 * 栈的应用举例-行编辑:
 * 输入行中字符'#'表示退格, '@'表示之前的输入全都无效.
 * @param input
 * @return String
 */
private static String lineEdit(String input) {  
    MyStack<Character> myStack = new MyArrayStack<Character>();  
    char[] arr = input.toCharArray();  
    for (char c : arr) {  
        if (c == '#') {  
            myStack.pop();  
        } else if (c == '@') {  
            myStack.clear();  
        } else {  
            myStack.push(c);  
        }  
    }  
    // StringBuffer线程安全，StringBuilder线程不安全效率高
    StringBuilder sb = new StringBuilder();
    Character temp = null;  
    while ((temp = myStack.pop()) != null) {  
        sb.append(temp);  
    }  
    // 反转字符串  
    sb.reverse();  
    return sb.toString();  
}

 

美文美图

 

栈的应用：栈混洗
一、栈混洗的定义：


那么这到底是啥意思呢？栈混洗到底有啥作用呢？
二、栈混洗的常见问题分析：
根据上述栈混洗的原理，我们可以得知，栈混洗就是利用一个栈，去让无序变成有序，抑或是让有序变成无序，更有甚者，是让某种顺序，变成另一种顺序，进行序列的调整并且输出。
2.1 无序变有序：
练习1：天梯赛level2的压轴题：彩虹瓶 大伙感受一下
算法分析：
来了一串序列，它是乱序的，如何利用一个栈让他变成顺序？

可以先设定一个当前需要值：now = 1;

如果当前送来的颜色，是我们所需要的，也就是：color = now;

此时我们就要更新需要的颜色值：now++;

然后再去之前囤积的栈里去查找栈顶是不是我们所需要的当前值，如果是，则一直查顶、去顶：
while(now == s.top() && !s.empty()){
		now++;
		s.pop();
}

那最终如何判断是否成功了呢？很简单，就看最后栈是否为空即可！
AC代码如下：
#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;

int main(){
	int n, m, k;
	cin >> n >> m >> k;
	while(k--){
		stack<int>box;
		int now, full = 0, book = 1;
		for(int i = 0;i < n;i++){
			cin >> now;
			if(now == book){
				book++;
				while(!box.empty()){
					if(book == box.top()){
						book++;
						box.pop();
					}else
						break;
				}
			}else if(!full){
				box.push(now);
				if(box.size() > m)
					full = 1;
			}
		}
		if(full || book != n + 1)
			cout << "NO" << endl;
		else
			cout << "YES" << endl;
	}
	return 0;
}

2.2 让有序变无序：

算法分析
这个问题明显的就是：有序进站（栈）

然后通过火车站这个容量大小一定的栈，去让他变成各种各样的顺序，问这些顺序是否合法？

算法很简单：

第一步：设一个当前进站编号：now = 1;

第二步：问当前顺序数组的第x个元素，初始化：x = 1;

然后判断，如果这个第x个元素就是当前所需要的，那么x++, now++;

如果不是，则把第x个元素进栈

如果发现当前进站编号，是等于栈顶元素的，那么就一直判断栈顶，然后出栈即可！

这个代码和上述差不多，就留给各位自己练习吧！
附上参考代码：
#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;

const int maxn = 1005;
int n, m, k, a[maxn];
int main(){
	cin >> n >> m >> k;
	while(k--){
		stack<int>s;
		int x = 1, cnt = 0;
		for(int i = 0;i < n;i++)
			cin >> a[i];
		while(cnt < n){
			if(x == a[cnt]){
				cnt++;
				x++;
			}else if(!s.empty() && a[cnt] == s.top()){
				cnt++;
				s.pop();
			}else if(s.size() < m){
				s.push(x);
				x++;
			}else
				break; 
		}
		if(s.empty())
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
	}	
	return 0;
} 

栈和栈的应用：撤销操作和系统栈

1、栈相关概念

栈是一种线性结构
	
相比数组，栈对应的操作是数组的子集
	
只能从一端添加元素，也只能从一端取出元素
	
这一端称为栈顶
 

2、栈数据结构类型



3、栈的应用

（1）撤销操作



（2）系统栈



A2表示函数A第二行

B2表示函数B第二行

 

函数A（）调用函数B（），把A2压入栈底，函数B（）调用函数C（），把B2压栈，当函数C（）调用完成时，B2出栈，当函数B（）调用完成时，A2出栈，最后函数A（）执行完成，至此整个系统栈调用完毕。

 

栈最常用的场景：递归调用

 

如果感兴趣的童鞋，可以观看我下一篇博客：自定义栈的基本实现