搞定数据结构-栈和队列

用户3045442

发布于 2019-11-06 13:52:10

5030

发布于 2019-11-06 13:52:10

栈和队列

本文带大家,理解什么是栈结构和队列结构,学习栈和队列能够帮住大家解决什么问题? 栈和队列很相似两个结构一同讲解. 你需要有上一节讲解的知识数组结构 栈 FLFO 什么是栈,栈是后进先出.就像放盘子一样,从下往上一个一个放,取盘子时从上往下一个一个取出,也就是后进入的盘子先取出来. 可以叫做后进先出或者先进后出.栈显然是一种操作受限的结构,我们完全可以使用上一节讲解的:数组结构来代替栈结构,那么为什么要使用栈结构呢? 满足后进先出这种特性的优先选择栈结构. 栈的应用

撤销操作

 栈可以应用到撤销操作中,比如我们输入了:“举”-》“头“-〉”网“. 其实想输入”望”结果写成了”网”,需要把“网”删除掉,重新写入.

如下,使用栈结构操作. “网”这个错别字在栈顶,“网”改成”望”只需要将“网”从栈顶移除重新写入”望”.

| 网 |
| 头 |
| 举 |
|____|

浏览器的前进和后退功能/程序调用的系统栈当你访问浏览器的a-b-c,当你点击后退之后可以浏览之前的a和b

实现栈

如何实现一个栈呢? 栈主要有两个操作就是入栈和出栈,都是对栈顶的操作,栈可以通过数组和链表来实现,这里我们根据上一节中的数组的结构来实现栈.

代码实现如下: 下面代码非常简单,基于我们上一节中写的动态数组Array来实现. 栈的时间复杂度:入栈和出栈在最好的情况下是O(1),在上一节中我们实现的Array 已经实现了动态扩容的方法,那么栈在入栈和出栈最坏的情况下时间复杂度为:O(n)

Array 内部实现了动态扩容和缩容机制,当栈空间不够时,进行两倍的扩容,当栈中的元素个数小于栈空间的1/4时,进行缩容处理.

极客时间如上图摘自极客时间.

/**
 * 基于动态数组的栈
 *
 * @param <E>
 */
public class ArrayStack<E> extends Array<E> implements Stack<E> {

    private Array<E> array;

    public ArrayStack(int capacity) {
        this.array = new Array<>(capacity);
    }

    public ArrayStack() {
        this.array = new Array<>();
    }

    @Override
    public void push(E e) {//O(1)
        array.addLast(e);
    }

    @Override
    public E pop() {//O(1)
        return array.removeLast();
    }

    @Override
    public E peek() {
        return array.getLast();
    }

    @Override
    public int size() {
        return array.getSize();
    }

    public int getCapacity() {
        return array.getCapacity();
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append("Stack:");
        res.append("[");
        for (int i = 0; i < size(); i++) {
            res.append(array.get(i));
            if (i != array.getSize() - 1) {
                res.append(", ");
            }
        }
        res.append("] top");
        return res.toString();
    }
}

用栈解决括号匹配问题

括号匹配问题是LeetCode上的一个经典问题. 当我们匹配到左括号的时候进行入栈操作,当匹配到右扩号到时候进行栈顶出队操作来匹配两个括号

匹配[]{}() 
public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            //将左括号添加到栈中 ()[]{}
            if (c == '(' || c == '[' || c == '{')
                stack.push(c);
            else {
                //如果栈中没有都没有返回false
                if (stack.isEmpty()) return false;
                Character top = stack.pop();
                if (c == ')' && top != '(') {
                    return false;
                }
                if (c == ']' && top != '[') {
                    return false;
                }
                if (c == '}' && top != '{') {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }

栈在函数调用中的应用

栈还有一个重要的应用就是函数的调用栈. 我们可以根据如下代码理解:

int A(){
1...
2  B();
3...
}
int B(){
1...
2  C();
3...
}

int C(){
...
}

当开始执行A函数,当程序执行到A的第二行时,需要去执行B函数,此时将栈中压入一个信息叫做A2.这是执行B函数当执行到B函数的第二行时,需要去执行C函数,此时将在栈中压入一个信息叫做B2,然后执行C函数,当C函数执行完成之后,此时系统从栈顶中查找信息,找到B2然后出栈,执行完B函数.系统在从栈顶中查找信息,找到A2然后出栈,执行完A函数,栈顶没有任何信息时,A函数就执行完毕了. 运用栈结构实现了函数的调用

栈在表达式求值中的应用

在算术中的加减乘除四则运算比如:3+5x6-1. 我们通过心算就能算出结果,但是计算机是如何计算的呢? 编译器就是通过两个栈结构来实现的,一个栈A保存数,一个栈B保存运算符,当遇到数字压入栈A中,当遇到运算符与栈B的栈顶运算符比较,如果优先级高于栈顶运算符则压入栈.如果低于栈顶运算符的优先级,则从运算符栈B中取出栈顶运算符,与数字栈A中从栈顶取出俩个数字进行运算,把运算结果压入数字栈A中继续比较. 最后清空栈得到运算结果.

图片来自极客时间了解了原理就可以用代码来实现了,这里我就不贴代码了,大家可以自己实现一下. 栈解决浏览器前进和后退问题 了解了栈结构,我们如何用栈来实现浏览器的前进和后退功能呢? 其实我们只需要两个栈即可,一个栈X记录页面,一个栈Y记录后退的页面点击前进按钮,依次从Y 栈中取出页面添加到X栈中,当Y栈为空时,就不能在前进了. 点击后退按钮,一次从X栈中取出页面添加到Y栈中,当X栈为空时,就不能在后退了.

如下图所示

|c |  |  |  
|b |  |  | 
|a |  |  |
|__|  |__|


X栈    Y栈

点击了后退按钮,将c页面存储到了Y栈中.此时显示的是b页面

|  |  |  |  
|b |  |  | 
|a |  |c |
|__|  |__|


X栈    Y栈

点击了前进按钮,将c从Y栈中取出,放入X栈中,此时显示的是c页面

|c |  |  |  
|b |  |  | 
|a |  |  |
|__|  |__|


X栈    Y栈

代码实现如下:

public class BrowserStack {
    //前进栈froward
    private ArrayStack<String> forwardStack = new ArrayStack<>();
    //后退栈
    private ArrayStack<String> backStack = new ArrayStack<>();

    private String currentPage;

    public void open(String url) {
        this.currentPage = url;
        forwardStack.push(url);
        System.out.println("open forwardStack:" + forwardStack);
    }

    /**
     * 后退操作
     * f：a b
     * b: d c
     *
     * @return
     */
    public boolean goBack() {
        if (forwardStack.isEmpty()) {
            System.out.println("Not Go Back");
            return false;
        }
        //将当前页面加入后退栈中
        //前进栈移除此页面
        String pop = forwardStack.pop();
        backStack.push(pop);
        showUrl(forwardStack.peek(), "Back");
        System.out.println("backStack:" + backStack);
        System.out.println("forwardStack:" + forwardStack);
        return true;
    }

    /**
     * 前进操作
     * F:a b
     * B:c
     * F:a b c
     *
     * @return
     */
    public boolean goForward() {
        if (backStack.isEmpty()) {
            System.out.println("Not Go Forward");
            return false;
        }
        String pop = backStack.pop();
        showUrl(pop, "Forward");
        forwardStack.push(pop);
        System.out.println("backStack:" + backStack);
        System.out.println("forwardStack:" + forwardStack);
        return true;
    }

    public void showUrl(String url, String p) {
        this.currentPage = url;
        System.out.println("showUrl = [" + url + "] " + p);
    }

    public void checkCurrentPage() {
        System.out.println("showUrl = [" + currentPage + "]");
    }

    public static void main(String[] args) {
        BrowserStack browser = new BrowserStack();
        browser.open("a");
        browser.open("b");
        browser.open("c");
        browser.checkCurrentPage();//c
        browser.goBack();//b
        browser.goBack();//a
        browser.goForward();//b
        browser.open("d");
        browser.goForward();//c
        browser.goBack();//d
        browser.goForward();//c
        browser.goBack();//d
        browser.goBack();//b
        browser.goBack();//a
        browser.goBack();//nul
        browser.checkCurrentPage();
        System.out.println();
    }
}

如何求栈中的最小栈是多少?

同样的原理我们使用两个栈,其中一个作为辅助栈,存储的是x - min

public class MinStack {
    /**
     * initialize your data structure here.
     */
    List<Long> array;

    //assist stack records min stack
    Stack<Long> assistStack;

    private long min;

    public MinStack() {
        array = new ArrayList<>();
        assistStack = new Stack<>();
    }

    //1 2 3 -1 -2 -4
    public void push(long x) {
        array.add(x);
        //
        if (assistStack.isEmpty()) {
            assistStack.push(0L);
            min = x;
        } else {
            System.out.println("x = [" + x + "]" + ",min = [" + min + "]" + "data = [" + (x - min) + "]");
            assistStack.push(x - min);//如果x-min>0 则说明 最小的是min 如果<0
            if (x < min) {
                min = x;
            }
        }
    }

    public Long pop() {
        if (array.isEmpty()) return -1l;
        Long remove = array.remove(array.size() - 1);
        Long pop = assistStack.pop();
        if (pop < 0) {
            min = min - pop;
        }
        System.out.println("min:" + min + " pop:" + pop);
        return remove;
    }

    public Long top() {
        if (array.isEmpty()) return -1l;
        return array.get(array.size() - 1);
    }

    public Long getMin() {
        return min;
    }
}

队列 queue FIFO

队列是先进先出的结构,可以理解为队列是两端开口的,栈是一端开口的,队列从一端进入另一段取出,栈只能从一端进入,同一端取出.

可以理解队列是排队买票,先来的先买,后来的后买,不允许插队.队列和栈一样只有两个操作,入队和出队操作,队尾入队,队头出队.

理解了栈,队列就更容易理解了,我们使用数组来对队列的实现代码如下:

import datastructure.array.Array;

/**
 * 动态队列结构
 *
 * @param <E>
 */
public class ArrayQueue<E> implements Queue<E> {
    private Array<E> array;

    public ArrayQueue(int capacity) {
        array = new Array<>(capacity);
    }

    public ArrayQueue() {
        this(10);
    }

    @Override
    public void enqueue(E e) {
        array.addLast(e);
    }

    /**
     * 每次移除的是数组的第一个，会导致所有数据的移动 性能低效
     */
    @Override
    public E dequeue() {
        if (isEmpty()) return null;
        return array.removeFirst();
    }

    @Override
    public boolean isEmpty() {
        return array.isEmpty();
    }

    @Override
    public int size() {
        return array.getSize();
    }

    @Override
    public E getTopQueue() {
        return array.get(0);
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append("Queue: \n");
        res.append("top: ");
        for (int i = 0; i < size(); i++) {
            res.append(array.get(i));
            if (i < size() - 1) {
                res.append(", ");
            }
        }
        return res.toString();
    }

    public static void main(String[] args) {
//        ArrayQueue<Integer> arrayQueue = new ArrayQueue<Integer>();
//        for (int i = 0; i < 6; i++) {
//            arrayQueue.enqueue(i);
//        }
//        System.out.println(arrayQueue);
//        arrayQueue.dequeue();
//        System.out.println(arrayQueue);
//        arrayQueue.enqueue(7);
//        System.out.println(arrayQueue);
//        arrayQueue.dequeue();
//        System.out.println(arrayQueue);
        System.out.println("求余："+1%2);
    }
}

上述队列的实现不知道大家有没有看出一个问题,在出队的时候需要移除数组的第0个元素,这个会导致,从第0个元素之后的所有的元素都要往前移动1位,出队的时间复杂度为O(n),如何优化出队操作呢? 使用循环队列.

循环队列

图片来自-极客时间

如上图所示,我们通过head来标记队头,tail来标记队尾,当head==tail时队列为空.当(tail+1)%length == head时队列满了.循环队列会浪费1个存储空间

循环队列的实现代码如下:

求余公式:a%b = a-(int)(a/b)*b

/**
 * 循环队列
 *
 * @param <E>
 */
public class LoopQueue<E> implements Queue<E> {
    private E[] array;

    private int size;

    //标记队头
    private int front;
    //标记队尾
    private int tail;

    public LoopQueue(int capacity) {
        array = (E[]) new Object[capacity + 1];//容器的大小要多申请一个空间 因为循环队列需要有一个额外的空间占用 否则无法判断队列是否满了
        size = 0;
        front = 0;
        tail = 0;
    }

    public LoopQueue() {
        this(10);
    }

    public int getCapacity() {
        return array.length - 1;
    }

    @Override
    public void enqueue(E e) {
        //首先判断队列容器是否满了？如果tail的下一个等于front则表示队列已经满了
        if ((tail + 1) % array.length == front) {
            //进行扩容操作
            resize(getCapacity() * 2);
        }
        array[tail] = e;
        tail = (tail + 1) % array.length;
        size++;
    }

    /**
     * 对数组进行扩容和缩容
     *
     * @param capacity 大小
     */
    private void resize(int capacity) {
        E[] newData = (E[]) new Object[capacity + 1];//同样我们需要预留一个空间来判断队列是否满了

        for (int i = 0; i < size; i++) {
            newData[i] = array[(i + front) % array.length];
        }
        //优化循环 每次循环
//        for (int i = front, j = 0; i != tail; i = (i + 1) % array.length, j++) {
//            newData[j] = array[i];
//        }
        array = newData;
        front = 0;
        tail = size;
    }

    @Override
    public E dequeue() {
        if (isEmpty()) {
            throw new IllegalArgumentException("LoopQueue is Empty!");
        }
        E res = array[front];
        array[front] = null;
        front = (front + 1) % array.length;
        size--;
        if (size == getCapacity() / 4 && getCapacity() / 2 != 0) {
            //缩容
            resize(getCapacity() / 2);
        }
        return res;
    }

    @Override
    public boolean isEmpty() {
        return front == tail;
    }

    @Override
    public int size() {
        return array.length - 1;//注意要减掉占用的一个空间的大小
    }

    @Override
    public E getTopQueue() {
        return array[front];//查看队头数据
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append(String.format("LoopQueue:size:%d,capacity:%d\n", size, getCapacity()));
        builder.append("front:");
        for (int i = front; i != tail; i = (i + 1) % array.length) {
            builder.append(array[i]);
            if ((i + 1) % array.length != tail)
                builder.append(", ");
        }
//        for (int i = 0; i < array.length; i++) {
//            builder.append(array[i]);
//            if (i<array.length-1)
//                builder.append(", ");
//        }
        builder.append(" tail");
        return builder.toString();
    }

    public static void main(String[] args) {
        LoopQueue<Integer> queue = new LoopQueue<Integer>(5);
        for (int i = 0; i < 10; i++) {
            queue.enqueue(i);
            System.out.println(queue);

            if (i % 3 == 2) {
                queue.dequeue();
                System.out.println(queue);
            }
        }
    }
}

我们可以对比一下两个队列的运行时间:

// 测试使用q运行opCount个enqueueu和dequeue操作所需要的时间，单位：秒
    private static double testQueue(Queue<Integer> q, int opCount) {

        long startTime = System.nanoTime();

        Random random = new Random();
        for (int i = 0; i < opCount; i++)
            q.enqueue(random.nextInt(Integer.MAX_VALUE));
        for (int i = 0; i < opCount; i++)
            q.dequeue();

        long endTime = System.nanoTime();

        return (endTime - startTime) / 1000000000.0;
    }

    public static void main(String[] args) {

        int opCount = 100000;

        ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();
        double time1 = testQueue(arrayQueue, opCount);
        System.out.println("ArrayQueue, time: " + time1 + " s");

        LoopQueue<Integer> loopQueue = new LoopQueue<>();
        double time2 = testQueue(loopQueue, opCount);
        System.out.println("LoopQueue, time: " + time2 + " s");
    }
}

输出结果如下:很明显循环队列的性能要高于普通的队列.

ArrayQueue, time: 3.089252806 s
LoopQueue, time: 0.015925464 s

小结

队列在Java中应用广泛,如阻塞队列和并发队列. 这些队列实现较为复杂我会在后面进行讲解.

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2019-09-27，如有侵权请联系 cloudcommunity@tencent.com 删除

c 语言

编程算法

本文分享自 Android研究院微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

c 语言

编程算法

登录后参与评论

0 条评论

热度