栈:LIFO(后进先出)
队列:FIFO(先进先出)
栈的顺序存储结构实现:
- * top:栈顶指针,初始化top=-1
- * 入栈:data[++top]=e
- * 出栈:(E)data[top--]
- * 得到栈顶元素:(E)data[top]
- * 空:top=-1
- package com.myutil.stack;
- /**
- * 基于数组实现的顺序栈
- * @param <E>
- *
- * top:栈顶指针,初始化top=-1
- * 入栈:data[++top]=e
- * 出栈:(E)data[top--]
- * 得到栈顶元素:(E)data[top]
- * 空:top=-1
- */
- public class Stack < E > {
- 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);
- }
- }
- //进栈,第一个元素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--];
- }
- }
- //判空
- public boolean empty() {
- return top == -1 ? true: false;
- }
- //返回对象在堆栈中的位置,以 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 static void main(String[] args) {
- Stack < Integer > stack = new Stack < >();
- for (int i = 0; i < 5; i++) {
- stack.push(i);
- }
- for (int i = 0; i < 5; i++) {
- System.out.print(stack.pop() + " ");
- }
- }
- }
栈的链式存储结构实现:
- package com.myutil.stack;
- public class LinkStack < E > {
- //链栈的节点
- private class Node < E > {
- E e;
- Node < E > next;
- public Node() {}
- public Node(E e, Node next) {
- this.e = e;
- this.next = next;
- }
- }
- private Node < E > top; //栈顶元素
- private int size; //当前栈大小
- public LinkStack() {
- top = null;
- }
- //入栈:让top指向新创建的元素,新元素的next引用指向原来的栈顶元素
- public boolean push(E e) {
- top = new Node(e, top);
- size++;
- return true;
- }
- //查看栈顶元素但不删除
- public Node < E > peek() {
- if (empty()) {
- throw new RuntimeException("空栈异常!");
- } else {
- return top;
- }
- }
- //出栈
- public Node < E > pop() {
- if (empty()) {
- throw new RuntimeException("空栈异常!");
- } else {
- Node < E > value = top; //得到栈顶元素
- top = top.next; //让top引用指向原栈顶元素的下一个元素
- value.next = null; //释放原栈顶元素的next引用
- size--;
- return value;
- }
- }
- //当前栈大小
- public int length() {
- return size;
- }
- //判空
- public boolean empty() {
- return size == 0;
- }
- public static void main(String[] args) {
- LinkStack < Integer > stack = new LinkStack < >();
- for (int i = 0; i < 5; i++) {
- stack.push(i);
- }
- for (int i = 0; i < 5; i++) {
- System.out.print(stack.pop().e + " ");
- }
- }
- }
基于 LinkedList 实现的栈结构:
- * push-----addFirst()
- * pop------removeFirst()
- * peek-----getFirst()
- * empty----isEmpty()
- package com.myutil.stack;
- import java.util.LinkedList;
- /**
- * 基于LinkedList实现栈
- * 在LinkedList实力中只选择部分基于栈实现的接口
- *
- * push-----addFirst()
- * pop------removeFirst()
- * peek-----getFirst()
- * empty----isEmpty()
- */
- public class StackList < E > {
- private LinkedList < E > ll = new LinkedList < E > ();
- //入栈
- 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 static void main(String[] args) {
- StackList < Integer > stack = new StackList < >();
- for (int i = 0; i < 5; i++) {
- stack.push(i);
- }
- System.out.println(stack.toString());
- for (int i = 0; i < 5; i++) {
- System.out.print(stack.pop() + " ");
- }
- }
- }
队列的顺序存储结构实现
- * 入队:rear=rear+1,data[rear]=e
- * 出队:front=front+1,E value=(E)data[front],data[front]=null
- * 得到对首元素:(E)data[front+1];
- * 判断对空:rear==front
- * 对长:rear-front
- package com.myutil.queue;
- /*
- * 设置两个指针,头指针front和尾指针rear
- * 规定front总是指向当前队头元素的前一个位置,rear指向当前队尾元素的位置
- * 初始化front=rear=-1
- *
- * 入队:rear=rear+1,data[rear]=e
- * 出队:front=front+1,E value=(E)data[front],data[front]=null
- * 得到对首元素:(E)data[front+1];
- * 判断对空:rear==front
- * 对长:rear-front
- */
- public class Queue < E > {
- private Object[] data = null;
- private int maxSize; //队列容量
- private int front; //队列头,允许删除
- private int rear; //队列尾,允许插入
- //构造函数
- public Queue() {
- this(10);
- }
- public Queue(int initialSize) {
- if (initialSize >= 0) {
- this.maxSize = initialSize;
- data = new Object[initialSize];
- front = rear = -1;
- } else {
- throw new RuntimeException("初始化大小不能小于0:" + initialSize);
- }
- }
- //插入
- public boolean add(E e) {
- if (rear == maxSize - 1) {
- throw new RuntimeException("队列已满,无法插入新的元素!");
- } else {
- data[++rear] = e;
- return true;
- }
- }
- //返回队首元素,但不删除
- public E peek() {
- if (empty()) {
- throw new RuntimeException("空队列异常!");
- } else {
- return (E) data[front + 1];
- }
- }
- //出队
- public E poll() {
- if (empty()) {
- throw new RuntimeException("空队列异常!");
- } else {
- E value = (E) data[++front]; //保留队列的front端的元素的值
- data[front] = null; //释放队列的front端的元素
- return value;
- /*front=front+1;
- E value=(E) data[front];
- return value;*/
- }
- }
- //队列长度
- public int length() {
- return rear - front;
- }
- //判空
- public boolean empty() {
- return rear == front ? true: false;
- }
- public static void main(String[] args) {
- Queue < Integer > queue = new Queue < >();
- for (int i = 0; i < 5; i++) {
- queue.add(i);
- }
- for (int i = 0; i < queue.length(); i++) {
- System.out.print(queue.peek() + " ");
- }
- System.out.println();
- int size = queue.length();
- for (int i = 0; i < size; i++) {
- System.out.print(queue.poll() + " ");
- }
- }
- }
循环队列的顺序存储结构实现
- * 入队:rear=(rear+1)%maxSize,data[rear]=e
- * 出队:front = (front+1)%maxSize; E value =(E)data[front]; data[front] = null;
- * 得到对首元素:(E)data[front+1];
- * 判断对空:rear==front
- * 对长:rear-front
- package com.myutil.queue;
- /*
- * 入队:rear=(rear+1)%maxSize,data[rear]=e
- * 出队:front = (front+1)%maxSize; E value =(E)data[front]; data[front] = null;
- * 得到对首元素:(E)data[front+1];
- * 判断对空:rear==front
- * 对长:rear-front
- */
- import java.util.Arrays;
- 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 initialSize) {
- if (initialSize >= 0) {
- this.maxSize = initialSize;
- data = new Object[initialSize];
- front = rear = -1;
- } else {
- throw new RuntimeException("初始化大小不能小于0:" + initialSize);
- }
- }
- // 插入
- public boolean add(E e) {
- if ((rear + 1) % maxSize == front) {
- throw new RuntimeException("队列已满,无法插入新的元素!");
- } else {
- rear = (rear + 1) % maxSize;
- data[rear] = e;
- return true;
- }
- }
- // 返回队首元素,但不删除
- public E peek() {
- if (empty()) {
- throw new RuntimeException("空队列异常!");
- } else {
- return (E) data[front + 1];
- }
- }
- // 出队
- public E poll() {
- if (empty()) {
- throw new RuntimeException("空队列异常!");
- } else {
- front = (front + 1) % maxSize; //队首指针加1
- E value = (E) data[front]; // 保留队列的front端的元素的值
- data[front] = null; // 释放队列的front端的元素
- return value;
- }
- }
- // 队列长度
- public int length() {
- return rear - front;
- }
- // 判空
- public boolean empty() {
- return rear == front;
- }
- //清空循环队列
- public void clear() {
- Arrays.fill(data, null);
- front = -1;
- rear = -1;
- }
- public static void main(String[] args) {
- LoopQueue < Integer > queue = new LoopQueue < >();
- for (int i = 0; i < 5; i++) {
- queue.add(i);
- }
- for (int i = 0; i < queue.length(); i++) {
- System.out.print(queue.peek() + " ");
- }
- System.out.println();
- int size = queue.length();
- for (int i = 0; i < size; i++) {
- System.out.print(queue.poll() + " ");
- }
- }
- }
队列的链式存储结构实现
- package com.myutil.queue;
- public class LinkQueue < E > {
- // 链栈的节点
- private class Node < E > {
- E e;
- Node < E > 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() {
- front = null;
- rear = null;
- }
- //判空
- public boolean empty() {
- return size == 0;
- }
- //插入
- public boolean add(E e) {
- if (empty()) { //如果队列为空
- front = new Node(e, null); //只有一个节点,front、rear都指向该节点
- rear = front;
- } else {
- Node < E > newNode = new Node < E > (e, null);
- rear.next = newNode; //让尾节点的next指向新增的节点
- rear = newNode; //以新节点作为新的尾节点
- }
- size++;
- return true;
- }
- //返回队首元素,但不删除
- public Node < E > peek() {
- if (empty()) {
- throw new RuntimeException("空队列异常!");
- } else {
- return front;
- }
- }
- //出队
- public Node < E > poll() {
- if (empty()) {
- throw new RuntimeException("空队列异常!");
- } else {
- Node < E > value = front; //得到队列头元素
- front = front.next; //让front引用指向原队列头元素的下一个元素
- value.next = null; //释放原队列头元素的next引用
- size--;
- return value;
- }
- }
- //队列长度
- public int length() {
- return size;
- }
- public static void main(String[] args) {
- LinkQueue < Integer > queue = new LinkQueue < >();
- for (int i = 0; i < 5; i++) {
- queue.add(i);
- }
- for (int i = 0; i < queue.length(); i++) {
- System.out.print(queue.peek().e + " ");
- }
- System.out.println();
- int size = queue.length();
- for (int i = 0; i < size; i++) {
- System.out.print(queue.poll().e + " ");
- }
- }
- }
基于 LinkedList 实现队列结构
- * 使用java.util.Queue接口,其底层关联到一个LinkedList(双端队列)实例.
- *
- * add----add() 会抛出异常
- * offer-----offer()
- *
- * element-----element() 对为空,返回异常
- * peek------peek()
- *
- * remove----remove() 对为空,返回异常
- * poll------poll()
- *
- * empty-----isEmpty()
- package com.myutil.queue;
- /**
- * 使用java.util.Queue接口,其底层关联到一个LinkedList(双端队列)实例.
- *
- * add----add() 会抛出异常
- * offer-----offer()
- *
- * element-----element() 对为空,返回异常
- * peek------peek()
- *
- * remove----remove() 对为空,返回异常
- * poll------poll()
- *
- * empty-----isEmpty()
- */
- import java.util.LinkedList;
- import java.util.Queue;
- public class QueueList < E > {
- private Queue < E > queue = new LinkedList < E > ();
- // 将指定的元素插入此队列(如果立即可行且不会违反容量限制),在成功时返回 true,
- //如果当前没有可用的空间,则抛出 IllegalStateException。
- public boolean add(E e) {
- return queue.add(e);
- }
- //获取,但是不移除此队列的头。
- public E element() {
- return queue.element();
- }
- //将指定的元素插入此队列(如果立即可行且不会违反容量限制),当使用有容量限制的队列时,
- //此方法通常要优于 add(E),后者可能无法插入元素,而只是抛出一个异常。
- public boolean offer(E e) {
- return queue.offer(e);
- }
- //获取但不移除此队列的头;如果此队列为空,则返回 null
- public E peek() {
- return queue.peek();
- }
- //获取并移除此队列的头,如果此队列为空,则返回 null
- public E poll() {
- return queue.poll();
- }
- //获取并移除此队列的头
- public E remove() {
- return queue.remove();
- }
- //判空
- public boolean empty() {
- return queue.isEmpty();
- }
- public static void main(String[] args) {
- QueueList < Integer > queueList = new QueueList < >();
- for (int i = 0; i < 5; i++) {
- queueList.add(i);
- }
- /*while (!queueList.empty()) {
- System.out.println(queueList.peek());
- }
- System.out.println();
- */
- while (!queueList.empty()) {
- System.out.print(queueList.poll() + " ");
- }
- }
- }
本文参考地址:http://www.cnblogs.com/CherishFX/p/4608880.html 并在此博客的基础上进行了一些修改
来源: http://www.bubuko.com/infodetail-2447397.html