欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【数据结构与算法】栈和队列

程序员文章站 2022-03-13 10:37:23
...

1. 栈(stack)

  • 栈是一种线性结构
  • 栈是一种后进先出的数据结构(LIFO)

Stack<> :下压

返回值类型 方法 功能
void push(E) 压入元素到栈顶
E pop() 弹出栈顶元素
E peek() 取出栈顶元素
int size() 栈的元素个数
boolean isEmpty() 栈是否为空

经典例题:括号匹配

package com.zhan;


import java.util.Scanner;
import java.util.Stack;

/**
 * 括号匹配
 *
 * @author boyi on 2019/11/28
 */
public class Kuohao {

    static boolean isValid(String st) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < st.length(); i++) { //遍历
            char ch = st.charAt(i);
            if (ch == '{' || ch == '[' || ch == '(') {
                stack.push(ch);  //如果是左括号就压入栈中
            } else {
                if (stack.isEmpty()) {  //如果栈为空了,说明左括号少了,匹配失败。
                    return false;
                }
                char ch1 = stack.pop(); //弹出栈顶元素并取到该值
                if (ch1 == '}' && ch != '{') { //如果不能匹配就结束
                    return false;
                }
                if (ch1 == ']' && ch != '[') {
                    return false;
                }
                if (ch1 == ')' && ch != '(') {
                    return false;
                }
            }
        }
        return stack.isEmpty(); //注意:该处必须还要判栈是否为空,才能完全匹配上。
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String st = sc.next();
        System.out.println(isValid(st));
    }
}

2.队列(Queue)

  • 是一种线性结构
  • 是一种先进先出的数据结构
返回值类型 方法 功能
void enqueue(E) 添加一个元素
E dequeue() 删除元素
int size() 队列的元素个数
boolean isEmpty() 队列是否为空

action: dequeue()方法是o(n)复杂度

3.循环队列

【数据结构与算法】栈和队列【数据结构与算法】栈和队列【数据结构与算法】栈和队列