线性结构-栈

栈是Stack一个后进先出Last In First Out,LIFO的线性表，他要求只在表尾对数据执行删除和插入等操作。 栈就是一个线性表，可以是数组、也可以是链表。但它的操作有别于一般的线性表。栈的元素必须先进后出，也就是先进入栈的元素必须后出栈。而不能像一般的链表或数组那样从任意位置读取元素。 栈的操作只能在线性表的表尾进行，这个标为被称为栈的栈顶top，相应的表头被称为栈的栈底bottom

栈的数据必须从栈顶进入，也必须从栈顶取出，先入栈的数据在后入栈的数据下面。 栈中不含有任何数据时的状态叫作空栈，此时栈顶top等于栈底bottom。

栈的定义

前面说过，作为一个线性结构，栈既可以用数组实现，也可以用链表实现。 在大多数情况下，我们用数组来实现栈。

代码语言：javascript复制

public class MyStack {
	int[] stack; // 用数组实现一个栈
	int top; // 栈顶索引，实际上就是栈顶位置的数组下标
	int capacity; // 栈的容量
	public MyStack(int capacity) {
		stack = new int[capacity]; // 动态初始化栈，长度为capacity
		top = 0; // 栈顶索引为0，说明此时是空栈
		this.capacity = capacity; // 初始化栈的容量
	}
    //更多操作
}

MyStack类中并没有定义栈底位置bottom的值。这是因为我们是使用数组来实现栈的，所以bottom的值恒为0。 如果采用链表的形式实现栈，则需要定义bottom的值，它应当是指向栈底节点的指针变量（引用变量）。

MyStack是我们定义的栈类，包含3个成员变量：

• stack：int[]类型的数组，说明栈将存储整型。
• top：栈顶在数组stack中的下标，一般规定top始终指向栈顶元素的上一个空间。真正的栈顶元素是stack[top-1]。
• capacity：记录栈当前的容量，随着栈中元素不断增加，可对栈进行扩容，变量capacity的值也应随之调整。

在调用构造函数public MyStack(int capacity)初始化一个栈后。top等于bottom等于0，即栈顶等于栈底，此时栈中没有数据（空栈）。

栈的基本操作

入栈

入栈就是向栈中存入数据。入栈要在栈顶进行，每当向栈顶压入一个数据，栈顶指针top都要 1，直到栈满。

代码语言：javascript复制

public void push(int elem) {
    // 入栈操作
    if (top == capacity) {
        // 达到栈容量上限，需要扩容
        increaseCapacity();
    }
    stack[top] = elem; // 将元素elem存放在stack[top]
    top  ; // top指向栈顶元素的上一个空间，此时栈顶元素为stack[top-1]
}

在数据入栈前判断栈是否已满if (top == capacity) 因为规定了top始终指向栈顶元素的上一个空间，下标top是从0开始计算的，所以**stack[top-1]**就是栈顶元素，并且**top**值等于该栈中元素的个数。当top等于capacity时，栈中元素的个数等于capacity，top已经指向stack数组的外面，所以不能再向栈中压入元素，需要调用increaseCapacity()函数对栈进行扩容。

代码语言：javascript复制

public void increaseCapacity() {
    // 增加栈的容量
    // 初始化一个新栈，容量是原stack容量的2倍
    int[] stackTmp = new int[stack.length * 2];
    System.arraycopy(stack, 0, stackTmp, 0, stack.length);
    stack = stackTmp;
}

将参数存入栈顶，即执行stack[top] = elem;操作。 然后移动top，指向栈顶元素的上一个位置top ;。

出栈

函数pop()的作用是将栈顶元素取出并返回，同时调整栈顶指针top的值-1。

代码语言：javascript复制

public int pop() {
    // 出栈操作
    if (top == 0) {
        // 栈顶等于栈底，说明栈中没有数据
        System.out.println("There are no elements in stack");
        return -111;
    }
    return stack[--top];
}

与所有数据结构一样，在执行增删操作之前，要先判断是否符合条件。 从栈顶取出元素前，需要判断栈内是否有元素。当top==0时，栈内没有元素，pop的操作将是非法的，所以需要返回一个无效值ERROR_ELEM_VALUE，在介绍“线性结构-数组”中，有一道“删除重复元素”的题目，当时将重复元素赋值为-111，也是同样的道理。一旦将某个整数赋值给常量**ERROR_ELEM_VALUE**，则该整数就不能作为栈中的有效元素了。

来两道题

二/十进制转换

利用栈结构将二进制数转换为十进制数

利用栈的FILO特点，方便位权运算

首先将二进制数从高位到低位顺序入栈。然后从栈顶依次取出每一个元素。当取出第i个元素时，结果增加

2^{i-1}

。最终的和即为该二进制数对应的十进制数。

代码语言：javascript复制

public class BiToDecTest {
	public static String BiToDec(String binary) {
		MyStack stack = new MyStack(10);
		int i;
		for (i = 0; i < binary.length(); i  ) {
			if (binary.charAt(i) == '0') {
				stack.push(0); // 将二进制0入栈
			} else {
				stack.push(1);// 将二进制1入栈
			}
		}
		i = 0;
		int e;
		long sum = 0;
		while ((e = stack.pop()) != stack.ERROR_ELEM_VALUE) {
			sum = sum   (int) (e * Math.pow(2, i));
			i  ;
		}
		return String.valueOf(sum);
	}

	public static void main(String args[]) {
		System.out.println("The result of converting 11001 to decimal number is");
		System.out.println(BiToDecTest.BiToDec("11001"));
	}
}

public static String BiToDec(String binary)和String.valueOf(sum)的作用是将binary指定的二进制串转换成对应的十进制串并返回。参数**binary**是**String**类型，为了与之对应，函数的返回值也是**String**类型，并通过**String.valueOf()**函数将十进制转换成对应的字符串。

括号匹配问题

---

已知表达式中只允许有两种括号：圆括号()和方括号[]。它可以任意地嵌套使用，例如[()]、[()()]、[()([])]都是合法的表达式。括号必须成对出现，[(])、([)]、[())等不成对出现的情况是非法的。编写一个程序，判断一个括号表达式是否合法。

---

一道栈的经典问题

1. 合法的情况下，第一个入栈的字符应该是左括号。
2. 我们可以在检测到下一个字符为右括号时，弹出栈内的左括号，查看是否匹配。
3. 如果不匹配或已经空栈，则表明括号表达式不合法。

我们介绍一段没上面那么好理解的代码：

循环遍历字符串上的字符，每个字符进行如下判断： 首先是判断是否栈空，如果栈不为空，则将栈顶c与临时字符expression.charAt(i)匹配，成功则继续遍历；不成功则再将刚刚出栈的元素塞回，并将临时字符入栈。 如果栈为空，则将临时字符expression.charAt(i)直接入栈。 如果表达式合法，所有元素都被弹出，最后结果是空栈。 因此最后一步即为判断是否为空栈，栈空则表示合法。不为空则非法。

代码语言：javascript复制

public static boolean MatchBracket(String expression) {
    // 判断括号表达式expression是否合法
    MyStack stack = new MyStack(10); // 初始化栈
    char c;
    for (int i = 0; i < expression.length(); i  ) {
        if ((c = stack.pop()) != stack.ERROR_ELEM_VALUE) {
            // 从栈中弹出了有效元素，说明栈不为空
            if (!match(c, expression.charAt(i))) {
                // 如果栈顶元素c跟expression的第i个括号
                // 不相匹配，则将c重新入栈，同时将
                // expression的第i个括号入栈
                stack.push(c);
                stack.push(expression.charAt(i));
            }
        } else {
            // 如果是空栈，说明输入的是第1个括号，因此保存在栈中
            stack.push(expression.charAt(i));
        }
    }
    if (stack.pop() != stack.ERROR_ELEM_VALUE) {
        // 栈不为空，说明表达式expression不合法，返回false
        return false;
    } else {
        return true; // 栈为空，说明表达式expression合法，返回true
    }
}

在检索完括号表达式之后，如果栈已空，说明左右括号完全匹配，即括号表达式合法。 如果栈未空，则表明输入的括号不完全匹配，也就是括号表达式非法。 对于匹配括号的函数，我们不能简单地作==的判断，因为'('注定不等于')'。 如果是C ，我们可以使用map容器，右括号为索引，所括号为实值。因为我们是检测到右括号之后才去匹配左括号，所以要将右括号作为索引。 如果是Java，也有类似的容器。但在这里，我们使用更粗暴的方法。

代码语言：javascript复制

private static boolean match(char a, char b) {
    if ((a == '(' && b == ')') ||
            (a == '[' && b == ']')) {
        return true;
    }
    return false;
}

二进制 函数 链表 数据 数组

0 人点赞