Java 实现栈的三种方式

Java 实现栈的三种方式

栈：LIFO（后进先出），自己实现一个栈，要求这个栈具有push()、pop()（返回栈顶元素并出栈）、peek() （返回栈顶元素不出栈）、isEmpty()这些基本的方法。

一、采用数组实现栈

提示：每次入栈之前先判断栈的容量是否够用，如果不够用就用Arrays.copyOf()进行扩容

import java.util.Arrays;

/**

* 数组实现栈

* @param

*/

class Mystack1 {

//实现栈的数组

private Object[] stack;

//数组大小

private int size;

Mystack1() {

stack = new Object[10];//初始容量为10

}

//判断是否为空

public boolean isEmpty() {

return size == 0;

}

//返回栈顶元素

public T peek() {

T t = null;

if (size > 0)

t = (T) stack[size - 1];

return t;

}

public void push(T t) {

expandCapacity(size + 1);

stack[size] = t;

size++;

}

//出栈

public T pop() {

T t = peek();

if (size > 0) {

stack[size - 1] = null;

size--;

}

return t;

}

//扩大容量

public void expandCapacity(int size) {

int len = stack.length;

if (size > len) {

size = size * 3 / 2 + 1;//每次扩大50%

stack = Arrays.copyOf(stack, size);

}

}

}

public class ArrayStack {

public static void main(String[] args) {

Mystack1 stack = new Mystack1<>();

System.out.println(stack.peek());

System.out.println(stack.isEmpty());

stack.push("java");

stack.push("is");

stack.push("beautiful");

stack.push("language");

System.out.println(stack.pop());

System.out.println(stack.isEmpty());

System.out.println(stack.peek());

}

}

二、采用链表实现栈

/**

* 链表实现栈

*

* @param

*/

class Mystack2 {

//定义链表

class Node {

private T t;

private Node next;

}

private Node head;

//构造函数初始化头指针

Mystack2() {

head = null;

}

//入栈

public void push(T t) {

if (t == null) {

throw new NullPointerException("参数不能为空");

}

if (head == null) {

head = new Node();

head.t = t;

head.next = null;

} else {

Node temp = head;

head = new Node();

head.t = t;

head.next = temp;

}

}

//出栈

public T potlcvvJp() {

T t = head.t;

head = head.next;

return t;

}

//栈顶元素

public T peek() {

T t = head.t;

return t;

}

//栈空

public boolean isEmpty() {

if (head == null)

return true;

else

return false;

}

}

public class LinkStack {

public static void main(String[] args) {

Mystack2 stack = new Mystack2();

System.out.println(stack.isEmpty());

stack.push("Java");

stack.push("is");

stack.push("beautiful");

System.out.println(stack.peek());

System.out.println(stack.peek());

System.out.println(stack.pop());

System.out.println(stack.pop());

System.out.println(stack.isEmpty());

System.out.println(stack.pop());

System.out.println(stack.isEmpty());

}

}

三、采用LinkedList实现栈

push-----addFirst()

pop-------removeFirst()

peek-----getFirst()

isEmpty-isEmpty()

import java.util.LinkedList;

/**

* LinkedList实现栈

*

* @param

*/

class ListStack {

private LinkedList ll = new LinkedList<>();

//入栈

public void push(T t) {

ll.addFirst(t);

}

//出栈

public T pop() {

return ll.removeFirst();

}

//栈顶元素

public T peek() {

T t = null;

//直接取元素会报异常，需要先判断是否为空

if (!ll.isEmpty())

t = ll.getFirst();

return t;

}

//栈空

public boolean isEmpty() {

return ll.isEmpty();

}

}

public class LinkedListStack {

public static void main(String[] args) {

ListStack stack = new ListStack();

System.out.println(stack.isEmpty());

System.out.println(stack.peek());

stack.push("java");

stack.push("is");

stack.push("beautiful");

System.out.println(stack.peek());

System.out.println(stack.pop());

System.out.println(stack.isEmpty());

System.out.println(stack.peek());

}

}

接着分享java使用两种方式实现简单栈

两种栈的不同点

基于数组实现的栈需要指定初始容量，栈的大小是有限的（可以利用动态扩容改变其大小），基于链表实现的栈则是没有大小限制的。

基于数组实现栈

数组实现栈的主要方法就是标识栈顶在数组中的位置，初始化时可以将栈顶指向为-1的虚拟位置，元素入栈则栈顶元素加1，出栈则栈顶元素减一，栈的元素容量为栈顶指针当前位置加1，且不能超过底层数组的最大容量。

/**

* 以数组为底层实现栈

* @param

*/

public class MyStackOfArray {

private Object[] data;//底层数组

private int maxSize = 0;//栈存储的最大元素个数

private int top = -1;//初始时栈顶指针指向-1

//默认初始化容量为10的栈

public MyStackOfArray(){

this(10);

}

//初始化指定大小的栈

public MyStackOfArray(int initialSize){

if(initialSize >= 0){

this.maxSize = initialSize;

data = new Object[initialSize];

top = -1;

}else{

throw new RuntimeException("初始化容量不能小于0" + initialSize);

}

}

//入栈，栈顶指针先加一再填入数据

public boolean push(T element){

if(top == maxSize - 1){

throw new RuntimeException("当前栈已满，无法继续添加元素");

}else{

data[++top] = element;

return true;

}

}

//查看栈顶元素

public T peek(){

if(top == -1)

throw new RuntimeException("栈已空");

return (T) data[top];

}

//出栈，先弹出元素再将栈顶指针减一

public T pop(){

if(top == -1)

throw new RuntimeException("栈已空");

return (T) data[top--];

}

//判断当前栈是否为空，只需判断栈顶指针是否等于-1即可

public boolean isEmpty(){

return top == -1;

}

public int search(T element){

int i = top;

while (top != -1){

if(peek() != element)

top--;

else

break;

}

int result = top + 1;

top = i;

return top;

}

public static void main(String[] args) {

MyStackOfArray myStackOfArray = new MyStackOfArray<>(10);

for(int i = 0; i < 10; i++){

myStackOfArray.push(i);

}

System.out.println("测试是否执行");

for(int i = 0; i < 10; i++){

System.out.println(myStackOfArray.pop());

}

}

}

基于链表实现栈

基于链表实现栈只要注意控制栈顶指针的指向即可。

/**

* 链表方式实现栈

* @param

*/

public class MyStack {

/**

* 内部节点类

* @param

*/

private class Node{

E e;

Node next;

public Node(){}

public Node(E e, Node next){

this.e = e;

this.next = next;

}

}

private Node top;//栈顶指针

private int size;//栈容量

public MyStack(){

top = null;

}

//入栈，将新节点的next指针指向当前top指针，随后将top指针指向新节点

public boolean push(E e){

top = new Node(e, top);

size++;

return true;

}

//判断栈是否为空

public boolean isEmpty(){

return size == 0;

}

//返回栈顶节点

public Node peek(){

if(isEmpty())

throw new RuntimeException("栈为空");

return top;

}

//出栈，先利用临时节点保存要弹出的节点值，再将top指针指向它的下一个节点，并将弹出的节点的next指针赋空即可

public Node pop(){

if(isEmpty())

throw new RuntimeException("栈为空");

Node value = top;

top = top.next;

value.next = null;

size--;

return value;

}

//返回当前栈的大小

public int length(){

return size;

}

public static void main(String[] args) {

MyStack myStack = new MyStack<>();

for(int i = 0; i < 10; i++){

myStack.push(i);

}

for(int i = 0; i < 10; i++){

System.out.println(myStack.pop().e);

}

}

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。