栈，又叫做堆栈（Stack），但是它和堆没有关系。实际上堆和栈是两种不同的概念，栈是一种只能在一端进行插入和删除的线性数据结构。
栈的特点：先进先出（LIFO，Last In First Out），也可以说是先进后出（FILO，First In Last Out），我们只能从一端去操作元素。
一般来说，栈主要有两种操作：一个是进栈（Push），又叫做入栈，压栈；另一个是出栈（POP），或者叫退栈。
我们可以用数组去实现一个简单的栈，在下面栈的实现代码中，以整型元素为例，在Java等高级语言中，数据类型中，可以换成对象。
public class Stack { private int size = 0; private int[] array; public Stack() { this(10); } public Stack(int init) { if (init <= 0) { init = 10; } array = new int[init]; } /** * 入栈 * @param item 入栈元素 */ public void push(int item) { if (size == array.length) { array = Arrays.copyOf(array, size*2); } array[size++] = item; } /** * 获取栈顶元素，但是没有出栈 * @return 栈顶元素 */ public int peek() { if (size ==0) { throw new IndexOutOfBoundsException("栈里已经为空"); } return array[size -1]; } /** * 出栈，同时获取栈顶元素 * @return 栈顶元素 */ public int pop() { int item = peek(); size --; return item; } /** * 栈是否满了？ * @return */ public boolean isFull() { return size == array.length; } /** *栈是否为空栈 ？ * @return */ public boolean isEmpty() { return size ==0; } public int size() { return size; } } public class StackTest { public static void main(String[] args) { Stack stack = new Stack(1); stack.push(1); stack.push(2); System.out.println(stack.size());//栈内元素个数为2，当前数组长度也为2 stack.push(3); System.out.println(stack.size());//栈内元素个数为3，当前数组长度为4 System.out.println(stack.peek());//获取栈顶元素为3，但没有出栈 System.out.println(stack.size());//元素个数还为3 System.out.println(stack.pop());//栈顶元素出栈，返回3 System.out.println(stack.pop());//栈顶元素出栈，返回2 System.out.println(stack.size());//两次出栈之后，当前元素个数为1 } }由于栈有先进先出的特点，把元素顺序入栈，然后顺序出栈，就可以轻松得到逆序输出。
语法检查，符号成对出现在编程语言中，{ } [ ] ( ) < > 等都是成对出现的，当遇到符号的前半部分，就进行入栈操作（PUSH），当遇到后半部分就与栈顶元素匹配（PEEK），如果相匹配，就出栈（POP），否则匹配出错。
数值转换我们在进行数值转换时，最后的商需要逆序输出，用栈就可以简单的实现。当然，栈还有许多应用，比如经常听到的“函数栈”就是我们在调用方法时，计算机会执行PUSH方法，记录调用，在return的时候。就是在方法结束后，执行POP方法，完成前后对应。
队列也是一种操作受限的数据结构，插入操作只能从一端进行，这个叫队尾，移除操作只能从另一端操作，这个叫队头。
一般来说，队列的实现方式有两种，数组和链表。数组来实现有两种方式：顺序队列和循环队列。用数组实现队列，若出现队满的情况，当有新的元素需要入队的时候，可是没有位置，这时候，要么丢掉，不管它，要么等待，等待时间由程序来控制。
实现顺序队列：
public class ArrayQueue { private final Object[] items; private int head = 0; private int tail = 0; /** * 初始化队列 * @param capacity 队列长度 */ public ArrayQueue(int capacity) { this.items = new Object[capacity]; } /** * 入队 * @param item * @return */ public boolean put(Object item) { if (head == ((tail + 1) % items.length)) { //说明队满 return false; } items[tail] = item; tail = (tail + 1) % items.length; //tail标记后移一位 return true; } /** * 获取队列头元素，不出队 * @return */ public Object peek() { if (head == tail) { //s说明对空 return null; } return items[head]; } /** * 出队 * @return */ public Object poll() { if (head == tail) { //说明队空 return null; } Object item = items[head]; items[head] = null;//没用的元素赋空值，当然不设置也可以，反正标记移动之后会被覆盖 head = (head +1 ) % items.length;//head标记后移一位 return item; } public boolean isFull() { return head == (tail + 1) % items.length; } public boolean isEmpty() { return head == tail; } public int Size() { if (tail >= head) { return tail - head; }else { return tail + items.length - head; } } } public class ArrayQueueTest { public static void main(String[] args) { ArrayQueue queue = new ArrayQueue(4); System.out.println(queue.put("A"));//true System.out.println(queue.put("B"));//true System.out.println(queue.put("C"));//true System.out.println(queue.put("D"));//false System.out.println(queue.isFull());//true,队列已经满了，队列长度为4，因为是循环队列，最大存3个元素 System.out.println(queue.Size());//3 System.out.println(queue.peek());//A 获取队头元素，不出队 System.out.println(queue.poll());//A System.out.println(queue.poll());//B System.out.println(queue.poll());//C System.out.println(queue.isEmpty());//true ,当前队列为空 } }买东西，秒杀
我们很容易想到这个场景，从网购秒杀商品，到排队买早餐。先进先出，先来先走
生产者和消费者模式
还记得生产者和消费者模式吗? 生产者负责生产，生产之后放到传送带，消费者拿下来，这个模式实现起来，无非就是存在一个队列，若干个生产者向队列增加元素，若干个消费者从队列中获取元素。
