数据结构栈以及Java代码实现

太过爱你忘了你带给我的痛 2022-06-12 04:08 185阅读 0赞

## 1. 栈 ##

栈是一种特殊的线性表，是操作受限的线性表  
栈的定义和特点

*  定义：限定仅在表尾进行插入或删除操作的线性表，表尾—栈顶，表头—栈底，不含元素的空表称空栈
 *  特点：先进后出（FILO）或后进先出（LIFO）

![这里写图片描述][1358296549_6909.png]

## 2. 顺序栈 ##

![这里写图片描述][1358296803_1759.png]

/** * Stack * 栈 * Created by heqianqian on 2017/7/14. */
    public interface Stack<T> {
        /** * 清空堆栈 */
        public void clear();
    
        /** * 入栈 * * @param obj 入栈的元素 */
        public void push(T obj);
    
        /** * 出栈 * * @return 出栈的结果 */
        public T pop();
    
        /** * 判断是否为空 * * @return 是否为空 */
        public boolean isEmpty();
    
        /** * 求元素的个数 * * @return 元素的个数 */
        public int size();
    
        /** * 取栈顶元素 * * @return 栈顶元素 */
        public T peek();
    }

/** * ArrayStack * 顺序数组实现栈 * Created by heqianqian on 2017/7/14. */
    public class ArrayStack<T> implements Stack<T> {
    
        private static final int DEFAUL_SIZE = 10;
    
        private T[] stack;
    
        private int top;
    
        @SuppressWarnings("unchecked")
        public ArrayStack() {
            stack = (T[]) new Object[DEFAUL_SIZE];
            top = 0;
        }
    
        @Override
        public void clear() {
            top = 0;
        }
    
        @Override
        public void push(T obj) {
            if (top == DEFAUL_SIZE) {
                expand();
            }
            stack[top++] = obj;
        }
    
        @SuppressWarnings("unchecked")
        private void expand() {
            T[] s = (T[]) new Object[DEFAUL_SIZE * 2];
            System.arraycopy(stack, 0, s, 0, top);
            stack = s;
        }
    
        @Override
        public T pop() {
            return stack[--top];
        }
    
        @Override
        public boolean isEmpty() {
            return top == 0;
        }
    
        @Override
        public int size() {
            return top;
        }
    
        @Override
        public T peek() {
            return top > 0 ? stack[top - 1] : null;
        }
    }

## 3.链式栈 ##

![这里写图片描述][1358297368_5846.png]

/** * Node * Created by heqianqian on 2017/7/14. */
    public class Node<T> {
    
        public Node<T> next;
    
        public T data;
    
        public Node(T data) {
            this.data = data;
            next = null;
        }
    
        @Override
        public String toString() {
            return data.toString();
        }
    }

/** * LinkedStack * Created by heqianqian on 2017/7/14. */
    public class LinkedStack<T> implements Stack<T> {
    
        private Node<T> head;
    
        private Node<T> top;
    
        private int size;
    
        public LinkedStack() {
            size = 0;
            head = new Node<T>(null);
            top = head;
        }
    
        @Override
        public void clear() {
            size = 0;
            head.next = null;
            top = head;
        }
    
        @Override
        public void push(T obj) {
            Node<T> node = new Node<T>(obj);
            top.next = node;
            top = node;
            size++;
        }
    
        @Override
        public T pop() {
            Node<T> node = head;
            for (int i = 0; i < size - 1; i++) {
                node = node.next;
            }
            T data = node.next.data;
            node.next = node.next.next;
            size--;
            return data;
        }
    
        @Override
        public boolean isEmpty() {
            return size == 0;
        }
    
        @Override
        public int size() {
            return size;
        }
    
        @Override
        public T peek() {
            return top.data;
        }
    
        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append("[");
            Node<T> temp = head.next;
            for (int i = 0; i < size - 1; i++) {
                sb.append(temp.data.toString()).append(",");
                temp = temp.next;
            }
            sb.append(temp.data.toString()).append("]");
            return sb.toString();
        }
    }

[1358296549_6909.png]: https://img-my.csdn.net/uploads/201301/16/1358296549_6909.png
[1358296803_1759.png]: https://img-my.csdn.net/uploads/201301/16/1358296803_1759.png
[1358297368_5846.png]: https://img-my.csdn.net/uploads/201301/16/1358297368_5846.png