栈：LIFO（后进先出）

队列：FIFO（先进先出）

栈的顺序存储结构实现：

/**
?* 基于数组实现的顺序栈
?* @param
?*/
public class Stack {
? ? private Object[] data = null;
? ? private int maxSize=0;? //栈容量
? ? private int top =-1;? //栈顶指针
? ?
? ? /**
? ? * 构造函数：根据给定的size初始化栈
? ? */
? ? Stack(){
? ? ? ? this(10);? //默认栈大小为10
? ? }
? ?
? ? Stack(int initialSize){
? ? ? ? if(initialSize >=0){
? ? ? ? ? ? this.maxSize = initialSize;
? ? ? ? ? ? data = new Object[initialSize];
? ? ? ? ? ? top = -1;
? ? ? ? }else{
? ? ? ? ? ? throw new RuntimeException("初始化大小不能小于0：" + initialSize);
? ? ? ? }
? ? }
? ?
? ? //判空
? ? public boolean empty(){
? ? ? ? return top==-1 ? true : false;
? ? }
? ?
? ? //进栈,第一个元素top=0；
? ? public boolean push(E e){
? ? ? ? if(top == maxSize -1){
? ? ? ? ? ? throw new RuntimeException("栈已满，无法将元素入栈！");
? ? ? ? }else{
? ? ? ? ? ? data[++top]=e;
? ? ? ? ? ? return true;
? ? ? ? }? ?
? ? }
? ?
? ? //查看栈顶元素但不移除
? ? public E peek(){
? ? ? ? if(top == -1){
? ? ? ? ? ? throw new RuntimeException("栈为空！");
? ? ? ? }else{
? ? ? ? ? ? return (E)data[top];
? ? ? ? }
? ? }
? ?
? ? //弹出栈顶元素
? ? public E pop(){
? ? ? ? if(top == -1){
? ? ? ? ? ? throw new RuntimeException("栈为空！");
? ? ? ? }else{
? ? ? ? ? ? return (E)data[top--];
? ? ? ? }
? ? }
? ?
? ? //返回对象在堆栈中的位置，以 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 class LinkStack {
? ? //链栈的节点
? ? private class Node{
? ? ? ? E e;
? ? ? ? Node next;
? ? ? ?
? ? ? ? public Node(){}
? ? ? ? public Node(E e, Node next){
? ? ? ? ? ? this.e = e;
? ? ? ? ? ? this.next = next;
? ? ? ? }
? ? }
? ?
? ? private Node top;? //栈顶元素
? ? private int size;? //当前栈大小
? ?
? ? public LinkStack(){
? ? ? ? top = null;
? ? }
? ?
? ? //当前栈大小
? ? public int length(){
? ? ? ? return size;
? ? }
? ?
? ? //判空
? ? public boolean empty(){
? ? ? ? return size==0;
? ? }
? ?
? ? //入栈：让top指向新创建的元素，新元素的next引用指向原来的栈顶元素
? ? public boolean push(E e){
? ? ? ? top = new Node(e,top);
? ? ? ? size ++;
? ? ? ? return true;
? ? }
? ?
? ? //查看栈顶元素但不删除
? ? public Node peek(){
? ? ? ? if(empty()){
? ? ? ? ? ? throw new RuntimeException("空栈异常！");
? ? ? ? }else{
? ? ? ? ? ? return top;
? ? ? ? }
? ? }
? ?
? ? //出栈
? ? public Node pop(){
? ? ? ? if(empty()){
? ? ? ? ? ? throw new RuntimeException("空栈异常！");
? ? ? ? }else{
? ? ? ? ? ? Node value = top; //得到栈顶元素
? ? ? ? ? ? top = top.next; //让top引用指向原栈顶元素的下一个元素
? ? ? ? ? ? value.next = null;? //释放原栈顶元素的next引用
? ? ? ? ? ? size --;
? ? ? ? ? ? return value;
? ? ? ? }
? ? }
}

基于LinkedList实现的栈结构：

import java.util.LinkedList;

/**
?* 基于LinkedList实现栈
?* 在LinkedList实力中只选择部分基于栈实现的接口
?*/
public class StackList {
? ? private LinkedList ll = new LinkedList();
? ?
? ? //入栈
? ? public void push(E e){
? ? ? ? ll.addFirst(e);
? ? }
? ?
? ? //查看栈顶元素但不移除
? ? public E peek(){
? ? ? ? return ll.getFirst();
? ? }
? ?
? ? //出栈
? ? public E pop(){
? ? ? ? return ll.removeFirst();
? ? }
? ?
? ? //判空
? ? public boolean empty(){
? ? ? ? return ll.isEmpty();
? ? }
? ?
? ? //打印栈元素
? ? public String toString(){
? ? ? ? return ll.toString();
? ? }
}

队列的顺序存储结构实现

public class Queue {
? ? private Object[] data=null;
? ? private int maxSize; //队列容量
? ? private int front;? //队列头，允许删除
? ? private int rear;? //队列尾，允许插入