java 数据结构之栈与队列

时间:2022-01-13 08:07:04

java 数据结构队列

一:对列

队列是一种先进先出的数据结构

实现代码:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
package Queue;
 
/*
 * 使用java构建队列,并模拟实现队列的入队和出对方法
 */
 
public class Queue {   //队列类
 
  private int maxSize; //定义队列的长度
  private int[] arrQueue;   //队列
  private int rear;   //定义队列的尾指针
  private int front;  //定义队列的头指针
  private int empty; //元素的个数
   
  public Queue(int s)  //初始化构造函数
  {
    maxSize = s;
    arrQueue = new int[s];
    rear = -1;
    front=0;
    empty = 0;
  }
   
  //实现插入方法
  public void insert(int m)
  {
    if(rear == maxSize-1//处理循环
      rear = -1;   
    arrQueue[++rear] = m;  //对尾指针加一,把值放在队列结尾
    empty++;   //队列元素个数加1
    System.out.println("队列入队元素 为:" + m);
  }
   
  //实现出栈的方法,即取得队列的头元素
  public int remove()
  {
    int temp = arrQueue[front++]; //将栈顶元素赋值给temp,栈顶指针加1
    if(front == maxSize) //处理循环
      front = 0;
    empty--; //元素个数-1
    return temp;
  }
   
  //判断队列是否为空
  public boolean isEmpty()
  {
    return (empty==0);
  }
   
  //判断对列是否为满
  public boolean isFull()
  {
    return (empty == maxSize);
  }
   
  //返回队列长度
  public int qLong()
  {
    return empty;
  }
   
  public static void main(String[] args) {
    Queue q = new Queue(5); //初始化队列为5个元素
     
    q.insert(1);
    q.insert(2);
    q.insert(3);
    q.insert(4);
    q.insert(5);
     
    int t1 = q.remove();
    System.out.println("队列元素出队:" + t1);
    int t2 = q.remove();
    System.out.println("队列元素出队:" + t2);
     
    System.out.println("队列是否为空:" + q.isEmpty());
    System.out.println("队列是否为满:" + q.isFull());
    System.out.println("队列的长度:" + q.qLong());
  }
   
}

二:栈

栈是一种先进后出的数据结构

1:使用数组模拟栈

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
package Statck;
/*
 * 使用java构建栈,并模拟实现栈的入栈和出栈方法
 * 使用数组实现
 */
 
public class Statck1 {
 
  private int maxSize;   //栈的最多元素数
  private int top;  //栈顶指针
  private int len;   //栈的深度
  private int[] arrStack; // 模拟栈
   
  //栈的初始化
  public Statck1(int s){
    maxSize = s;
    len =0;
    top= -1;
    arrStack = new int[s];
  }
   
  //获取栈的长度
  public int getLen(){
    return len;
  }
   
  //获取当前栈还能插入多少个f元素
  public int getLeaveLen(){
    return (maxSize-len);
  }
  //判断栈是否满
  public boolean isFull(){
    return (len==maxSize);
  }
   
  //判断栈是否为空
  public boolean isEmpty(){
    return (len ==0);
  }
   
  //元素入栈
  public void inStack(int s)
  {
    arrStack[++top] = s; //栈顶指针加1,入栈
    System.out.println("元素入栈:" + s);
    len ++ ;//栈深度+1
  }
   
  //元素出栈
  public int outStack()
  {
    int temp = arrStack[top--];//赋值之后减1
    System.out.println("元素出栈:" + temp);
    len--;  //栈深度-1
    return temp;
  }
   
  public static void main(String[] args) {
    Statck1 s = new Statck1(5);
     
    s.inStack(1);
    s.inStack(2);
    s.inStack(3);
    s.inStack(4);
    s.inStack(5);
     
    s.outStack();
    s.outStack();
    System.out.println("栈的长度:" + s.getLen());
    System.out.println("还能入栈元素个数:" + s.getLeaveLen());
    System.out.println("栈的是否为空:" + s.isEmpty());
    System.out.println("栈的是否为满:" + s.isFull());
  }
}

2:使用链表模拟栈

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
package Statck;
 
import java.util.ArrayList;
import java.util.EmptyStackException;
import java.util.List;
 
/*
 * 使用java构建栈,并模拟实现栈的入栈和出栈方法
 * 使用链表实现
 */
 
public class Statck2<E extends Object> { 
   
  private List<E> statck = new ArrayList<E>(); 
   
  public Statck2(){
       //栈的初始化
  }
   
  //清空栈
  public void clear(){
    statck.clear();
    System.out.println("清空栈..........");
  }
  //判断栈是否为空
  public boolean isEmpty(){
    return statck.isEmpty();
  }
  //获取栈顶元素
  public E getTop(){
    if(isEmpty())
      return null;
    return statck.get(0);
  }
   
  //弹出栈操作
  public E pop(){
    if (isEmpty()) 
      throw new EmptyStackException(); 
    System.out.println(statck.size() + "\t 出栈");
    return statck.remove(statck.size() - 1); 
  }
   
  //压入栈操作
  public void push(E e){
    statck.add(e);
    System.out.println(e + "\t 入栈");
  }
   
  //获取当前栈的深度
  public int getStatckSize(){
    if(isEmpty())
      throw new EmptyStackException();
    return statck.size();
  }
   
  public static void main(String[] args) {
    Statck2 s = new Statck2();
    s.clear();      //清空栈
    System.out.println("当前栈是否为空:" + s.isEmpty());
    s.push(1);
    s.push(2);
    s.push(3);
     
    s.pop();
    System.out.println("当前栈的深度为:" + s.getStatckSize());
    System.out.println("当前栈顶元素为:" + s.getTop());
  }
   
}

感谢阅读,希望能帮助到大家,谢谢大家对本站的支持,如有疑问请留言或者到本站社区交流讨论,大家共同进步!

原文链接:http://blog.csdn.net/gamer_gyt/article/details/51457106