欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构栈---java实现

程序员文章站 2022-07-10 20:29:17
...

数据结构栈,原则是先进后出,就是把羽毛球装到球桶里面,最先放进去的羽毛球,一定是最后拿出来的(排除掉球桶底掉的情况);最后放进去的球,一定是最先拿出来的。

栈的操作:

push--压栈,将元素压入栈,栈的大小加1(把羽毛球放进球桶,为啥叫压栈,就是放到最底部)

pop---出栈,将栈顶的元素取出,栈的大小减1(从球桶中取出一个羽毛球,只能取出第一个羽毛球吧)

peek---查看栈顶元素

这里我用了两种实现方式,一种是数组实现,一种是借助LinkedList实现。

数组实现:

package com.no5;

/**
 * 栈的实现---数组实现
 */
public class MyStack {

	private int maxSize;
	private int top;
	private int[] arr;

	/**
	 * 栈的初始化
	 * 
	 * @param size
	 */
	public MyStack(int size) {
		maxSize = size;
		top = -1;
		arr = new int[maxSize];
	}

	/**
	 * 压栈
	 * 
	 * @param value
	 */
	public void push(int value) {
		arr[++top] = value;
	}

	/**
	 * 弹栈
	 * 
	 * @return
	 */
	public int pop() {
		return arr[top--];
	}

	/**
	 * 访问栈顶元素
	 * 
	 * @return
	 */
	public int peek() {
		return arr[top];
	}

	/**
	 * 判断是否栈满
	 * 
	 * @return
	 */
	public boolean isFull() {
		return maxSize - 1 == top;
	}

	/**
	 * 判断栈是否为空
	 * 
	 * @return
	 */
	public boolean isEmpty() {
		return top == -1;
	}

}

LinkedList实现:

package com.no5;

import java.util.LinkedList;

/**
 * 栈的实现---链表实现
 * 
 * @author yushen
 * 
 */
public class MyStack2 {

	private LinkedList<Integer> list = new LinkedList<>();
	private int size;

	/**
	 * 栈的初始化
	 */
	public MyStack2() {
		list = new LinkedList<>();
		size = 0;
	}

	/**
	 * 压栈
	 * 
	 * @param value
	 */
	public void push(int value) {
		list.addFirst(value);
		size++;
	}

	/**
	 * 弹栈
	 * 
	 * @return
	 */
	public int pop() {
		size--;
		return list.removeFirst();
	}

	/**
	 * 访问栈顶元素
	 * 
	 * @return
	 */
	public int peek() {
		return list.getFirst();
	}

	/**
	 * 判断是否栈满
	 * 
	 * @return
	 */
	public boolean isFull() {
		return list.size() == size;
	}

	/**
	 * 判断栈是否为空
	 * 
	 * @return
	 */
	public boolean isEmpty() {
		return list.isEmpty();
	}
}