基于双向链表的栈和队列实现

Java基础

浏览数:55

2019-10-8

AD:资源代下载服务

栈的实现:     栈(stack)又名堆栈,它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶(top),相对地,把另一端称为栈底(bottom)。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。   栈接口:

 1 /**
 2  * 描述栈的基本操作
 3  */
 4 public interface IStack<T> {
 5     /**
 6      * 元素入栈
 7      */
 8     void push(T e);
 9 
10     /**
11      * 弹出栈顶(栈中无此元素)
12      */
13     T pop();
14 
15     /**
16      * 是否空栈
17      */
18     boolean empty();
19 
20     /**
21      * 栈内元素个数
22      */
23     int getSize();
24 
25     /**
26      * 查看栈顶元素,不弹出
27      */
28     T peek();
29 }

  栈的实现:


 1 import java.util.EmptyStackException;
 2 
 3 // DoubleLinkedList ListNode 前面的博客已经介绍 
 4 public class MyStack<T> extends DoubleLinkedList<T> implements IStack<T> {
 5     @Override
 6     public void push(T e) {
 7         super.add(e);
 8     }
 9 
10     @Override
11     public T pop() {
12         if (size <= 0)
13             throw new EmptyStackException();
14         ListNode<T> the = super.last.getPre();
15         T res = the.getData();
16 
17         the.getPre().setNext(last);
18         last.setPre(the.getPre());
19         the.setNext(null);
20         the.setPre(null);
21         size--;
22         return res;
23     }
24 
25     @Override
26     public boolean empty() {
27         return getSize() == 0;
28     }
29 
30     @Override
31     public int getSize() {
32         return super.getSize();
33     }
34 
35     @Override
36     public T peek() {
37         return last.getPre().getData();
38     }
39 }

队列的实现:

  队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。队列中没有元素时,称为空队列。   队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队,从队列中删除一个队列元素称为出队。因为队列只允许在一端插入,在另一端删除,所以只有最早进入队列的元素才能最先从队列中删除,故队列又称为先进先出(FIFO—first in first out)线性表。队列结构与日常生活中排对等候服务的模型是一致的,最早进入队列的人,最早得到服务并从队首离开;最后到来的只能排在队列的最后,最后得到服务并最后离开。   队列接口:

 1 /**
 2  * 描述队列的基本操作
 3  */
 4 public interface IQueue<T> {
 5     // 入队
 6     void enqueue(T e);
 7 
 8     // 出队
 9     T dequeue();
10 
11     // 返回队列的大小
12     int getSize();
13 
14     // 判断队列是否为空
15     boolean empty();
16 
17     // 取队首元素
18     T peek();
19 }

  队列的实现:


 1 //DoubleLinkedList ListNode 前面的博客已经介绍 
 2 public class MyQueue<T> extends DoubleLinkedList<T> implements IQueue<T> {
 3     @Override
 4     public void enqueue(T e) {
 5         super.add(e);
 6     }
 7 
 8     @Override
 9     public T dequeue() {
10         ListNode<T> h = first.getNext();
11         first.setNext(h.getNext());
12         h.getNext().setPre(first);
13         h.setPre(null);
14         h.setNext(null);
15         size--;
16         return h.getData();
17     }
18 
19     @Override
20     public boolean empty() {
21         return getSize() == 0;
22     }
23 
24     @Override
25     public T peek() {
26         return first.getNext().getData();
27     }
28 }

  

作者:|旧市拾荒|