数据结构 栈

    xiaoxiao2021-03-25  144

    栈是一种特殊的线性表,其插入(也称为入栈或压栈)和删除(也称出栈或弹栈)操作都在表的同一端进行。这一端称为栈顶,另一端称为栈底。简言之就是先进后出的数据结构,就因为栈具有这个特征,栈在程序设计中的运用很多,例如递归调用就是压栈和出栈的过程。下面分别以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 

    转载请注明原文地址: https://ju.6miu.com/read-1463.html

    最新回复(0)