大话数据结构——栈和队列

本文在阅读大话数据结构这本书的基础上，结合java语言的特点，来理解栈和队列。

栈与队列的定义

栈是限定仅在表尾进行插入和删除操作的线性表。（类似弹夹中的子弹）
队列是只允许在一端进行插入操作、而在另一端进行删除操作的线性表。（类似等待客服电话排队）

栈

栈本身也是一种线性表，除了删除和添加改名为pop(弹)和push(压)，抽象功能没有特别的地方。需要注意一点是java的sdk继承vector实现的stack，相关操作使用synchronized，具有安全性。

栈的顺序存储结构(顺序栈)

/**
 * 基于数组实现的顺序栈
 * @param <E>
 */
public class Stack<E> {
    private Object[] data = null;
    private Object e;
    private int maxSize=0;
    private int top=-1;

    /**
     * 构造函数：根据给定的size初始化栈
     */
    Stack(){
        this(10);
    }

    public Stack(int initSize){
        if(initSize>=0){
            this.maxSize=initSize;
            data = new Object[initSize];
            top=-1;
        }else{
            throw new RuntimeException("初始化大小不能小于0"+initSize);
        }
    }

    //判断栈是否为空
    public boolean isEmpty(){
        return top == -1 ? true : false;
    }

    //元素进栈
    public boolean push(E e){
        if (top == maxSize-1){
            throw new RuntimeException("栈已满，元素无法入栈！");
        }else{
            data[++top]=e;
            return true;
        }
    }

    //查看栈顶元素
    public Object peek(){
        if(top==-1){
            throw new RuntimeException("栈为空！");
        }else{
            return data[top];
        }
    }

    //元素出栈
    public Object pop(){
        if(top==-1){
            throw new RuntimeException("栈为空！");
        }else{
            Object elem=data[top];
            data[top--]=null;
            return elem;
        }
    }

    //返回对象在堆栈中的位置，以1为基数
    public int search(E e){
        int i=top;
        while(top!=-1){
            if(peek()!=e){
                top--;
            }else{
                break;
            }
        }
        int result = top+1;
        top=i;
        return result;
    }
    //查看栈的大小
    public int getSize(){
        return top+1;
    }

    //清空栈
    public void clear(){
        Arrays.fill(data,null);
        top=-1;
    }

    public static void main(String[] args) {
        Stack<String> stack=new Stack<>();
        System.out.println("stack.maxSize="+stack.maxSize);
        System.out.println("stack.size="+stack.getSize());
        System.out.println("stack is empty?"+stack.isEmpty());
        stack.push("a");
        stack.push("b");
        stack.push("c");
        stack.push("d");
        stack.push("e");
        System.out.println("stack.size="+stack.getSize());
        System.out.println("stack is empty?"+stack.isEmpty());
        System.out.println(stack.pop());
        System.out.println(stack.peek());
        System.out.println(stack.pop());
        System.out.println("stack.size="+stack.getSize());
        System.out.println("stack is empty?"+stack.isEmpty());
        stack.clear();
        System.out.println("---------------after clear---------------");
        System.out.println("queue is empty?"+stack.isEmpty());
        System.out.println("queue.size="+stack.getSize());
    }

}

栈的链式存储结构（链栈）

/**
 * 基于链表实现的栈
 * @param <E>
 */
public class LinkStack<E> {
    private class Node{
        E e;
        Node next;
        public Node(E e,Node next){
            this.e=e;
            this.next=next;
        }
    }
    private Node top;
    private int size;

    public LinkStack(){
        top=null;
    }

    //当前栈大小
    public int getSize(){
        return size;
    }

    //判断是否为空
    public boolean isEmpty(){
        return size==0;
    }

    //入栈
    public boolean push(E e){
        top = new Node(e,top);
        size++;
        return true;
    }

    //查看栈顶元素但不删除
    public E peek(){
        if(isEmpty()){
            throw new RuntimeException("栈为空！");
        }else{
            return top.e;
        }
    }

    //出栈
    public E pop(){
        if (isEmpty()) {
            throw new RuntimeException("栈为空！");
        }else{
            Node elem=top;
            top =top.next;
            elem.next=null;
            size--;
            return elem.e;
        }
    }

    //清空栈
    public void clear(){
        for(Node node=top;node!=null;){
            Node next=node.next;
            node.e=null;
            node.next=null;
            node=next;
        }
        size=0;
    }

    public static void main(String[] args) {
        LinkStack<String> linkStack=new LinkStack<>();
        System.out.println("linkStack.size = "+linkStack.getSize());
        System.out.println("stack is empty?"+linkStack.isEmpty());
        linkStack.push("a");
        linkStack.push("b");
        linkStack.push("c");
        linkStack.push("d");
        linkStack.push("e");
        System.out.println("stack.size="+linkStack.getSize());
        System.out.println("stack is empty?"+linkStack.isEmpty());
        System.out.println(linkStack.pop());
        System.out.println(linkStack.peek());
        System.out.println(linkStack.pop());
        System.out.println("stack.size="+linkStack.getSize());
        System.out.println("stack is empty?"+linkStack.isEmpty());
        linkStack.clear();
        System.out.println("------------after clear-------------");
        System.out.println("stack.size="+linkStack.getSize());
        System.out.println("stack is empty?"+linkStack.isEmpty());
    }
    
}

队列

队列本身也是一种线性表，不同的是插入只能是队尾，删除只能是队首。

队列的顺序存储结构

顺序队列

/**
 * 基于数组实现的队列
 * @param <E>
 */
public class Queue<E> {
    private Object[] data=null;
    private int maxSize;
    private int front;
    private int rear;

    //构造函数
    public Queue(){
        this(10);
    }

    public Queue(int initSize){
        if(initSize>=0){
            this.maxSize=initSize;
            data=new Object[initSize];
            front=rear=0;
        }else{
            throw new RuntimeException("初始化大小不能小于："+initSize);
        }
    }

    //判断是否为空
    public boolean isEmpty(){
        return rear==front?true:false;
    }

    //插入队列
    public boolean offer(E e){
        if(rear==maxSize){
            throw new RuntimeException("队列已满，无法插入新的元素！");
        }else{
            data[rear++]=e;
            return true;
        }
    }

    //返回队首元素，但不删除
    public Object peek(){
        if(isEmpty()){
            throw new RuntimeException("队列为空！");
        }else{
            return data[front];
        }
    }

    //出队
    public Object poll(){
        if (isEmpty()){
            throw new RuntimeException("队列为空！");
        }else{
            Object elem= data[front];
            data[front++]=null;
            return elem;
        }
    }

    //队列长度
    public int getSize(){
        return rear-front;
    }

    //清空队列
    public void clear(){
        Arrays.fill(data,null);
        rear=front=0;
    }

    public static void main(String[] args) {
        Queue<String> queue=new Queue<>();
        System.out.println("queue is empty:"+queue.isEmpty());
        System.out.println("queue.size="+queue.getSize());
        queue.offer("a");
        queue.offer("b");
        queue.offer("c");
        queue.offer("d");
        queue.offer("e");
        System.out.println("queue is empty:"+queue.isEmpty());
        System.out.println("queue.size="+queue.getSize());
        System.out.println(queue.poll());
        System.out.println(queue.peek());
        System.out.println(queue.poll());
        System.out.println("queue is empty:"+queue.isEmpty());
        System.out.println("queue.size="+queue.getSize());
        queue.clear();
        System.out.println("---------------after clear---------------");
        System.out.println("queue is empty:"+queue.isEmpty());
        System.out.println("queue.size="+queue.getSize());
    }

}

循环队列

/**
 * 基于数组实现的循环队列
 * @param <E>
 */
public class LoopQueue<E> {
    public Object[] data=null;
    private int maxSize;//队列容量
    private int rear;//队列尾，允许插入
    private int front;//队列头，允许删除
    private int size=0;//队列当前长度

    //构造队列
    public LoopQueue(){
        this(10);
    }

    public LoopQueue(int initSize){
        if(initSize>=0){
            this.maxSize=initSize;
            data=new Object[initSize];
            front=rear=0;
        }else{
            throw new RuntimeException("初始化大小不能小于0："+initSize);
        }
    }

    //判断是否为空
    public boolean isEmpty(){
        return size==0;
    }

    //队列插入元素
    public boolean offer(E e){
        if(size==maxSize){
            throw new RuntimeException("队列已满，无法插入新的元素！");
        }else{
            data[rear]=e;
            rear=(rear+1)%maxSize;//队尾指针+1
            size++;
            return true;
        }
    }

    //返回队首元素，但并不删除
    public Object peek(){
        if(isEmpty()){
            throw new RuntimeException("队列为空！");
        }else{
            return data[front];
        }
    }

    //出队
    public Object poll(){
        if(isEmpty()){
            throw new RuntimeException("队列为空！");
        }else{
            Object elem=data[front];
            data[front]=null;
            front=(front+1)%maxSize;//队首指针+1
            size--;
            return elem;
        }
    }

    //获取队列长度
    public int getSize(){
        return size;
    }

    //清空队列
    public void clear(){
        Arrays.fill(data,null);
        size=0;
        rear=front=0;
    }

    public static void main(String[] args) {
        LoopQueue<String> loopQueue=new LoopQueue<>();
        System.out.println("queue is empty:"+loopQueue.isEmpty());
        System.out.println("queue.size="+loopQueue.getSize());
        loopQueue.offer("a");
        loopQueue.offer("b");
        loopQueue.offer("c");
        loopQueue.offer("d");
        loopQueue.offer("e");
        System.out.println("queue is empty:"+loopQueue.isEmpty());
        System.out.println("queue.size="+loopQueue.getSize());
        System.out.println(loopQueue.poll());
        System.out.println(loopQueue.peek());
        System.out.println(loopQueue.poll());
        System.out.println("queue is empty:"+loopQueue.isEmpty());
        System.out.println("queue.size="+loopQueue.getSize());
        loopQueue.clear();
        System.out.println("---------------after clear---------------");
        System.out.println("queue is empty:"+loopQueue.isEmpty());
        System.out.println("queue.size="+loopQueue.getSize());
    }

}

队列的链式存储结构

public class LinkQueue<E> {
    //链式队列的节点
    private class Node{
        E e;
        Node next;
        public Node(){
        }
        public Node(E e,Node next){
            this.e=e;
            this.next=next;
        }
    }
    private Node front;//队列头，允许插入
    private Node rear;//队列尾，允许插入
    private int size;//队列当前长度

    //构造队列
    public LinkQueue(){
        Node node=new Node(null,null);
        front=node;
        rear=node;
        size=0;
    }

    //判断是否为空
    public boolean isEmpty(){
        return size==0;
    }

    //队列插入元素
    public boolean offer(E e){
        Node elem=new Node(e,null);
        rear.next=elem;
        rear=elem;
        size++;
        return true;
    }

    //返回队首元素，但并不删除
    public E peek(){
        if(isEmpty()){
            throw new RuntimeException("队列为空！");
        }else{
            return front.next.e;
        }
    }

    //出队
    public E poll(){
        if(isEmpty()){
            throw new RuntimeException("队列为空！");
        }else{
            Node elem=front.next;
            front.next=elem.next;
            elem.next=null;
            size--;
            return elem.e;
        }
    }

    //获取队列长度
    public int getSize(){
        return size;
    }

    //清空队列
    public void clear(){
        for(Node node=front;node!=null;){
            Node next=node.next;
            node.e=null;
            node.next=null;
            node=next;
        }
        size=0;
    }

    public static void main(String[] args) {
        LinkQueue<String> linkQueue=new LinkQueue<>();
        System.out.println("queue is empty:"+linkQueue.isEmpty());
        System.out.println("queue.size="+linkQueue.getSize());
        linkQueue.offer("a");
        linkQueue.offer("b");
        linkQueue.offer("c");
        linkQueue.offer("d");
        linkQueue.offer("e");
        System.out.println("queue is empty:"+linkQueue.isEmpty());
        System.out.println("queue.size="+linkQueue.getSize());
        System.out.println(linkQueue.poll());
        System.out.println(linkQueue.peek());
        System.out.println(linkQueue.poll());
        System.out.println("queue is empty:"+linkQueue.isEmpty());
        System.out.println("queue.size="+linkQueue.getSize());
        linkQueue.clear();
        System.out.println("---------------after clear---------------");
        System.out.println("queue is empty:"+linkQueue.isEmpty());
        System.out.println("queue.size="+linkQueue.getSize());
    }

}