Java实现栈和队列

栈：LIFO（后进先出）

队列：FIFO（先进先出）

栈的顺序存储结构实现：

* top:栈顶指针，初始化top=-1
* 入栈：data[++top]=e
* 出栈：(E)data[top--]
* 得到栈顶元素：(E)data[top]
* 空：top=-1

 1 package com.myutil.stack;
 2 
 3 /**
 4  * 基于数组实现的顺序栈
 5  * @param <E>
 6  * 
 7  * top:栈顶指针，初始化top=-1
 8  * 入栈：data[++top]=e
 9  * 出栈：(E)data[top--]
10  * 得到栈顶元素：(E)data[top]
11  * 空：top=-1
12  */
13 public class Stack<E> {
14     private Object[] data = null;
15     private int maxSize=0;   //栈容量
16     private int top =-1;  //栈顶指针
17     
18     /**
19      * 构造函数：根据给定的size初始化栈
20      */
21     Stack(){
22         this(10);   //默认栈大小为10
23     }
24     
25     Stack(int initialSize){
26         if(initialSize >=0){
27             this.maxSize = initialSize;
28             data = new Object[initialSize];
29             top = -1;
30         }else{
31             throw new RuntimeException("初始化大小不能小于0：" + initialSize);
32         }
33     }
34     
35     
36     
37     //进栈,第一个元素top=0；
38     public boolean push(E e){
39         if(top == maxSize -1){
40             throw new RuntimeException("栈已满，无法将元素入栈！");
41         }else{
42             data[++top]=e;
43             return true;
44         }    
45     }
46     
47     //查看栈顶元素但不移除
48     public E peek(){
49         if(top == -1){
50             throw new RuntimeException("栈为空！");
51         }else{
52             return (E)data[top];
53         }
54     }
55     
56     //弹出栈顶元素
57     public E pop(){
58         if(top == -1){
59             throw new RuntimeException("栈为空！");
60         }else{
61             return (E)data[top--];
62         }
63     }
64     
65     //判空
66     public boolean empty(){
67         return top==-1 ? true : false;
68     }
69     
70     //返回对象在堆栈中的位置，以 1 为基数
71     public int search(E e){
72         int i=top;
73         while(top != -1){
74             if(peek() != e){
75                 top --;
76             }else{
77                 break;
78             }
79         }
80         int result = top+1;
81         top = i;
82         return result;      
83     }
84     
85     public static void main(String[] args) {
86         Stack<Integer> stack=new Stack<>();
87         for (int i = 0; i < 5; i++) {
88             stack.push(i);
89         }
90         for (int i = 0; i < 5; i++) {
91             System.out.print(stack.pop()+" ");
92         }
93     }
94 }

栈的链式存储结构实现：

 1 package com.myutil.stack;
 2 
 3 public class LinkStack<E> {
 4     //链栈的节点
 5     private class Node<E>{
 6         E e;
 7         Node<E> next;
 8         
 9         public Node(){}
10         public Node(E e, Node next){
11             this.e = e;
12             this.next = next;
13         }
14     }
15     
16     private Node<E> top;   //栈顶元素
17     private int size;  //当前栈大小
18     
19     public LinkStack(){
20         top = null;
21     }
22     
23     
24     
25     //入栈：让top指向新创建的元素，新元素的next引用指向原来的栈顶元素
26     public boolean push(E e){
27         top = new Node(e,top);
28         size ++;
29         return true;
30     }
31     
32     //查看栈顶元素但不删除
33     public Node<E> peek(){
34         if(empty()){
35             throw new RuntimeException("空栈异常！");
36         }else{
37             return top;
38         }
39     }
40     
41     //出栈
42     public Node<E> pop(){
43         if(empty()){
44             throw new RuntimeException("空栈异常！");
45         }else{
46             Node<E> value = top; //得到栈顶元素
47             top = top.next; //让top引用指向原栈顶元素的下一个元素 
48             value.next = null;  //释放原栈顶元素的next引用
49             size --;
50             return value;
51         }
52     }
53     
54   //当前栈大小
55     public int length(){
56         return size;
57     }
58     
59     //判空
60     public boolean empty(){
61         return size==0;
62     }
63     
64     public static void main(String[] args) {
65         LinkStack<Integer> stack=new LinkStack<>();
66         for (int i = 0; i < 5; i++) {
67             stack.push(i);
68         }
69         for (int i = 0; i < 5; i++) {
70             System.out.print(stack.pop().e+" ");
71         }
72     }
73 }

基于LinkedList实现的栈结构：

 * push-----addFirst()
 * pop------removeFirst()
 * peek-----getFirst()
 * empty----isEmpty()

 1 package com.myutil.stack;
 2 
 3 import java.util.LinkedList;
 4 
 5 /**
 6  * 基于LinkedList实现栈
 7  * 在LinkedList实力中只选择部分基于栈实现的接口
 8  * 
 9  * push-----addFirst()
10  * pop------removeFirst()
11  * peek-----getFirst()
12  * empty----isEmpty()
13  */
14 public class StackList<E> {
15     private LinkedList<E> ll = new LinkedList<E>();
16     
17     //入栈
18     public void push(E e){
19         ll.addFirst(e);
20     }
21     
22     //查看栈顶元素但不移除
23     public E peek(){
24         return ll.getFirst();
25     }
26     
27     //出栈
28     public E pop(){
29         return ll.removeFirst();
30     }
31     
32     //判空
33     public boolean empty(){
34         return ll.isEmpty();
35     }
36     
37     //打印栈元素
38     public String toString(){
39         return ll.toString();
40     }
41     
42     public static void main(String[] args) {
43         StackList<Integer> stack=new StackList<>();
44         for (int i = 0; i < 5; i++) {
45             stack.push(i);
46         }
47         System.out.println(stack.toString());
48         for (int i = 0; i < 5; i++) {
49             System.out.print(stack.pop()+" ");
50         }
51     }
52 }

队列的顺序存储结构实现

front=rear=0 
入队：rear=rear+1
出队：front=front+1
取队头：队头指针：front

队满：rear=maxSize-1
对空：rear==front
对长：rear-front

如果实现一个简单的只有入队和出队功能的队列：可以设置front=0，rear=-1

 1 package com.myutil.queue;
 2 
 3 public class Queue<E> {
 4     private Object[] data=null;
 5     private int maxSize; //队列容量
 6     private int front;  //队列头，允许删除
 7     private int rear;   //队列尾，允许插入
 8 
 9     //构造函数
10     public Queue(){
11         this(10);
12     }
13     
14     public Queue(int initialSize){
15         if(initialSize >=0){
16             this.maxSize = initialSize;
17             data = new Object[initialSize];
18             front = rear =0;
19         }else{
20             throw new RuntimeException("初始化大小不能小于0：" + initialSize);
21         }
22     }
23     
24     //判空
25     public boolean empty(){
26         return rear==front?true:false;
27     }
28     
29     //插入
30     public boolean add(E e){
31         if(rear== maxSize-1){
32             throw new RuntimeException("队列已满，无法插入新的元素！");
33         }else{
34             data[rear++]=e;
35             return true;
36         }
37     }
38     
39     //返回队首元素，但不删除
40     public E peek(){
41         if(empty()){
42             throw new RuntimeException("空队列异常！");
43         }else{
44             return (E) data[front];
45         }    
46     }
47     
48     //出队
49     public E poll(){
50         if(empty()){
51             throw new RuntimeException("空队列异常！");
52         }else{
53             E value = (E) data[front];  //保留队列的front端的元素的值
54             data[front++] = null;     //释放队列的front端的元素                
55             return value;
56         }            
57     }
58     
59     //队列长度
60     public int length(){
61         return rear-front;
62     }
63     
64     public static void main(String[] args) {
65         Queue<Integer> queue=new Queue<>();
66         for (int i = 0; i < 5; i++) {
67             queue.add(i);
68         }
69         for (int i = 0; i < queue.length(); i++) {
70             System.out.print(queue.peek()+" ");
71         }
72         System.out.println();
73         int size=queue.length();
74         for (int i = 0; i < size; i++) {
75             System.out.print(queue.poll()+" ");
76         }
77     }
78 }

循环队列的顺序存储结构实现

front=rear=0

入队：rear=(rear+1)/maxSize
出队：front=(front+1)/maxSize

取队头：队头指针：front
队满：(rear+1)/maxSize=front（如果不设置变量size来判断队满）

队空：rear=front
对长：rear-front

  1 package com.myutil.queue;
  2 
  3 /*
  4  * 入队：rear=(rear+1)%maxSize，data[rear]=e
  5  * 出队：front = (front+1)%maxSize; E value =(E)data[front]; data[front] = null; 
  6  * 得到对首元素：(E)data[front+1];
  7  * 判断对空：rear==front
  8  * 对长：rear-front
  9  */
 10 import java.util.Arrays;
 11 
 12 import java.util.Arrays;
 13 
 14 public class LoopQueue<E> {
 15     public Object[] data = null;
 16     private int maxSize; // 队列容量
 17     private int rear;// 队列尾，允许插入
 18     private int front;// 队列头，允许删除
 19     private int size=0; //队列当前长度
 20 
 21     public LoopQueue() {
 22         this(10);
 23     }
 24 
 25     public LoopQueue(int initialSize) {
 26         if (initialSize >= 0) {
 27             this.maxSize = initialSize;
 28             data = new Object[initialSize];
 29             front = rear = 0;
 30         } else {
 31             throw new RuntimeException("初始化大小不能小于0：" + initialSize);
 32         }
 33     }
 34 
 35     // 判空
 36     public boolean empty() {
 37         return size == 0;
 38     }
 39 
 40     // 插入
 41     public boolean add(E e) {
 42         if (size == maxSize) {
 43             throw new RuntimeException("队列已满，无法插入新的元素！");
 44         } else {
 45             data[rear] = e;
 46             rear = (rear + 1)%maxSize;
 47             size ++;
 48             return true;
 49         }
 50     }
 51 
 52     // 返回队首元素，但不删除
 53     public E peek() {
 54         if (empty()) {
 55             throw new RuntimeException("空队列异常！");
 56         } else {
 57             return (E) data[front];
 58         }
 59     }
 60 
 61     // 出队
 62     public E poll() {
 63         if (empty()) {
 64             throw new RuntimeException("空队列异常！");
 65         } else {
 66             E value = (E) data[front]; // 保留队列的front端的元素的值
 67             data[front] = null; // 释放队列的front端的元素
 68             front = (front+1)%maxSize;  //队首指针加1
 69             size--;
 70             return value;
 71         }
 72     }
 73 
 74     // 队列长度
 75     public int length() {
 76         return size;
 77     }
 78 
 79     //清空循环队列
 80     public void clear(){
 81         Arrays.fill(data, null);
 82         size = 0;
 83         front = 0;
 84         rear = 0;
 85     }
 86     
 87     public static void main(String[] args) {
 88         LoopQueue<Integer> queue=new LoopQueue<>();
 89         for (int i = 0; i < 5; i++) {
 90             queue.add(i);
 91         }
 92         for (int i = 0; i < queue.length(); i++) {
 93             System.out.print(queue.peek()+" ");
 94         }
 95         System.out.println();
 96         int size=queue.length();
 97         for (int i = 0; i < size; i++) {
 98             System.out.print(queue.poll()+" ");
 99         }
100     }
101 }

队列的链式存储结构实现

 1 package com.myutil.queue;
 2 
 3 public class LinkQueue<E> {
 4     // 链栈的节点
 5     private class Node<E> {
 6         E e;
 7         Node<E> next;
 8 
 9         public Node() {
10         }
11 
12         public Node(E e, Node next) {
13             this.e = e;
14             this.next = next;
15         }
16         
17     }
18     
19     private Node front;// 队列头，允许删除  
20     private Node rear;// 队列尾，允许插入  
21     private int size; //队列当前长度 
22     
23     public LinkQueue() {
24         front = null;
25         rear = null;
26     }
27     
28     //判空
29       public boolean empty(){
30           return size==0;
31       }
32       
33       //插入
34       public boolean add(E e){
35           if(empty()){    //如果队列为空
36               front = new Node(e,null);//只有一个节点，front、rear都指向该节点
37               rear = front;
38           }else{
39               Node<E> newNode = new Node<E>(e, null);
40               rear.next = newNode; //让尾节点的next指向新增的节点
41               rear = newNode; //以新节点作为新的尾节点
42           }
43           size ++;
44           return true;
45       }
46       
47       //返回队首元素，但不删除
48       public Node<E> peek(){
49           if(empty()){
50               throw new RuntimeException("空队列异常！");
51           }else{
52               return front;
53           }
54       }
55       
56       //出队
57       public Node<E> poll(){
58           if(empty()){
59               throw new RuntimeException("空队列异常！");
60           }else{
61               Node<E> value = front; //得到队列头元素
62               front = front.next;//让front引用指向原队列头元素的下一个元素
63               value.next = null; //释放原队列头元素的next引用
64               size --;
65               return value;
66           }        
67       }
68       
69       //队列长度
70       public int length(){
71           return size;
72       }
73       
74       public static void main(String[] args) {
75           LinkQueue<Integer> queue=new LinkQueue<>();
76           for (int i = 0; i < 5; i++) {
77               queue.add(i);
78           }
79           for (int i = 0; i < queue.length(); i++) {
80               System.out.print(queue.peek().e+" ");
81           }
82           System.out.println();
83           int size=queue.length();
84           for (int i = 0; i < size; i++) {
85               System.out.print(queue.poll().e+" ");
86           }
87       }
88 }

基于LinkedList实现队列结构

 * 使用java.util.Queue接口,其底层关联到一个LinkedList（双端队列）实例.
 * 
 * add----add()            会抛出异常
 * offer-----offer()
 * 
 * element-----element() 对为空，返回异常
 * peek------peek()
 * 
 * remove----remove() 对为空，返回异常
 * poll------poll()
 * 
 * empty-----isEmpty()

 1 package com.myutil.queue;
 2 
 3 /**
 4  * 使用java.util.Queue接口,其底层关联到一个LinkedList（双端队列）实例.
 5  * 
 6  * add----add()            会抛出异常
 7  * offer-----offer()
 8  * 
 9  * element-----element() 对为空，返回异常
10  * peek------peek()
11  * 
12  * remove----remove() 对为空，返回异常
13  * poll------poll()
14  * 
15  * empty-----isEmpty()
16  */
17 import java.util.LinkedList;
18 import java.util.Queue;
19 
20 public class QueueList<E> {
21     private Queue<E> queue = new LinkedList<E>();
22     
23     // 将指定的元素插入此队列（如果立即可行且不会违反容量限制），在成功时返回 true，
24     //如果当前没有可用的空间，则抛出 IllegalStateException。
25     public boolean add(E e){
26         return queue.add(e);
27     }
28     
29     //获取，但是不移除此队列的头。
30     public E element(){
31         return queue.element();
32     }
33     
34     //将指定的元素插入此队列（如果立即可行且不会违反容量限制），当使用有容量限制的队列时，
35     //此方法通常要优于 add(E)，后者可能无法插入元素，而只是抛出一个异常。
36     public boolean offer(E e){
37         return queue.offer(e);
38     }
39     
40     //获取但不移除此队列的头；如果此队列为空，则返回 null
41     public E peek(){
42         return queue.peek();
43     }
44     
45     //获取并移除此队列的头，如果此队列为空，则返回 null
46     public E poll(){
47         return queue.poll();
48     }
49     
50     //获取并移除此队列的头
51     public E remove(){
52         return queue.remove();
53     }
54     
55     //判空
56     public boolean empty() {
57         return queue.isEmpty();
58     }
59     public static void main(String[] args) {
60           QueueList<Integer> queueList=new QueueList<>();
61           for (int i = 0; i < 5; i++) {
62               queueList.add(i);
63           }
64           /*while (!queueList.empty()) {
65             System.out.println(queueList.peek());
66         }
67           System.out.println();
68           */
69           while (!queueList.empty()) {
70             System.out.print(queueList.poll()+" ");
71         }
72       }
73 }

本文参考地址：http://www.cnblogs.com/CherishFX/p/4608880.html 并在此博客的基础上进行了一些修改