【数据结构】栈的实现---数组方式及链表方式

栈：

  一种先进后出的数据结构

基本操作：

• 入栈：将元素压入栈底
• 出栈：弹出栈顶元素
• 判满：栈是否为满，满则不能再加入元素
• 判空：栈是否为空，空则不能再弹出元素

实现：（数组实现）

public class ArrayStack {
	int top = -1;   //标记栈顶位置
	int ArrayStack[];
	
	ArrayStack()
	{
		this.ArrayStack = new int[10];    //默认栈空间为10
	}
	ArrayStack(int n)
	{
		this.ArrayStack = new int[n];     
	}
	//入栈
	boolean push(int a)
	{
		//自动扩容，并将旧的栈复制到新栈
		if(this.top == this.ArrayStack.length-1)    //判断是否栈满
		{
			int newArrayStack[] = new int[this.ArrayStack.length*2];
			for(int i=0;i<=top;i++)
				newArrayStack[i] = this.ArrayStack[i];
			this.ArrayStack = newArrayStack;
		}
		top++;  
		ArrayStack[this.top] = a;   //将元素存入栈顶
		return true;
	}
	//出栈
	int pop()
	{
		if(this.top == -1) return -1;     //判断是否栈空
		else return this.ArrayStack[this.top--];
	}
	//判空
	boolean isFull()
	{
		if(this.top == this.ArrayStack.length-1)return true;
		else return false;
	}
	//判满
	boolean isEmpty()
	{
		if(this.top == -1) return true;
		else return false;
	}

}

链表实现：（链表不会栈满）

import java.util.Scanner;

class Node{                      //Node作为栈的属性
	public int data;
	public Node next = null;
	
	Node(int data)
	{
		this.data = data;
		this.next = null;	
	}
}

public class ListStack 
{
	private Node top;
	
	ListStack()
	{
		this.top = null;	
	}
	//入栈
	public boolean push(int num)
	{
		Node p = new Node(num);
		p.next = this.top;       
		this.top = p;
		return true;
		
	}
	//出栈
	public int pop()
	{
		if(this.top==null)return -1;
		int num = this.top.data;
		this.top = this.top.next;   //取完元素后头指针后移
		return num;
	}
	//判空
	boolean isEmpty()
	{
		return this.top == null;
	}
	//判满
	public boolean isFull()
	{
		return true;
	}
	
}

测试：

public class app {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		//ArrayStack s = new ArrayStack(10);
		ListStack s = new ListStack();
		s.push(10);
		s.push(50);
		s.push(20);
		while(!s.isEmpty())
		{
			System.out.print(s.pop()+" ");
		}	
	}

}