队列和栈都是线性表，队列先进先出（FIFO），栈先进后出（FILO）
队列
只允许在表的头部删除，尾部插入。普通的顺序队列，在出队入队中，由于头尾指针只+1不减小，容易造成假溢出。所以实际应用中一般使用循环队列。
循环队列
入队算法：
判断为空的条件：front=rear；
为满的条件：front=（rear+1）%MaxSize（为了区别为空，队列中最多有MaxSize-1个元素）
iOS中的队列
队列是对线程的包装，分为串行和并行队列，串行队列中的线程满足先进先出。
栈
由于先进后出特性，最大的应用是递归，还能储存函数断点（即先执行到的断点最后放开）
两个栈实现一个队列
两个后进先出实现一个先进先出。栈1，栈2。
入队：全部入栈1；（只有当栈2的元素全部出栈，栈1的元素会再次进栈2）
出队：如果栈2为空，栈1中的元素，后进先出倒序进栈2，留最后一个元素即最先进栈的元素（不留也可以，栈1留一个的话省了这个元素的出栈进栈的时间），出栈（即出队），即实现了先进先出；如果栈2不为空，此时栈2的顺序应是入队时候的倒序，直接出栈（出队），也实现了先进先出。
两个队列实现一个栈
两个先进先出实现一个先进后出。如果固定Q1，Q2的职能，每次出栈完毕都要将Q2中的元素转移回Q1（同倒栈），所以应采用指针的思想，一个指向入/出栈队列ppQ，一个指向中转队列tmpQ。无论出栈还是入栈时，不为空的永远是ppQ（出栈时都为空为下溢）。
入栈：全部入队ppQ；（Q1Q2都为空入队任一）
出栈：ppQ中的元素先进先出顺序进tmpQ，ppQ剩最后一个元素，出队（即实现出栈）。
网友评论