数据结构之栈和队列(双向链表及数组实现)

逻辑概念：

• 栈：数据先进先出，犹如弹匣
• 队列：数据先进先出，好似排队

• 双向链表实现（对链表不熟悉的可以看我的另一篇文章数据结构之单双向链表）：

  • 实现双向队列：

    //  双向链表结构
    public class DoubleNode {
    	public int value;
    	public DoubleNode pre;
    	public DoubleNode next;
    	
    	public DoubleNode(int data) {
    		value = data;
    	}
    }
    
    // 双向队列
    public static class DoubleEndsQueue {
    	public Node head; // 头部指针
    	public Node tail; // 尾部指针
    
    	// 从头部添加
    	public void addFromHead(T value) {
    		Node cur = new Node(value);
    		if(head == null) {
    			head = cur;
    			tail = cur;
    		} else {
    			cur.next = head;
    			head.pre = cur;
    			head = cur;
    		}
    	}
    
    	// 从尾部添加
    	public void addFromBottom(T value) {
    		Node cur = new Node(value);
    		if(tail == null) {
    			head = cur;
    			tail = cur;
    		} else {
    			cur.pre = tail;
    			tail.next = cur;
    			tail = cur;
    		}
    	}
    
    	// 从头部弹出
    	public T popFromHead() {
    		if(head == null) {
    			return null;
    		}
    		Node cur = head;
    		if(head == tail) {
    			head = null;
    			tail = null;
    		}else {
    			head = head.next;
    			head.pre = null;
    			cur.next = null;
    		}
    		return cur.value;
    	}
    	// 尾部弹出
    	public T popFromBottom() {
    		if(head == null) {
    			return null;
    		}
    		Node cur = tail;
    		if(head == tail) {
    			head = null;
    			tail = null;
    		}else {
    			tail = tail.pre;
    			tail.next = null;
    			cur.pre = null;
    		}
    		return cur.value;
    	}
    	// 判断是否队列为空
    	public boolean isEmpty() {
    		return head == null;
    	}
    }
    

  • 实现栈结构：

    public static  class MyStack {
    	private DoubleEndsQueue queue;
    	// 构造函数
    	public MyStack() {
    		queue = new DoubleEndsQueue();
    	}
    	// 入栈
    	public void push(T value) {
    		queue.addFromHead(value);
    	}
    	// 出栈
    	public T pop() {
    		return queue.popFromHead();
    	}
    	// 判断是否为空
    	public boolean isEmpty() {
    		return queue.isEmpty();
    	}
    }
    

  • 实现队列：

    public static  class MyQueue {
    	private DoubleEndsQueue queue;
    	// 构造函数
    	public MyQueue() {
    		queue = new DoubleEndsQueue();
    	}
    	// 入队列
    	public void push(T value) {
    		queue.addFromHead(value);
    	}
    	// 出队列
    	public T pop() {
    		return queue.popFromBottom();
    	}
    	// 判断是否为空
    	public boolean isEmpty() {
    		return queue.isEmpty();
    	}
    }
    

• 数组实现：

  • 实现栈结构(非动态，以int数组为例)：

    public static class MyStack {
    	private int[] arr;
    	private int index; // index表示下一个要加元素的位置，规定了栈的尾部
    	private final int limit;  // 栈的最大长度
    
    	// 构造函数
    	public MyQueue(int limit) {
    		arr = new int[limit];
    		index = 0;
    		this.limit = limit;
    	}
    	// 入栈
    	public void push(int value) {
    		if(index >= limit) {
    			throw new RuntimeException("栈满了，不能再加了");
    		}
    		arr[index++] = value;
    	}
    	// 出栈，因为添加元素使用的是数组赋值，所以弹出的元素不需要删除，只要把index - 1就好
    	public T pop() {
    		if(index == 0) {
    			throw new RuntimeException("栈空了，不能再拿了");
    		}
    		return arr[--index];
    	}
    	// 判断栈是否为空
    	public boolean isEmpty() {
    		return index == 0;
    	}
    }
    

  • 实现队列(非动态，以int数组为例)：

    // 因为push和pop可能会交替进行，所以要使用双指针对数组循环指向，实现内存的循环使用
    public static class MyQueue {
    	private int[] arr;
    	private pushi; //入队列位置的指针
    	private polli; // 出队列位置的指针
    	private size; // 队列内元素的多少
    	private final int limit; // 队列的最大大小
    
    	// 构造函数
    	public MyQueue(int limit) {
    		arr = new int[limit];
    		pushi = 0;
    		polli = 0;
    		size = 0;
    		this.limit = limit;
    	}
    	// 入队列
    	public void push(int value) {
    		if(size == limit) {
    			throw new RuntimeException("队列满了，不能再加了");
    		}
    		size++;
    		arr[pushi] = value;
    		pushi = nextIndex(pushi); // 指针移到下一个入队列的位置
    	}
    	// 出队列
    	public int pop() {
    		if(size == 0) {
    			throw new RuntimeException("队列空了，不能再拿了");
    		}
    		size--;
    		int ans = arr[polli];
    		polli = nextIndex(pollii);
    		return ans;
    	}
    	// 判断队列是否为空
    	public boolean isEmpty() {
    		return size == 0;
    	}
    	// 使指针移到下一目标位置的方法
    	private int nextIndex(int i) {
    		return i < limit - 1 ? i + 1 : 0;
    	}
    }