数据结构之栈

目录

一、栈的概念 

 二、栈的相关小题

三、栈中的一些方法

 四、栈的实现

一、栈的概念 

 二、栈的相关小题

1.出栈顺序，如：

已知一个栈的入栈序列是mnxyz，则不可能的出栈顺序是（）

A.mnxyz                                                        B.xnyzm                                                   C.nymxz                                                    D.nmyzx

答案：C

分析如下：

A.进一个出一个即可达到这种效果,B、C如下图，D与之同理

 2.中缀表达式转后缀表达式

（1）中缀表达式是一个通用的算术或逻辑公式表示方法， 操作符是以中缀形式处于操作数的中间（例：3 + 4），中缀表达式是人们常用的算术表示方法。与前缀表达式（例：+ 3 4）或后缀表达式（例：3 4 +）相比，中缀表达式不容易被计算机解析，但仍被许多程序语言使用，因为它符合人们的普遍用法。与前缀或后缀记法不同的是，中缀记法中括号是必需的。计算过程中必须用括号将操作符和对应的操作数括起来，用于指示运算的次序。

（2）前缀表达式是一种没有括号的算术表达式，与中缀表达式不同的是，其将运算符写在前面，操作数写在后面。为纪念其发明者波兰数学家Jan Lukasiewicz，前缀表达式也称为“波兰式”。例如，- 1 + 2 3，它等价于1-(2+3)。

（3）后缀表达式：逆波兰式（Reverse Polish notation，RPN，或逆波兰记法），也叫后缀表达式（将运算符写在操作数之后）

算法定义：①如果E是一个变量或常量，则E的后缀式是E本身。②如果E是E1 op E2形式的表达式，这里op是任何二元操作符，则E的后缀式为E1'E2' op，这里E1'和E2'分别为E1和E2的后缀式。③如果E是（E1）形式的表达式，则E1的后缀式就是E的后缀式。

三、栈中的一些方法

 四、栈的实现

可以用顺序表实现，也也可以用链表实现，但是相对来说，用顺序表实现要简单一些，所以我们优先使用顺序表实现栈

import java.util.Arrays;

public class MyStack {
    public int[] elem;
    public int usedSize;

    public MyStack()
    {
        this.elem = new int[5];
    }

    public void push(int val)
    {
        if(isFull()){
            this.elem = Arrays.copyOf(this.elem,2*this.elem.length);//扩容
        }
        this.elem[this.usedSize++] = val;
    }
    public boolean isFull(){
        return this.usedSize == this.elem.length;
    }
    public int pop()
    {
        if(isEmpty())
        {
            throw new RuntimeException("栈为空！\n");
        }
        int oldVal = this.elem[usedSize - 1];
        this.usedSize--;
        return oldVal;
    }
    //入栈和出栈的时间复杂度为O（1）
    public boolean isEmpty()
    {
        return this.usedSize == 0;
    }
    public int peek(){
        if(isEmpty())
        {
            throw new RuntimeException("栈为空！\n");
        }
        return this.elem[usedSize-1];
    }
}

public class TestDemo {
    public static void main(String[] args) {
        MyStack stack = new MyStack();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.println(stack.pop());
        System.out.println(stack.peek());
        System.out.println(stack.isEmpty());
        System.out.println(stack.isEmpty());
    }
}

编译并运行，输出如下：

3
2
false
false

 我们也可以用链表实现一个栈，但是链表既可以是头插，也可以是尾插，那么当我们入栈的时候是用头插法还是尾插法呢？答案是头插法，因为尾插法的时间复杂度为O(n)（因为尾插法需要找尾巴）；我们假设用头插法入栈，那么出栈的时候只需要删除头结点即可，时间复杂度仍为O(1)。但是尾插法也不是不行，我们可以增加一个变量记录尾结点，这样我们的入栈就可以做到时间复杂度为O(1)了，但是出栈呢？链表的删除节点操作需要找到前一个节点，此时我们还是需要通过遍历去找到该节点，时间复杂度又变成了O(n)，为此，我们使用尾插法实现栈时，使用双向链表来实现它。