Java：栈的几种不同实现

末蓝、 2021-09-24 21:32 281阅读 0赞

### 文章目录 ###

*  1. 栈
 *  2. 自己实现
 *   *  2.1. 顺序栈
     *   *  2.1.1. 入栈
         *  2.1.2. 出栈
         *  2.1.3. 测试结果
     *  2.2. 链栈
     *   *  2.2.1. 入栈
         *  2.2.2. 出栈
         *  2.3.3. 测试结果
 *  3. 使用库
 *   *  3.1. ArrayList
     *  3.2. LinkedList
     *  3.3. ArrayDeque

# 1. 栈 #

满足先进后出（FILO）规则，且只能在一端进行操作的数据结构，称为**栈**。

*  FILO：先进后出，与之相反的是先进先出（FIFO）；
 *  栈顶：进行“入”和“出”操作的一端；
 *  栈底：固定不变的一端。

不同的存储形式，对应了不同的栈。  
由顺序表表示的栈称为顺序栈，由链表表示的栈栈。

# 2. 自己实现 #

## 2.1. 顺序栈 ##

定义：

public class MyStack
    { 
    	private int[] array;    // 顺序表
    	private int capacity;	// 顺序表的容量
    	private int top;	    // 栈顶指针
    	
    	// 带参数构造函数
    	public MyStack(int capacity)
    	{ 
    		this.array = new int[capacity];
    		this.capacity = capacity;
    		this.top = 0;
    	}
    	
    	// 默认构造函数
    	public MyStack()
    	{ 
    		this(16);
    	}
    }

### 2.1.1. 入栈 ###

由于顺序存储存在空间不足的情况（数组大小过小），因此顺序栈的入栈需要考虑两点，分别是：

*  入栈操作在栈顶进行；
 *  入栈需要考虑空间不足；

// 判断栈满状态
    private boolean isFull()
    { 
    	return this.top == this.capacity;
    }
    
    // 在栈满的状态下，扩增顺序表的容量
    private void enlargeSpace()
    { 
    	if (isFull())
    	{ 
    		int enlargeCapacity = this.capacity + (this.capacity >> 1);
    		int[] enlargeArray = new int[enlargeCapacity];
    		System.arraycopy(this.array, 0, enlargeArray, 0, this.capacity);
    		this.array = enlargeArray;
    		this.capacity = enlargeCapacity;
    	}
    }
    
    // 在保证有多余空间的情况下，将元素放入栈顶
    public void push(int value)
    { 
    	enlargeSpace();
    	this.array[this.top++] = value;
    }

### 2.1.2. 出栈 ###

顺序栈的出栈需要考虑两点，分别是：

*  出栈操作在栈顶进行；
 *  栈可能为空；

// 栈空时，抛出异常；非空时，返回栈顶元素
    public int pop() throws EmptyStackException
    { 
    	if (isEmpty())
    	{ 
    		throw new EmptyStackException();
    	}
    	return this.array[--this.top];
    }

### 2.1.3. 测试结果 ###

源代码：

package louis;
    
    import java.util.EmptyStackException;
    
    public class MyStack
    { 
    	private int[] array;
    	private int capacity;
    	private int top;
    	
    	public MyStack(int capacity)
    	{ 
    		this.array = new int[capacity];
    		this.capacity = capacity;
    		this.top = 0;
    	}
    	
    	public MyStack()
    	{ 
    		this(3);
    	}
    	
    	public boolean isEmpty()
    	{ 
    		return this.top == 0;
    	}
    	
    	private boolean isFull()
    	{ 
    		return this.top == this.capacity;
    	}
    	
    	private void enlargeSpace()
    	{ 
    		if (isFull())
    		{ 
    			int enlargeCapacity = this.capacity + (this.capacity >> 1);
    			int[] enlargeArray = new int[enlargeCapacity];
    			System.arraycopy(this.array, 0, enlargeArray, 0, this.capacity);
    			this.array = enlargeArray;
    			this.capacity = enlargeCapacity;
    		}
    	}
    	
    	public void push(int value)
    	{ 
    		enlargeSpace();
    		this.array[this.top++] = value;
    	}
    	
    	public int pop() throws EmptyStackException
    	{ 
    		if (isEmpty())
    		{ 
    			throw new EmptyStackException();
    		}
    		return this.array[--this.top];
    	}
    	
    	public static void main(String[] args)
    	{ 
    		MyStack stack = new MyStack();
    		stack.push(10);
    		stack.push(20);
    		stack.push(30);
    		System.out.println(stack.pop());
    		System.out.println(stack.pop());
    		System.out.println(stack.pop());
    		System.out.println(stack.pop());
    	}
    }

测试结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1B1cnN1ZUx1bw_size_16_color_FFFFFF_t_70_pic_center]

## 2.2. 链栈 ##

首先定义链栈中的节点：一个存储值的域和一个指向下一个节点的域

public class MyStackNode
    { 
    	private int value; 	       // 值域
    	private MyStackNode next;  // 指针域
    	
    	public MyStackNode(int value)
    	{ 
    		this.value = value;
    	}
    	
    	public MyStackNode(int value, MyStackNode next)
    	{ 
    		this(value);
    		this.next = next;
    	}
    	
    	public int getValue()
    	{ 
    		return value;
    	}
    	
    	public void setValue(int value)
    	{ 
    		this.value = value;
    	}
    	
    	public MyStackNode getNext()
    	{ 
    		return next;
    	}
    	
    	public void setNext(MyStackNode next)
    	{ 
    		this.next = next;
    	}
    }

链栈的定义：

public class MyStack
    { 
    	private final MyStackNode head;
    	
    	public MyStack()
    	{ 
    		this.head = new MyStackNode(0, null);
    	}
    }

### 2.2.1. 入栈 ###

由于链式存储不存在空间不足的情况（假设内存充足），因此链栈的入栈操作只需考虑一点，是

*  入栈操作在栈顶进行

这里补充说明一句，为了效率，采用头插法。即栈顶在头指针一端。

public boolean isEmpty()
    { 
    	return this.head.getNext() == null;
    }
    
    public void push(int value)
    { 
    	MyStackNode node = new MyStackNode(value);
    	if (!isEmpty())
    	{ 
    		node.setNext(this.head.getNext());
    	}
    	this.head.setNext(node);
    }

### 2.2.2. 出栈 ###

链栈的出栈操作需要考虑两点，分别是：

*  链栈为空；
 *  出栈操作在栈顶进行；

public int pop() throws EmptyStackException
    { 
    	if (isEmpty())
    	{ 
    		throw new EmptyStackException();
    	}
    	MyStackNode node = this.head.getNext();
    	this.head.setNext(node.getNext());
    	return node.getValue();
    }

### 2.3.3. 测试结果 ###

源代码：

package louis;
    
    import java.util.EmptyStackException;
    
    public class MyStack
    { 
    	private final MyStackNode head;
    	
    	public MyStack()
    	{ 
    		this.head = new MyStackNode(0, null);
    	}
    	
    	public boolean isEmpty()
    	{ 
    		return this.head.getNext() == null;
    	}
    	
    	public int pop() throws EmptyStackException
    	{ 
    		if (isEmpty())
    		{ 
    			throw new EmptyStackException();
    		}
    		MyStackNode node = this.head.getNext();
    		this.head.setNext(node.getNext());
    		return node.getValue();
    	}
    	
    	public void push(int value)
    	{ 
    		MyStackNode node = new MyStackNode(value);
    		if (!isEmpty())
    		{ 
    			node.setNext(this.head.getNext());
    		}
    		this.head.setNext(node);
    	}
    	
    	public static void main(String[] args)
    	{ 
    		MyStack stack = new MyStack();
    		stack.push(10);
    		stack.push(20);
    		stack.push(30);
    		System.out.println(stack.pop());
    		System.out.println(stack.pop());
    		System.out.println(stack.pop());
    		System.out.println(stack.pop());
    	}
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1B1cnN1ZUx1bw_size_16_color_FFFFFF_t_70_pic_center 1]

# 3. 使用库 #

## 3.1. ArrayList ##

package louis;
    
    import java.util.ArrayList;
    import java.util.EmptyStackException;
    
    public class MyStack
    { 
    	private final ArrayList<Integer> stack;
    	
    	public MyStack()
    	{ 
    		this.stack = new ArrayList<Integer>();
    	}
    	
    	public void push(int value)
    	{ 
    		this.stack.add(value);
    	}
    	
    	public int pop() throws EmptyStackException
    	{ 
    		if (this.stack.isEmpty())
    		{ 
    			throw new EmptyStackException();
    		}
    		return this.stack.remove(this.stack.size() - 1);
    	}
    }

## 3.2. LinkedList ##

package louis;
    
    import java.util.EmptyStackException;
    import java.util.LinkedList;
    
    public class MyStack
    { 
    	private final LinkedList<Integer> stack;
    	
    	public MyStack()
    	{ 
    		this.stack = new LinkedList<Integer>();
    	}
    	
    	public void push(int value)
    	{ 
    		this.stack.offerFirst(value);
    	}
    	
    	public int pop() throws EmptyStackException
    	{ 
    		if (this.stack.size() == 0)
    		{ 
    			throw new EmptyStackException();
    		}
    		return this.stack.pollFirst();
    	}
    }

## 3.3. ArrayDeque ##

package louis;
    
    import java.util.EmptyStackException;
    import java.util.ArrayDeque;
    
    public class MyStack
    { 
    	private final ArrayDeque<Integer> stack;
    	
    	public MyStack()
    	{ 
    		this.stack = new ArrayDeque<Integer>();
    	}
    	
    	public void push(int value)
    	{ 
    		this.stack.offerFirst(value);
    	}
    	
    	public int pop() throws EmptyStackException
    	{ 
    		if (this.stack.size() == 0)
    		{ 
    			throw new EmptyStackException();
    		}
    		return this.stack.pollFirst();
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1B1cnN1ZUx1bw_size_16_color_FFFFFF_t_70_pic_center]: /images/20210923/dc488ad6a3c342ce86cf92c3d4dcedd7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1B1cnN1ZUx1bw_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20210923/fe871952a6204a439609a3beb57bfdde.png