数据结构——栈【基于数组实现和链表实现】

Love The Way You Lie 2022-05-09 00:06 257阅读 0赞

## 栈Stack: ##

栈和数组一样，也是一种线性结构，相比数组，栈对用的操作是数组的子集，只能从一端添加元素，从同一端取出元素，这一端为栈顶，栈是一种后进后出的数据结构，Last in First Out (LIFO)

### 栈的应用: ###

①undo(撤销)---编辑器        ②系统调用栈(递归)---操作系统       ③括号匹配---编译器

## 栈的实现： ##

public interface Stack<E> {
        void push(E e);
        E pop();
        E peek();
        int getSize();
        boolean isEmpty();
    }

### 基于数组实现栈 ###

Array类

public class Array<E> {
        private E[] data;
        private int size;
    
        public Array(int capacity) {
            data =(E[]) new Object[capacity];
            size = 0;
        }
    
        public Array() {
            //空参数构造默认的capacity为10
            this(10);
        }
    
        //获取数组元素中元素个数
        public int getSize() {
            return this.size;
        }
    
        //获得数组容量
        public int getCapacity() {
            return data.length;
        }
    
        //判断数组是否为空
        public boolean isEmpty() {
            return size == 0;
        }
    
        //向数组尾部添加元素
        public void addLast(E e) {
            add(size, e);
        }
    
        //向数组头部添加元素
        public void addFirst(E e) {
            add(0, e);
        }
    
        //向数组中index索引处插入某个元素
        public void add(int index, E e) {
            //检查数组中是否能容纳新的元素
            if (size == data.length)
                System.out.println("数组需要扩容");
                resize(data.length * 2);
            if (index < 0 || index > size)
                throw new IllegalArgumentException("index非法");
            //移动元素
            for (int i = size - 1; i >= index; i--) {
                //后一个索引赋上前一个索引的元素，即每一个元素都向后挪了一个位置
                data[i + 1] = data[i];
            }
            data[index] = e;
            size++;
        }
    
        //获取数组中的值
        E get(int index) {
            if (index < 0 || index >= size)
                throw new IllegalArgumentException("index非法");
            return data[index];
        }
    
        //获取数组中的值
        E getLast() {
            return get(size - 1);
        }
    
        //获取数组中的值
        E getFirst() {
            return get(0);
        }
    
        //更新数组的值
        E update(int index, E e) {
            E oldValue = get(index);
            data[index] = e;
            return oldValue;
        }
    
        //数组中是否含有某元素,有返回true,无返回false
        public boolean contains(E e) {
            for (int i = 0; i < size; i++) {
                if (data[i].equals(e))
                    return true;
            }
            return false;
        }
    
        //查找数组中的某个元素，找到返回索引，找不到返回-1
        public int find(E e) {
            for (int i = 0; i < size; i++) {
                if (data[i].equals(e)) {
                    return i;
                }
            }
            return -1;
        }
    
        //删除数组中某个元素
        public E remove(int index) {
            if (index < 0 || index >= size) {
                throw new IllegalArgumentException("index非法");
            }
            E ret = data[index];
            for (int i = index + 1; i < size; i++) {
                data[i - 1] = data[i];
            }
            size--;
            data[size] = null;
            if(size == data.length / 4 && data.length / 2 != 0 )
                resize(data.length /2);
            return ret;
        }
    
        public void removeFirst() {
            remove(0);
        }
    
        public E removeLast() {
            return remove(size - 1);
        }
    
        //删除指定元素,如果有则删除,删除成功返回true,删除失败返回false
        public boolean removeElement(E e) {
            int index = find(e);
            if(index != -1){
                remove(index);
                return true;
            }
            return false;
        }
    
        //实现动态数组,动态扩容 size==data.lenngth 扩容2倍 和 缩容 size == data.length / 2
        private void resize(int newCapacity){
            //创建一个新的数组
            E[] newData = (E[]) new Object[newCapacity];
            //把原来的元素迁移到新的数组中
            for(int i = 0 ; i < size ; i++){
                newData[i] = data[i];
            }
            data = newData;
        }
    
        //打印数组中的元素
        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append(String.format("Array: size = %d , capacity = %d\n", size, data.length));
            //显示[1,2,3,4,5]
            sb.append("[");
            for (int i = 0; i < size; i++) {
                sb.append(data[i]);
                if (i != size - 1) {
                    sb.append(", ");
                }
            }
            sb.append("]");
            return sb.toString();
        }
    
    
    }

利用上面的动态Array实现栈

public class ArrayStack<E> implements Stack<E>{
        private Array<E> array;
    
        public ArrayStack(int capacity){
            array = new Array<>(capacity);
        }
    
        public ArrayStack(){
            array = new Array<>();
        }
        @Override
        public void push(E e) {
            array.addLast(e);
        }
    
        @Override
        public E pop() {
            return array.removeLast();
        }
    
        @Override
        public E peek() {
            return  array.getLast();
        }
    
        @Override
        public int getSize() {
            return array.getSize();
        }
    
        @Override
        public boolean isEmpty() {
            return array.isEmpty();
        }
    
        public int getCapacity(){
            return array.getCapacity();
        }
    
        @Override
        public String toString(){
            StringBuilder sb = new StringBuilder("Stack:  [");
            for(int i = 0 ; i< array.getSize() ; i++){
                sb.append(array.get(i));
                if(i != array.getSize()  -1){
                    sb.append(", ");
                }
            }
            sb.append("]  top");
            return sb.toString();
        }
    }

基于数组的栈，测试类

public class ArrayStackTest {
        public static void main(String[] args) {
            ArrayStack<Integer> stack = new ArrayStack<>();
            for(int i = 0 ; i < 5 ; i++){
                stack.push(i);
                System.out.println(stack);
            }
            Integer i = stack.pop();
            System.out.println(stack+"   i:"+ i);
        }
    }

![70][]

### 基于链表实现栈 ###

LinkedList

package cn.itcats.stack;
    
    public class LinkedList<E> {
    
        //创建内部类Node
        private class Node{
            public E e;
            public Node next;
    
            public Node(E e , Node next){
                this.e = e ;
                this.next = next;
            }
    
            public Node(E e){
                this(e,null);
            }
    
            public Node(){
                this(null,null);
            }
    
            @Override
            public String toString(){
                return e.toString();
            }
    
        }
        //为链表设置虚拟头结点,则不需要对头结点进行特殊处理
        private Node dummyHead;
        private int size;
    
        public LinkedList(){
            dummyHead = new Node(null,null);
            size = 0;
        }
    
        //获得链表中元素个数
        public int getSize(){
            return size;
        }
    
        //判断链表是否为空
        public boolean isEmpty(){
            return size == 0 ;
        }
    
        //在链表的index位置添加新元素e
        public void add(int index ,E e){
            //对index进行判断
            if(index < 0 && index > size){
                throw new IllegalArgumentException("index不合法");
            }
                Node prev = dummyHead;
                //当遍历到插入索引的前一个索引
                for(int i = 0 ;i < index ; i++){
                    //prev指向下一个元素(index)
                    prev = prev.next;
                }
    //            Node node = new Node(e);
    //            node.next = prev.next;
    //            prev.next = node;
                prev.next = new Node(e,prev.next);
                size ++ ;
            }
    
        //获取链表中指定"索引"的元素,所谓索引,只不过是遍历位置的次数而已
        public E get(int index){
            if(index < 0 || index >= size){
                throw new IllegalArgumentException("index不合法");
            }
            //从dummyHead的下一个节点遍历
            Node cur = dummyHead.next;
            for(int i = 0 ; i < index ; i++){
                cur = cur.next;
            }
            return cur.e;
        }
    
        //获取链表中的第一个元素
        public E getFirst(){
            return get(0);
        }
    
        //获取链表中的最后一个元素
        public E getLast(){
            return get(size-1);
        }
    
        //修改链表中第index个位置的元素为e
        public void set(int index, E e){
            if(index < 0 || index >= size){
                throw new IllegalArgumentException("index不合法");
            }
            //找到第index位置的元素
            Node cur = dummyHead.next;
            for(int i = 0 ; i < index ; i++){
                cur = cur.next;
            }
            cur.e = e;
        }
    
        //查找链表中是否存在元素e
        public boolean contains(E e){
            Node cur = dummyHead.next;
            while(cur != null){
                if(cur.e.equals(e)){
                    return true;
                }
                cur = cur.next;
            }
            return false;
        }
    
        /**
         * 在链表头部添加新的元素
         */
        public void addFirst(E e){
            add(0,e);
        }
    
        //在链表尾部添加元素
        public void addLast(E e){
            add(size,e);
        }
    
        //删除节点
        public E remove(int index){
            if(index < 0 || index >= size){
                throw new IllegalArgumentException("index不合法");
            }
            Node prev = dummyHead;
            for(int i = 0 ; i < index ;i++){
                //prev此时指向的是被删除节点的前一个位置
                prev = prev.next;
            }
            //需要被删除的节点
            Node removeNode = prev.next;
            prev.next = removeNode.next;
            removeNode.next = null;
            size --;
            return removeNode.e;
        }
    
        //从链表中删除第一个元素,返回删除的元素
        public E removeFirst(){
           return remove(0);
        }
    
        //从链表中删除最后一个元素,返回删除的元素
        public E removeLast(){
            return remove(size -1);
        }
    
    
        //遍历链表
        @Override
        public String toString(){
            StringBuilder sb = new StringBuilder();
            //for(Node cur = dummyHead.next ; cur != null ; cur = cur.next)
            Node cur = dummyHead.next ;
            while(cur != null){
                sb.append(cur+"-->");
                cur = cur.next;
            }
    
            sb.append("NULL");
            return sb.toString();
        }
    }

LinkedListStack

package cn.itcats.stack;
    
    public class LinkedListStack<E> implements Stack<E> {
        private LinkedList<E> list ;
        public LinkedListStack(){
            list = new LinkedList<>();
        }
    
        @Override
        public void push(E e) {
            list.addFirst(e);
        }
    
        @Override
        public E pop() {
            return list.removeFirst();
        }
    
        @Override
        public E peek() {
            return list.getFirst();
        }
    
        @Override
        public int getSize() {
            return list.getSize();
        }
    
        @Override
        public boolean isEmpty() {
            return list.isEmpty();
        }
    
        @Override
        public String toString(){
            StringBuilder sb = new StringBuilder("Stack: top  ");
            sb.append(list);
            return sb.toString();
        }
    
        public static void main(String[] args) {
            LinkedListStack<Integer> stack = new LinkedListStack();
            for(int i = 0 ; i < 5 ; i++){
                stack.push(i);
                System.out.println(stack);
            }
            Integer i = stack.pop();
            System.out.println(stack+"   i:"+ i);
        }
    }

[70]: /images/20220509/3ba5546700bb42dfb139454a99b70a3c.png