专栏首页极客慕白的成长之路算法学习之栈与队列

算法学习之栈与队列

算法学习之队列

一、栈 Stack

0x1 数组的子集

  • 栈也是一种线性结构
  • 相比数组,栈对应的操作是数组的子集
  • 只能从一端添加元素,也只能从一端取出元素
  • 这一端称为栈顶
  • 栈是一种后进先出的数据结构
    • Last In First Out (LIFO)
  • 在计算机的世界里,栈拥有着不可思议的作用

0x2 栈的应用

  • 无处不在的Undo操作(撤销)
  • 程序调用的系统栈
  • 括号匹配 - 编译器
//给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

Code:
import java.util.Stack;

class Solution {

    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{
                if(stack.isEmpty())
                    return false;

                char topChar = stack.pop();
                if(c == ')' && topChar != '(')
                    return false;
                if(c == ']' && topChar != '[')
                    return false;
                if(c == '}' && topChar != '{')
                    return false;
            }
        }
        return stack.isEmpty();
    }


//测试类:
    public static void main(String[] args) {

        System.out.println((new Solution()).isValid("()[]{}"));
        System.out.println((new Solution()).isValid("([)]"));
    }
}

0x3 栈的实现

Stack<E> void push(E) //入栈 E pop() //出栈 E peek() //查看 int getSize() //长度 boolean isEmpty() //是否为空

1234567

Stack<E>void push(E) //入栈E pop()  //出栈E peek()  //查看int getSize()  //长度boolean isEmpty()  //是否为空

二、队列 Queue

0x1 站队

  • 队列也是一种线性结构
  • 相比数组,队列对应的操作是数组的子集
  • 只能从一端(队尾)添加元素,只能从另一端(队首)取出元素
  • 队列是一种先进先出的数据结构(先到先得) FIFO

0x2 队列的实现

Interface Queue<E> 
void enqueue(E) //入队
E dequeue()   //出队
E getFront()  //查看队首
int getSize()  //长度
boolean isEmpty()  //是否为空

0x3 数组队列

public class ArrayQueue<E> implements Queue<E> {

    private Array<E> array;

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

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

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

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

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

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

    @Override
    public E dequeue(){
        return array.removeFirst();
    }

    @Override
    public E getFront(){
        return array.getFirst();
    }

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

    public static void main(String[] args) {

        ArrayQueue<Integer> queue = new ArrayQueue<>();
        for(int i = 0 ; i < 10 ; i ++){
            queue.enqueue(i);
            System.out.println(queue);
            if(i % 3 == 2){
                queue.dequeue();
                System.out.println(queue);
            }
        }
    }
}

0x4 循环队列

数组队列的实现出队的操作的复杂度是O(n),为了使得效率更高,这里编写循环队列。底层的实现仍然是数组,此时复杂度是O(1)。

public class LoopQueue<E> implements Queue<E> {

    private E[] data;
    private int front, tail;
    private int size;  // 有兴趣的同学,在完成这一章后,可以思考一下:
                       // LoopQueue中不声明size,如何完成所有的逻辑?
                       // 这个问题可能会比大家想象的要难一点点:)

    public LoopQueue(int capacity){
        data = (E[])new Object[capacity + 1];
        front = 0;
        tail = 0;
        size = 0;
    }

    public LoopQueue(){
        this(10);
    }

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

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

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

    @Override
    public void enqueue(E e){

        if((tail + 1) % data.length == front)
            resize(getCapacity() * 2);

        data[tail] = e;
        tail = (tail + 1) % data.length;
        size ++;
    }

    @Override
    public E dequeue(){

        if(isEmpty())
            throw new IllegalArgumentException("Cannot dequeue from an empty queue.");

        E ret = data[front];
        data[front] = null;
        front = (front + 1) % data.length;
        size --;
        if(size == getCapacity() / 4 && getCapacity() / 2 != 0)
            resize(getCapacity() / 2);
        return ret;
    }

    @Override
    public E getFront(){
        if(isEmpty())
            throw new IllegalArgumentException("Queue is empty.");
        return data[front];
    }

    private void resize(int newCapacity){

        E[] newData = (E[])new Object[newCapacity + 1];
        for(int i = 0 ; i < size ; i ++)
            newData[i] = data[(i + front) % data.length];

        data = newData;
        front = 0;
        tail = size;
    }

    @Override
    public String toString(){

        StringBuilder res = new StringBuilder();
        res.append(String.format("Queue: size = %d , capacity = %d\n", size, getCapacity()));
        res.append("front [");
        for(int i = front ; i != tail ; i = (i + 1) % data.length){
            res.append(data[i]);
            if((i + 1) % data.length != tail)
                res.append(", ");
        }
        res.append("] tail");
        return res.toString();
    }

    public static void main(String[] args){

        LoopQueue<Integer> queue = new LoopQueue<>();
        for(int i = 0 ; i < 10 ; i ++){
            queue.enqueue(i);
            System.out.println(queue);

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • C++上机考试试题解析

    慕白
  • ACM札记之一

    输入n(n<=100)个整数,按照绝对值从大到小排序后输出。题目保证对于每一个测试实例,所有的数的绝对值都不相等。

    慕白
  • Markdown编辑器 与 Crayon Syntax Highlighter 组合中代码转义问题

    慕白
  • (70) 原子变量和CAS / 计算机程序的思维逻辑

    从本节开始,我们探讨Java并发工具包java.util.concurrent中的内容,本节先介绍最基本的原子变量及其背后的原理和思维。 原子变量 什么是原子...

    swiftma
  • Java打飞机小游戏(附完整源码)

    技术源于分享,所以今天抽空把自己之前用java做过的小游戏整理贴出来给大家参考学习。java确实不适合写桌面应用,这里只是通过这个游戏让大家理解oop面向对象编...

    Java团长
  • 数据结构基础-栈和队列

    栈是一个有序线性表,只能在表的一端(成为栈顶,top)执行插入和删除操作。最后插入的元素将第一个被删除。所以栈也称为后进先出(Last In First Out...

    1025645
  • 挑战程序竞赛系列(90):3.6凸包(1)

    挑战程序竞赛系列(90):3.6凸包(1) 传送门:POJ 2187: Beauty Contest 题意: 平面上有N个牧场。i号牧场的位置在格点(xi,y...

    用户1147447
  • 挑战程序竞赛系列(91):3.6凸包(2)

    挑战程序竞赛系列(91):3.6凸包(2) 传送门:POJ 1113: Wall 题意参考hankcs: http://www.hankcs.com/pro...

    用户1147447
  • MVVM架构之自动增删改的极简RecycleView的实现

    介绍图 先上个源代码的链接:https://github.com/whenSunSet/MVVMRecycleView RecycleView是Google替...

    何时夕
  • 挑战程序竞赛系列(94):3.6凸包(5)

    挑战程序竞赛系列(94):3.6凸包(5) 传送门:POJ 2079: Triangle 题意: 求三个点构成的最大三角形面积。 思路: 可以证明,三点构...

    用户1147447

扫码关注云+社区

领取腾讯云代金券