数据结构Java实现----栈和队列

2018-07-23 05:33:07来源：博客园阅读 ()

一、线性栈

ArrayStack类

  1 package stack;
  2 
  3 // 线性栈
  4 public class ArrayStack implements Stack {
  5     private Object[] dataArray = null;
  6     private int maxSize = 0; // 栈的最大容量
  7     private int foot = -1; // 栈顶指针
  8     private int elementCount = 0; // 栈中含有元素个数
  9 
 10     // 无参构造
 11     public ArrayStack() {
 12 
 13     }
 14 
 15     // 构造一个maxSize大小的栈
 16     public ArrayStack(int maxSize) {
 17         if (maxSize <= 0)
 18             return;
 19         this.maxSize = maxSize;
 20         this.dataArray = new Object[maxSize];
 21     }
 22 
 23     // 设置栈的容量
 24     public boolean setMaxSize(int maxSize) {
 25         if (this.maxSize != 0)
 26             return false;
 27         this.maxSize = maxSize;
 28         this.dataArray = new Object[this.maxSize];
 29         return true;
 30     }
 31 
 32     // 得到栈的容量
 33     public int getMaxSize() {
 34         return this.maxSize;
 35     }
 36 
 37     // 得到栈含有元素的个数
 38     public int getElementCount() {
 39         return this.elementCount;
 40     }
 41 
 42     // 判空
 43     @Override
 44     public boolean IsEmpty() {
 45         return this.elementCount == 0;
 46     }
 47 
 48     // 判满
 49     @Override
 50     public boolean IsFull() {
 51         return this.elementCount == this.maxSize;
 52     }
 53 
 54     // 入栈
 55     @Override
 56     public boolean Push(Object data) {
 57         if (data == null)
 58             return false;
 59         if (this.IsFull())
 60             return false;
 61 
 62         // 指针上移 添加元素
 63         this.dataArray[++this.foot] = data;
 64         this.elementCount++;
 65         return true;
 66     }
 67 
 68     // 出栈
 69     @Override
 70     public Object Pop() {
 71         if (this.IsEmpty())
 72             return null;
 73 
 74         // 取出数据
 75         Object data = this.dataArray[this.foot];
 76         // 移除数据 指针下移
 77         this.dataArray[this.foot--] = null;
 78         this.elementCount--;
 79         return data;
 80     }
 81 
 82     // 查看栈顶元素
 83     @Override
 84     public Object GetTop() {
 85         if (this.IsEmpty())
 86             return null;
 87         return this.dataArray[foot];
 88     }
 89 
 90     // 打印1
 91     public void print() {
 92         if (this.IsEmpty()) {
 93             System.out.println("空栈");
 94             return;
 95         }
 96         int index = this.foot; // 栈顶指针
 97         for (; index >= 0;)
 98             System.out.print(this.dataArray[index--] + "  ");
 99     }
100 
101     // 判栈相等
102     @Override
103     public boolean equals(Object obj) {
104         if (obj == null)
105             return false;
106 
107         // 是ArrayotherStack类
108         if (obj instanceof ArrayStack) {
109             // 造型下转
110             ArrayStack otherStack = (ArrayStack) obj;
111 
112             // 含有元素相等
113             if (this.elementCount != otherStack.elementCount)
114                 return false;
115 
116             // 每个位置上的元素相等
117             int index = this.elementCount; // 比较次数
118             int thisFoot = this.foot; // 当前对象栈顶指针
119             int otherFoot = otherStack.foot; // 比较对象栈顶指针
120             for (; index > 0; --index) {
121                 if (this.dataArray[thisFoot] != otherStack.dataArray[otherFoot])
122                     return false;
123 
124                 // 指针下移
125                 thisFoot--;
126                 otherFoot--;
127             }
128             return true;
129         }
130         return false;
131     }
132     
133     // 置空
134     public boolean delete(){
135         this.dataArray = null;
136         this.elementCount  = 0;
137         this.foot = -1;
138         this.maxSize = 0;
139         return true;
140     }
141 
142 }

ArrayStack

TestArrayStack类

 1 package Test;
 2 
 3 import stack.ArrayStack;
 4 
 5 // 线性栈测试类
 6 public class TestArrayStack {
 7 
 8     public static void main(String[] args) {
 9         // 创建一个空栈
10         ArrayStack stack1 = new ArrayStack();
11         System.out.println("设置stack1的容量为5:" + stack1.setMaxSize(5));
12         System.out.println("重复设置stack1的容量:" + stack1.setMaxSize(5));
13         System.out.println("向stack1添加：5 12 10 14 16 20");
14         System.out.print(stack1.Push(5) + "  " + stack1.Push(12) + "  ");
15         System.out.print(stack1.Push(10) + "  " + stack1.Push(14) + "  ");
16         System.out.print(stack1.Push(16) + "  " + stack1.Push(20) + "   \n");
17         stack1.print();
18         System.out.println("\n出栈6次");
19         for (int index = 6; index > 0; --index)
20             System.out.print(stack1.Pop() + "  ");
21         stack1.print();
22 
23         // 比较栈是否相同
24         ArrayStack stack2 = new ArrayStack(3);
25         ArrayStack stack3 = new ArrayStack(3);
26         ArrayStack stack4 = new ArrayStack(3);
27         ArrayStack stack5 = new ArrayStack(2);
28         System.out.print("比较栈是否相同");
29         stack2.Push(2);
30         stack2.Push(3);
31         stack3.Push(3);
32         stack3.Push(2);
33         stack4.Push(2);
34         stack4.Push(3);
35         stack5.Push(2);
36         stack5.Push(3);
37         System.out.print("stack2: ");
38         stack2.print();
39         System.out.print("stack3: ");
40         stack3.print();
41         System.out.print("stack4: ");
42         stack4.print();
43         System.out.print("stack5：");
44         stack5.print();
45         System.out.println();
46         System.out.print("stack2:stack3 " + stack2.equals(stack3) + "  ");
47         System.out.print("stack2:stack4 " + stack2.equals(stack4) + "  ");
48         System.out.print("stack2:stack5 " + stack2.equals(stack5) + "  ");
49 
50     }
51 }

TestArrayStack

打印

1 设置stack1的容量为5:true
2 重复设置stack1的容量:false
3 向stack1添加：5 12 10 14 16 20
4 true  true  true  true  true  false   
5 16  14  10  12  5  
6 出栈6次
7 16  14  10  12  5  null  空栈
8 比较栈是否相同stack2: 3  2  stack3: 2  3  stack4: 3  2  stack5：3  2  
9 stack2:stack3 false  stack2:stack4 true  stack2:stack5 true

TestArrayStack-console

二、链式栈

LinkStack类

  1 package stack;
  2 
  3 // 链式栈
  4 public class LinkStack implements Stack {
  5     private Node root = null; // 根节点
  6     private int maxSize = 0; // 容量
  7     private int elementCount = 0; // 元素个数
  8 
  9     class Node {
 10         Object data = null; // 数据域
 11         Node next = null; // 指针域
 12 
 13         Node(Object data) {
 14             this.data = data;
 15         }
 16     }
 17 
 18     public LinkStack() {
 19 
 20     }
 21 
 22     public LinkStack(int maxSize) {
 23         this.maxSize = maxSize;
 24     }
 25 
 26     public boolean SetMaxSize(int maxSize) {
 27         if (this.maxSize != 0)
 28             return false;
 29         this.maxSize = maxSize;
 30         return true;
 31     }
 32 
 33     @Override
 34     public boolean IsEmpty() {
 35         return this.elementCount == 0;
 36     }
 37 
 38     @Override
 39     public boolean IsFull() {
 40         return this.elementCount == this.maxSize;
 41     }
 42 
 43     @Override
 44     public boolean Push(Object data) {
 45         if (data == null)
 46             return false;
 47         if (this.IsFull())
 48             return false;
 49 
 50         // 封装结点
 51         Node node = new Node(data);
 52         this.elementCount++;
 53         if (this.IsEmpty()) {
 54             this.root = node;
 55             return true;
 56         }
 57         node.next = this.root;
 58         this.root = node;
 59         return true;
 60     }
 61 
 62     @Override
 63     public Object Pop() {
 64         if (this.IsEmpty())
 65             return null;
 66 
 67         // 保存第二个结点信息
 68         Object data = this.root.data;
 69         if (this.elementCount > 1)
 70             this.root = this.root.next;
 71         this.elementCount--;
 72         return data;
 73     }
 74 
 75     @Override
 76     public Object GetTop() {
 77         return this.root.data;
 78     }
 79 
 80     @Override
 81     public boolean equals(Object obj) {
 82         if (obj == null)
 83             return false;
 84 
 85         // 是LinkStack类
 86         if (obj instanceof LinkStack) {
 87             LinkStack otherStack = (LinkStack) obj;
 88             if (this.elementCount != otherStack.elementCount)
 89                 return false;
 90             if (this.elementCount == 0) // 都不含有元素则一定相等
 91                 return true;
 92             Node thisNode = this.root;
 93             Node otherNode = this.root;
 94 
 95             while (true) {
 96                 if (thisNode.data.equals(otherNode.data))
 97                     return false;
 98 
 99                 if (thisNode.next == null)
100                     break;
101                 thisNode = thisNode.next;
102                 otherNode = otherNode.next;
103             }
104             return true;
105         }
106         return false;
107     }
108 
109     public void print() {
110         if (this.IsEmpty()) {
111             System.out.println("空栈");
112             return;
113         }
114         Node node = this.root;
115         for (int index = this.elementCount; index > 0; index--) {
116             System.out.print(node.data + " ");
117             node = node.next;
118         }
119     }
120 
121 }

LinkStack

TestLinkStack类

 1 package Test;
 2 
 3 import stack.LinkStack;
 4 
 5 // 链式栈测试类
 6 public class TestLinkStack {
 7 
 8     public static void main(String[] args) {
 9         // 创建一个空栈
10         LinkStack stack1 = new LinkStack();
11         System.out.println("设置stack1的容量为5:" + stack1.SetMaxSize(5));
12         System.out.println("重复设置stack1的容量:" + stack1.SetMaxSize(5));
13         System.out.println("向stack1添加：5 12 10 14 16 20");
14         System.out.print(stack1.Push(5) + "  " + stack1.Push(12) + "  ");
15         System.out.print(stack1.Push(10) + "  " + stack1.Push(14) + "  ");
16         System.out.print(stack1.Push(16) + "  " + stack1.Push(20) + "   \n");
17         stack1.print();
18         System.out.println("\n出栈6次");
19         for (int index = 6; index > 0; --index)
20             System.out.print(stack1.Pop() + "  ");
21         stack1.print();
22 
23         // 比较栈是否相同
24         LinkStack stack2 = new LinkStack(3);
25         LinkStack stack3 = new LinkStack(3);
26         LinkStack stack4 = new LinkStack(3);
27         LinkStack stack5 = new LinkStack(2);
28 
29         stack2.Push(2);
30         stack2.Push(3);
31         stack3.Push(3);
32         stack3.Push(2);
33         stack4.Push(2);
34         stack4.Push(3);
35         stack5.Push(2);
36         stack5.Push(3);
37         System.out.print("stack2:");
38         stack2.print();
39         System.out.print("stack3:");
40         stack3.print();
41         System.out.print("stack4:");
42         stack4.print();
43         System.out.print("stack5：");
44         stack5.print();
45         System.out.print("stack2:stack3 " + stack2.equals(stack3) + "  ");
46         System.out.print("stack2:stack4 " + stack2.equals(stack4) + "  ");
47         System.out.print("stack2:stack5 " + stack2.equals(stack5) + "  ");
48 
49     }
50 
51 }

TestLinkStack

打印

1 设置stack1的容量为5:true
2 重复设置stack1的容量:false
3 向stack1添加：5 12 10 14 16 20
4 true  true  true  true  true  false   
5 16 14 10 12 5 
6 出栈6次
7 16  14  10  12  5  null  空栈
8 stack2: 3 2 stack3: 2 3 stack4: 3 2 stack5：3 2 stack2:stack3 false  stack2:stack4 false  stack2:stack5 false