Java：栈的几种不同实现

文章目录

• 1. 栈
• 2. 自己实现
• • 2.1. 顺序栈
  • 2.2. 链栈
• 3. 使用库

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());
	}
}

测试结果：

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());
	}
}

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();
	}
}

本文地址：https://blog.csdn.net/PursueLuo/article/details/109257552