Java教程

数据结构----栈和队列

本文主要是介绍数据结构----栈和队列,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

栈与队列

栈的定义

1.栈(stack)是仅限表尾进行插入和删除的线性表。也被称为先进后出的线性表。其本身就是一个特殊的线性表,其数据元素仍具有线性关系。
2.栈的插入操作叫进栈也叫入栈(push);删除操作叫出栈或者弹栈(pop),不含任何元素的栈叫空栈。
举个例子
①1,2,3依次进栈,然后依次弹栈得到的新串为3,2,1
②1进,1出,2进,2出,3进,3出,新串为1,2,3
③1进,2进,2出,3进,3出,1出,新串为2,3,1
3.由于栈的进出操作都没有任何循环语句,都是在栈顶进行操作,所有其时间复杂度为O(1)。
4.栈同样可以使用顺序存储和链式存储实现。
在这里插入图片描述

ArrayStack栈的顺序存储

由于栈也是线性表,所以其顺序存储实际上也是在ArrayList基础上实现。
具体接口要实现的方法如下:

public interface Stack<E> extends Iterable<E>{
    public int size();
    public boolean isEmpty();
    public void push(E element);//进栈
    public E pop();//出栈
    public E peek();//判断栈顶元素
    public void clear();
}

栈的线性存储实现:

public class ArrayStack<E> implements Stack<E> {
    private ArrayList<E> list;//栈的内部其实就是有线性表实现
    public ArrayStack(){//创建一个默认容量的栈
        list = new ArrayList<E>();
    }
    public ArrayStack(int capacity){//创建一个指定容量的栈
        list = new ArrayList<>(capacity);
    }
    @Override
    public int size() {
        return list.size();
    }

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

    @Override
    public void push(E element) {
        list.add(element);
    }

    @Override
    public E pop() {
       return list.remove(list.size() - 1);
    }

    @Override
    public E peek() {
        return list.get(list.size() - 1);
    }

    @Override
    public void clear() {
        list.clear();
    }

    @Override
    public Iterator<E> iterator() {
        return list.iterator();
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder(String.format("ArrayStack:%d/%d[",list.size(),list.getCapacity()));
        if (isEmpty()) {
            sb.append(']');
        }
        else{
            for (int i = 0; i < list.size();i++){
                sb.append(list.get(i));
                if (i != list.size() - 1){
                    sb.append(',');
                }else {
                    sb.append(']');
                }
            }
        }
        return sb.toString();
    }
}

应用: 十进制转十六进制的问题(利用栈解决):

public class DecToHex {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);//获取用户输入
        System.out.println("请输入:");
        int number  = scanner.nextInt();
        ArrayStack<Character> stack = new ArrayStack<>();//创建一个栈存储余数,作为进栈的数据元素
        //计算余数
        int mod = 0;
        while (number != 0) {
            mod = number % 16;
            //获取余数  0~9 用数字表示,10~15用A~F表示
            // '0' + mod表示字符0往后第mod个字符的编码,表示以字符表示的数字
            // 'A' + mod - 10表示字符A往后mod-10个字符的编码,表示以编码表示的字母,这里用作16进制计数
            if (mod < 10) {
                stack.push((char) ('0' + mod));
            }else {
                stack.push((char) ('A' + mod - 10));
            }
            number /= 16;
        }
        while (!stack.isEmpty()){
            System.out.print(stack.pop());
        }
    }
}
这篇关于数据结构----栈和队列的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!