栈是一种特殊的线性表，其插入（也称为入栈或压栈）和删除（也称出栈或弹栈）操作都在表的同一端进行。这一端称为栈顶，另一端称为栈底。简言之就是先进后出的数据结构，就因为栈具有这个特征，栈在程序设计中的运用很多，例如递归调用就是压栈和出栈的过程。下面分别以java使用数组和链表描述栈结构。
1、栈的常用操作：
压栈：将一个元素从栈顶压入栈。
出栈：将一个元素从栈顶移除。
返回栈顶元素。
返回栈的大小。
打印栈内容。
复制栈内容。
2、数组描述
数组描述将栈底放在数组头，使用一个指针表示栈顶元素的位置，在插入时当数组长度不足时，将数组长度增加两倍。下面是java代码：
package Structure; public class ArrayStack { private Object [] stack;//存储栈的数组 private int top;//栈顶指针 //无参构造函数，构造空栈 public ArrayStack(){ stack=new Object[4]; top=0; } //复制构造函数 public ArrayStack(ArrayStack s){ if(s==null){ stack=new Object[4]; top=0; }else{ int size=s.size(); stack=new Object[size+1]; for(int i=1;i<=size;i++){ stack[size-i]=s.pop(); } top=size; } } //栈大小 public int size(){ return top; } //私有增加数组大小函数 private void addSize(){ Object [] temp =new Object[top*2]; for(int i=0;i<top;i++) temp[i]=stack[i]; stack=temp; } //插入函数 public void insert(Object theElement){ if(top==stack.length) addSize(); stack[top]=theElement; top++; } //删除函数 public Object pop(){ if(top==0) return null; top--; return stack[top]; } //返回栈顶元素 public Object getTop(){ return stack[top-1]; } //打印栈内容 public String toString(){ String str=""; for (int i=0;i<top;i++) str+=stack[i]+" "; return str; } } 测试代码：
package Test; import Structure.ArrayStack; public class ArrayStackTest { public static void main(String[] args) { //实例化 ArrayStack stack=new ArrayStack(); System.out.println("栈顶在右边"); //插入和删除操作 stack.insert(1); stack.insert(2); stack.insert(3); stack.insert(4); stack.insert(5); System.out.println("插入5个元素后栈内容："+stack); stack.pop(); stack.pop(); System.out.println("删除2个元素后栈内容："+stack); stack.insert(6); stack.insert(7); stack.insert(8); System.out.println("再插入三个元素后栈内容："+stack); //栈大小 System.out.println("当前栈大小为："+stack.size()); //当前栈顶元素 System.out.println("当前栈顶元素："+stack.getTop()); //使用复制构造函数 ArrayStack stack1=new ArrayStack(stack); System.out.println("新栈内容为：："+stack1); } }
输出：
栈顶在右边 插入5个元素后栈内容：1 2 3 4 5 删除2个元素后栈内容：1 2 3 再插入三个元素后栈内容：1 2 3 6 7 8 当前栈大小为：6 当前栈顶元素：8 新栈内容为：：1 2 3 6 7 8
3、链表描述
使用链表描述栈时将栈顶放在根节点，其插入和删除在根节点进行。下面是java代码：
首先定义节点：
package Structure; public class Node { //定义节点 Object element; //节点元素 Node next; //节点指针 //无参构造函数 public Node(){ element=null; next=null; } //单值构造函数,用于末尾插入 public Node(Object theElement){ element=theElement; next=null; } //双值构造函数，用于中间插入。 public Node(Object theElement,Node node){ element=theElement; next=node; } } 栈类
package Structure; public class LinkStack { private Node root;//根节点 //无参构造函数，构建空栈 public LinkStack(){ root=null; } //复制构造函数 public LinkStack(LinkStack list){ Node node =list.getRoot(); if(node==null) root=null; else{ root = new Node(node.element); Node p=root; while(node.next!=null){ node=node.next; p.next=new Node(node.element); p=p.next; } } } //私有返回根节点指针 private Node getRoot() { return root; } //栈大小 public int size(){ if(root==null) return 0; else{ Node node=root; int size=1; while(node.next!=null){ node=node.next; size++; } return size; } } //插入函数 public void insert(Object theElement){ Node node =new Node(theElement,root); root =node; } //删除函数 public Object pop(){ if(root==null) return null; else{ Object temp=root.element; root=root.next; return temp; } } //返回栈顶元素 public Object getTop(){ return root.element; } //打印链表内容 public String toString(){ String str=""; if (root==null) ; else{ str+=root.element+" "; Node node=root; while(node.next!=null){ node=node.next; str+=node.element+" "; } } return str; } }
测试代码：
package Test; import Structure.ArrayStack; import Structure.LinkStack; public class LinkStackTest { public static void main(String[] args) { //实例化 LinkStack stack=new LinkStack(); System.out.println("栈顶在左边"); //插入和删除操作 stack.insert(1); stack.insert(2); stack.insert(3); stack.insert(4); stack.insert(5); System.out.println("插入5个元素后栈内容："+stack); stack.pop(); stack.pop(); System.out.println("删除2个元素后栈内容："+stack); stack.insert(6); stack.insert(7); stack.insert(8); System.out.println("再插入三个元素后栈内容："+stack); //栈大小 System.out.println("当前栈大小为："+stack.size()); //当前栈顶元素 System.out.println("当前栈顶元素："+stack.getTop()); //使用复制构造函数 LinkStack stack1=new LinkStack(stack); System.out.println("新栈内容为：："+stack1); } } 输出：
栈顶在左边 插入5个元素后栈内容：5 4 3 2 1 删除2个元素后栈内容：3 2 1 再插入三个元素后栈内容：8 7 6 3 2 1 当前栈大小为：6 当前栈顶元素：8 新栈内容为：：8 7 6 3 2 1
