Java:栈的几种不同实现

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

测试结果:
Java:栈的几种不同实现

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

Java:栈的几种不同实现

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

猜你喜欢