Java使用链表实现栈_java 栈 链表实现

栈（Stack）：又称堆栈，栈和队列一样是一种操作受限制的表。

栈是一种特殊的线性表，特殊之处在于它遵从后进先出原则，它只允许在表的一端进行删除和插入操作，人们把这端称之为栈顶，栈顶的第一个元素为栈顶元素，相对地，把另一端称为栈底。向一个栈插入新元素又称为进栈或入栈，就是把该元素放到栈顶元素的上面，使之成为新的栈顶元素，从一个栈删除元素又称为出栈或退栈，它是把栈顶元素删除掉，使其下面的相邻元素成为新的栈顶元素。

（1） 初始化（创建）栈。

a) 构造函数初始化栈，size表示栈内数量，head指向栈顶元素

b) Node为节点内部类，记录当前元素和指向下一个元素的指针

public class StackLinkedList {
 private int size; 
 private Node head;//头节点
 public StackLinkedList(){
  size = 0;
  head = null;
  }
  class Node{
  public Object data;// 每个节点的数据
  public Node next;// 每个节点指向下一个节点的连接
  public Node(Object data) {
   this.data = data;
      }
   }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

（2） 入栈，向栈顶添加元素

a) 根据传递进来的元素创建节点。

b) 判断添加的是否为第一个节点，若是则之间将头节点设置为当前节点，若不是则将当创建的节点的next指向头节点。

c) 最后将刚创建的节点设置为头节点，size自增一。

public void insertHead(Object value){
  Node newNode = new Node(value);
  if (size == 0) {
   head = newNode;
  }else {
   newNode.next = head;
   head = newNode;
  }
  size++;
 }
1
2
3
4
5
6
7
8
9
10

（3） 出栈，向栈顶移除元素

a) 判断栈内元素是否大于零，为零不可移除。

b) 将头节点设置为头节点的next，size自减一。

public Node delectHead() {
  if (size > 0) {
   Node oldHead = head;
   head = head.next;
   size--;
   return oldHead;
  }else {
   return null;
  }
 }
1
2
3
4
5
6
7
8
9
10

（4） 判断栈内元素是否为空

//判断栈内元素是否为空
 public boolean isNull() {
  return size == 0;
 }
1
2
3
4

（5） 打印栈内元素信息

//打印
 public void printNode() {
  if (size > 0) {
   Node node = head;
   if (size == 1) {
     System.out.println("["+node.data+"]");
     return;
   }
   int item = size;
   System.out.print("[");
   while (item > 0) {
    if (node.next == null) {
     System.out.print(node.data + "]");
    }else {
     System.out.print(node.data + ",");
    }
    node = node.next;
    item--;
   }
  }else {
   System.out.println("[]");
  }
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23