数据结构(三)栈和队列

栈是一种线性结构,相比数组,栈对应的操作是数组的子集,栈只能从一端添加元素,也只能从一端取出元素,这一端称为栈顶。栈是一种后进先出的数据结构,从下图我们可以看出,先入栈的元素在栈底,得等到它之后的所有元素都出去,它才能出栈,反而最后入栈的元素可以先出栈。

1538361372515527.png

栈的应用:

  • 撤销操作

  • 程序调用的系统栈

栈的实现:

栈的实现很简单,我们需要实现5个操作即可,void push(E)-入栈操作、E pop()-出栈操作、E peek()-查看栈顶元素、int getSize()-查看栈里一共有多少元素、boolean isEmpty()-判断栈是否为空;  下面栈代码的实现用了上篇文章中写的数组,为了获取栈顶元素,我们需要在上篇数组的代码中添加两个方法,获取数组最后一个元素(即栈顶)和第一个元素(栈底),具体方法如下:

//获取数组最后一个元素
public E getLast(){
    return get(size -1);
}
//获取数组第一个元素
public E getFirst(){
    return get(0);
}

我们先来一个栈的接口,最后实现栈:

Stack.java:

package com.wjy329;

/**
 * @Author wjy329
 * @Time 2018/10/19:27 PM
 * @description
 */
public interface Stack<E> {
    //获取栈中元素个数
    int getSize();
    //判断栈是否为空
    boolean isEmpty();
    //入栈
    void push(E e);
    //出栈
    E pop();
    //查看栈顶元素
    E peek();
}

ArrayStack.java:

package com.wjy329;
/**
 * @Author wjy329
 * @Time 2018/10/19:30 PM
 * @description
 */

public class ArrayStack<E> implements Stack<E>{

    Array<E> array;

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

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

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

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

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

    @Override
    public E pop() {
        return array.delLast();
    }

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

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

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

文章一开始就说了两个栈的应用,在我们面试中,经常用到的栈的应有就有一个是括号的匹配,下面给出代码:

package com.wjy329;

import java.util.Stack;

/**
 * @Author wjy329
 * @Time 2018/10/110:07 PM
 * @description
 */

public 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();
    }
}

括号匹配的思路也很简单:就是将给定的字符串依次取出如果是左括号则入栈,右括号则对括号进行匹配。

队列

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

image.png

队列的实现:

和栈的实现类似,同样我们需要5个方法,void enqueue(E)-入队、E dequeue()-出队、E getFront()-查看队首元素、int getSize()-查看队列中的元素个数、boolean isEmpty()-判断队列是否为空;

package com.wjy329;
/**
 * @Author wjy329
 * @Time 2018/10/110:44 PM
 * @description
 */

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

    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();
    }

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

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

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

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append("Queue:");
        res.append("[");
        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();
    }
}

循环队列:

上述数组队列当进行删除队首元素时,其后面的元素需要往前移,时间复杂度为O(n),循环队列不需要往前移动,当后面空间满时,可以往前在寻找空间,循环队列可以通过(tail+1)%c == front 来判断队列是否已满。tail-队尾、c-队列容量、front-队首;

package com.wjy329;
/**
 * @Author wjy329
 * @Time 2018/10/29:12 AM
 * @description
 */

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

    private E[] data;
    private int front,tail;
    private int 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 int getSize() {
        return size;
    }

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

    @Override
    public void enqueue(E e) {
        if((tail + 1) % data.length == front){
            resize(getCapacity() * 2);
        }
        data[tail] = e;
        tail = (tail+1)%data.length;
        size++;
    }

    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 E dequeue() {
        if(isEmpty()){
            throw  new IllegalArgumentException("队列为空,不能出队");
        }
        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("队列为空");
        }
        return data[front];
    }

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append("Queue:");
        res.append("[");
        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();
    }

}

1 Comment

  1. […] 数据结构(三)栈和队列 […]

    回复

Leave a Reply