文档章节

实现一个栈

一贱书生
 一贱书生
发布于 2016/11/17 09:57
字数 2218
阅读 1
收藏 0
  1. public interface MyStack<T> {  
  2.     /** 
  3.      * 判断栈是否为空 
  4.      */  
  5.     boolean isEmpty();  
  6.     /** 
  7.      * 清空栈 
  8.      */  
  9.     void clear();  
  10.     /** 
  11.      * 栈的长度 
  12.      */  
  13.     int length();  
  14.     /** 
  15.      * 数据入栈 
  16.      */  
  17.     boolean push(T data);  
  18.     /** 
  19.      * 数据出栈 
  20.      */  
  21.     T pop();  
  22. }  

栈的数组实现, 底层使用数组:

Java代码

 收藏代码

  1. public class MyArrayStack<T> implements MyStack<T> {  
  2.     private Object[] objs = new Object[16];  
  3.     private int size = 0;  
  4.   
  5.     @Override  
  6.     public boolean isEmpty() {  
  7.         return size == 0;  
  8.     }  
  9.   
  10.     @Override  
  11.     public void clear() {  
  12.         // 将数组中的数据置为null, 方便GC进行回收  
  13.         for (int i = 0; i < size; i++) {  
  14.             objs[size] = null;  
  15.         }  
  16.         size = 0;  
  17.     }  
  18.   
  19.     @Override  
  20.     public int length() {  
  21.         return size;  
  22.     }  
  23.   
  24.     @Override  
  25.     public boolean push(T data) {  
  26.         // 判断是否需要进行数组扩容  
  27.         if (size >= objs.length) {  
  28.             resize();  
  29.         }  
  30.         objs[size++] = data;  
  31.         return true;  
  32.     }  
  33.   
  34.     /** 
  35.      * 数组扩容 
  36.      */  
  37.     private void resize() {  
  38.         Object[] temp = new Object[objs.length * 3 / 2 + 1];  
  39.         for (int i = 0; i < size; i++) {  
  40.             temp[i] = objs[i];  
  41.             objs[i] = null;  
  42.         }  
  43.         objs = temp;  
  44.     }  
  45.   
  46.     @SuppressWarnings("unchecked")  
  47.     @Override  
  48.     public T pop() {  
  49.         if (size == 0) {  
  50.             return null;  
  51.         }  
  52.         return (T) objs[--size];  
  53.     }  
  54.   
  55.     @Override  
  56.     public String toString() {  
  57.         StringBuilder sb = new StringBuilder();  
  58.         sb.append("MyArrayStack: [");  
  59.         for (int i = 0; i < size; i++) {  
  60.             sb.append(objs[i].toString());  
  61.             if (i != size - 1) {  
  62.                 sb.append(", ");  
  63.             }  
  64.         }  
  65.         sb.append("]");  
  66.         return sb.toString();  
  67.     }  
  68. }    

栈的链表实现, 底层使用链表:

Java代码

 收藏代码

  1. public class MyLinkedStack<T> implements MyStack<T> {  
  2.     /** 
  3.      * 栈顶指针 
  4.      */  
  5.     private Node top;  
  6.     /** 
  7.      * 栈的长度 
  8.      */  
  9.     private int size;  
  10.       
  11.     public MyLinkedStack() {  
  12.         top = null;  
  13.         size = 0;  
  14.     }  
  15.       
  16.     @Override  
  17.     public boolean isEmpty() {  
  18.         return size == 0;  
  19.     }  
  20.       
  21.     @Override  
  22.     public void clear() {  
  23.         top = null;  
  24.         size = 0;  
  25.     }  
  26.       
  27.     @Override  
  28.     public int length() {  
  29.         return size;  
  30.     }  
  31.       
  32.     @Override  
  33.     public boolean push(T data) {  
  34.         Node node = new Node();  
  35.         node.data = data;  
  36.         node.pre = top;  
  37.         // 改变栈顶指针  
  38.         top = node;  
  39.         size++;  
  40.         return true;  
  41.     }  
  42.       
  43.     @Override  
  44.     public T pop() {  
  45.         if (top != null) {  
  46.             Node node = top;  
  47.             // 改变栈顶指针  
  48.             top = top.pre;  
  49.             size--;  
  50.             return node.data;  
  51.         }  
  52.         return null;  
  53.     }  
  54.       
  55.     /** 
  56.      * 将数据封装成结点 
  57.      */  
  58.     private final class Node {  
  59.         private Node pre;  
  60.         private T data;  
  61.     }  
  62. }  

两种实现的比较, 主要比较数据入栈和出栈的速度:

Java代码

 收藏代码

  1. @Test  
  2. public void testSpeed() {  
  3.     MyStack<Person> stack = new MyArrayStack<Person>();  
  4.     int num = 10000000;  
  5.     long start = System.currentTimeMillis();  
  6.     for (int i = 0; i < num; i++) {  
  7.         stack.push(new Person("xing", 25));  
  8.     }  
  9.     long temp = System.currentTimeMillis();  
  10.     System.out.println("push time: " + (temp - start));  
  11.     while (stack.pop() != null)  
  12.         ;  
  13.     System.out.println("pop time: " + (System.currentTimeMillis() - temp));  
  14. }  

MyArrayStack中入栈和出栈10,000,000条数据的时间:

push time: 936

pop time: 47

将MyArrayStack改为MyLinkedStack后入栈和出栈的时间:

push time: 936

pop time: 126

可见两者的入栈速度差不多, 出栈速度MyArrayStack则有明显的优势.

为什么测试结果是这样的? 可能有些朋友的想法是数组实现的栈应该具有更快的遍历速度, 但增删速度应该比不上链表实现的栈才对. 但是栈中数据的增删具有特殊性: 只在栈顶入栈和出栈. 也就是说数组实现的栈在增加和删除元素时并不需要移动大量的元素, 只是在数组扩容时需要进行复制. 而链表实现的栈入栈和出栈时都需要将数据包装成Node或者从Node中取出数据, 还需要维护栈顶指针和前驱指针. 

 

栈的应用举例

1. 将10进制正整数num转换为n进制

Java代码

 收藏代码

  1. private String conversion(int num, int n) {  
  2.     MyStack<Integer> myStack = new MyArrayStack<Integer>();  
  3.     Integer result = num;  
  4.     while (true) {  
  5.         // 将余数入栈  
  6.         myStack.push(result % n);  
  7.         result = result / n;  
  8.         if (result == 0) {  
  9.             break;  
  10.         }  
  11.     }  
  12.     StringBuilder sb = new StringBuilder();  
  13.     // 按出栈的顺序倒序排列即可  
  14.     while ((result = myStack.pop()) != null) {  
  15.         sb.append(result);  
  16.     }  
  17.     return sb.toString();  
  18. }  

2. 检验符号是否匹配. '['和']', '('和')'成对出现时字符串合法. 例如"[][]()", "[[([]([])()[])]]"是合法的; "([(])", "[())"是不合法的.

遍历字符串的每一个char, 将char与栈顶元素比较. 如果char和栈顶元素配对, 则char不入栈, 否则将char入栈. 当遍历完成时栈为空说明字符串是合法的.

Java代码

 收藏代码

  1. public boolean isMatch(String str) {  
  2.     MyStack<Character> myStack = new MyArrayStack<Character>();  
  3.     char[] arr = str.toCharArray();  
  4.     for (char c : arr) {  
  5.         Character temp = myStack.pop();  
  6.         // 栈为空时只将c入栈  
  7.         if (temp == null) {  
  8.             myStack.push(c);  
  9.         }  
  10.         // 配对时c不入栈  
  11.         else if (temp == '[' && c == ']') {  
  12.         }   
  13.         // 配对时c不入栈  
  14.         else if (temp == '(' && c == ')') {  
  15.         }   
  16.         // 不配对时c入栈  
  17.         else {  
  18.             myStack.push(temp);  
  19.             myStack.push(c);  
  20.         }  
  21.     }  
  22.     return myStack.isEmpty();  
  23. }  

3. 行编辑: 输入行中字符'#'表示退格, '@'表示之前的输入全都无效.

使用栈保存输入的字符, 如果遇到'#'就将栈顶出栈, 如果遇到@就清空栈. 输入完成时将栈中所有字符出栈后反转就是输入的结果:

Java代码

 收藏代码

  1. private String lineEdit(String input) {  
  2.     MyStack<Character> myStack = new MyArrayStack<Character>();  
  3.     char[] arr = input.toCharArray();  
  4.     for (char c : arr) {  
  5.         if (c == '#') {  
  6.             myStack.pop();  
  7.         } else if (c == '@') {  
  8.             myStack.clear();  
  9.         } else {  
  10.             myStack.push(c);  
  11.         }  
  12.     }  
  13.       
  14.     StringBuilder sb = new StringBuilder();  
  15.     Character temp = null;  
  16.     while ((temp = myStack.pop()) != null) {  
  17.         sb.append(temp);  
  18.     }  
  19.     // 反转字符串  
  20.     sb.reverse();  
  21.     return sb.toString();  

 

或者

栈数组实现一:优点:入栈和出栈速度快,缺点:长度有限(有时候这也不能算是个缺点)

[java] view plain copy

 

  1. public class Stack {  
  2.     private int top = -1;  
  3.     private Object[] objs;  
  4.       
  5.     public Stack(int capacity) throws Exception{  
  6.         if(capacity < 0)  
  7.             throw new Exception("Illegal capacity:"+capacity);  
  8.         objs = new Object[capacity];  
  9.     }  
  10.       
  11.     public void push(Object obj) throws Exception{  
  12.         if(top == objs.length - 1)  
  13.             throw new Exception("Stack is full!");  
  14.         objs[++top] = obj;  
  15.     }  
  16.       
  17.     public Object pop() throws Exception{  
  18.         if(top == -1)  
  19.             throw new Exception("Stack is empty!");  
  20.         return objs[top--];  
  21.     }  
  22.       
  23.     public void dispaly(){  
  24.         System.out.print("bottom -> top: | ");  
  25.         for(int i = 0 ; i <= top ; i++){  
  26.             System.out.print(objs[i]+" | ");  
  27.         }  
  28.         System.out.print("\n");  
  29.     }  
  30.       
  31.     public static void main(String[] args) throws Exception{  
  32.         Stack s = new Stack(2);  
  33.         s.push(1);  
  34.         s.push(2);  
  35.         s.dispaly();  
  36.         System.out.println(s.pop());  
  37.         s.dispaly();  
  38.         s.push(99);  
  39.         s.dispaly();  
  40.         s.push(99);  
  41.     }  
  42. }  

[plain] view plain copy

 

  1. bottom -> top: | 1 | 2 |   
  2. 2  
  3. bottom -> top: | 1 |   
  4. bottom -> top: | 1 | 99 |   
  5. Exception in thread "main" java.lang.Exception: Stack is full!  
  6.     at Stack.push(Stack.java:17)  
  7.     at Stack.main(Stack.java:44)  

数据项入栈和出栈的时间复杂度都为常数O(1)

 

栈数组实现二:优点:无长度限制,缺点:入栈慢

[java] view plain copy

 

  1. import java.util.Arrays;  
  2.   
  3. public class UnboundedStack {  
  4.     private int top = -1;  
  5.     private Object[] objs;  
  6.       
  7.     public UnboundedStack() throws Exception{  
  8.         this(10);  
  9.     }  
  10.       
  11.     public UnboundedStack(int capacity) throws Exception{  
  12.         if(capacity < 0)  
  13.             throw new Exception("Illegal capacity:"+capacity);  
  14.         objs = new Object[capacity];  
  15.     }  
  16.       
  17.     public void push(Object obj){  
  18.         if(top == objs.length - 1){  
  19.             this.enlarge();  
  20.         }  
  21.         objs[++top] = obj;  
  22.     }  
  23.       
  24.     public Object pop() throws Exception{  
  25.         if(top == -1)  
  26.             throw new Exception("Stack is empty!");  
  27.         return objs[top--];  
  28.     }  
  29.       
  30.     private void enlarge(){  
  31.         int num = objs.length/3;  
  32.         if(num == 0)  
  33.             num = 1;  
  34.         objs = Arrays.copyOf(objs, objs.length + num);  
  35.     }  
  36.       
  37.     public void dispaly(){  
  38.         System.out.print("bottom -> top: | ");  
  39.         for(int i = 0 ; i <= top ; i++){  
  40.             System.out.print(objs[i]+" | ");  
  41.         }  
  42.         System.out.print("\n");  
  43.     }  
  44.       
  45.     public static void main(String[] args) throws Exception{  
  46.         UnboundedStack us = new UnboundedStack(2);  
  47.         us.push(1);  
  48.         us.push(2);  
  49.         us.dispaly();  
  50.         System.out.println(us.pop());  
  51.         us.dispaly();  
  52.         us.push(99);  
  53.         us.dispaly();  
  54.         us.push(99);  
  55.         us.dispaly();  
  56.     }  
  57. }  

[plain] view plain copy

 

  1. bottom -> top: | 1 | 2 |   
  2. 2  
  3. bottom -> top: | 1 |   
  4. bottom -> top: | 1 | 99 |   
  5. bottom -> top: | 1 | 99 | 99 |   

由于该栈是由数组实现的,数组的长度是固定的,当栈空间不足时,必须将原数组数据复制到一个更长的数组中,考虑到入栈时或许需要进行数组复制,平均需要复制N/2个数据项,故入栈的时间复杂度为O(N),出栈的时间复杂度依然为O(1)

 

栈单链表实现:没有长度限制,并且出栈和入栈速度都很快

[java] view plain copy

 

  1. public class LinkedList {  
  2.     private class Data{  
  3.         private Object obj;  
  4.         private Data next = null;  
  5.           
  6.         Data(Object obj){  
  7.             this.obj = obj;  
  8.         }  
  9.     }  
  10.       
  11.     private Data first = null;  
  12.       
  13.     public void insertFirst(Object obj){  
  14.         Data data = new Data(obj);  
  15.         data.next = first;  
  16.         first = data;  
  17.     }  
  18.       
  19.     public Object deleteFirst() throws Exception{  
  20.         if(first == null)  
  21.             throw new Exception("empty!");  
  22.         Data temp = first;  
  23.         first = first.next;  
  24.         return temp.obj;  
  25.     }  
  26.               
  27.     public void display(){  
  28.         if(first == null)  
  29.             System.out.println("empty");  
  30.         System.out.print("top -> bottom : | ");  
  31.         Data cur = first;  
  32.         while(cur != null){  
  33.             System.out.print(cur.obj.toString() + " | ");  
  34.             cur = cur.next;  
  35.         }  
  36.         System.out.print("\n");  
  37.     }  
  38. }  

[java] view plain copy

 

  1. public class LinkedListStack {  
  2.     private LinkedList ll = new LinkedList();  
  3.       
  4.     public void push(Object obj){  
  5.         ll.insertFirst(obj);  
  6.     }  
  7.       
  8.     public Object pop() throws Exception{  
  9.         return ll.deleteFirst();  
  10.     }  
  11.       
  12.     public void display(){  
  13.         ll.display();  
  14.     }  
  15.       
  16.     public static void main(String[] args) throws Exception{  
  17.         LinkedListStack lls = new LinkedListStack();  
  18.         lls.push(1);  
  19.         lls.push(2);  
  20.         lls.push(3);  
  21.         lls.display();  
  22.         System.out.println(lls.pop());  
  23.         lls.display();  
  24.     }  
  25. }  

[plain] view plain copy

 

  1. top -> bottom : | 3 | 2 | 1 |   
  2. 3  
  3. top -> bottom : | 2 | 1 |   

数据项入栈和出栈的时间复杂度都为常数O(1)

 

 

/**
 * 基于数组实现的顺序栈
 * @param <E>
 */
public class Stack<E> {
    private Object[] data = null;
    private int maxSize=0;   //栈容量
    private int top =-1;  //栈顶指针
    
    /**
     * 构造函数:根据给定的size初始化栈
     */
    Stack(){
        this(10);   //默认栈大小为10
    }
    
    Stack(int initialSize){
        if(initialSize >=0){
            this.maxSize = initialSize;
            data = new Object[initialSize];
            top = -1;
        }else{
            throw new RuntimeException("初始化大小不能小于0:" + initialSize);
        }
    }
    
    //判空
    public boolean empty(){
        return top==-1 ? true : false;
    }
    
    //进栈,第一个元素top=0;
    public boolean push(E e){
        if(top == maxSize -1){
            throw new RuntimeException("栈已满,无法将元素入栈!");
        }else{
            data[++top]=e;
            return true;
        }    
    }
    
    //查看栈顶元素但不移除
    public E peek(){
        if(top == -1){
            throw new RuntimeException("栈为空!");
        }else{
            return (E)data[top];
        }
    }
    
    //弹出栈顶元素
    public E pop(){
        if(top == -1){
            throw new RuntimeException("栈为空!");
        }else{
            return (E)data[top--];
        }
    }
    
    //返回对象在堆栈中的位置,以 1 为基数
    public int search(E e){
        int i=top;
        while(top != -1){
            if(peek() != e){
                top --;
            }else{
                break;
            }
        }
        int result = top+1;
        top = i;
        return result;      
    }
}

复制代码

链式存储结构实现:

复制代码

public class LinkStack<E> {
    //链栈的节点
    private class Node<E>{
        E e;
        Node<E> next;
        
        public Node(){}
        public Node(E e, Node next){
            this.e = e;
            this.next = next;
        }
    }
    
    private Node<E> top;   //栈顶元素
    private int size;  //当前栈大小
    
    public LinkStack(){
        top = null;
    }
    
    //当前栈大小
    public int length(){
        return size;
    }
    
    //判空
    public boolean empty(){
        return size==0;
    }
    
    //入栈:让top指向新创建的元素,新元素的next引用指向原来的栈顶元素
    public boolean push(E e){
        top = new Node(e,top);
        size ++;
        return true;
    }
    
    //查看栈顶元素但不删除
    public Node<E> peek(){
        if(empty()){
            throw new RuntimeException("空栈异常!");
        }else{
            return top;
        }
    }
    
    //出栈
    public Node<E> pop(){
        if(empty()){
            throw new RuntimeException("空栈异常!");
        }else{
            Node<E> value = top; //得到栈顶元素
            top = top.next; //让top引用指向原栈顶元素的下一个元素 
            value.next = null;  //释放原栈顶元素的next引用
            size --;
            return value;
        }
    }
}

复制代码

 

基于LinkedList实现的结构:

复制代码

import java.util.LinkedList;

/**
 * 基于LinkedList实现栈
 * 在LinkedList实力中只选择部分基于栈实现的接口
 */
public class StackList<E> {
    private LinkedList<E> ll = new LinkedList<E>();
    
    //入栈
    public void push(E e){
        ll.addFirst(e);
    }
    
    //查看栈顶元素但不移除
    public E peek(){
        return ll.getFirst();
    }
    
    //出栈
    public E pop(){
        return ll.removeFirst();
    }
    
    //判空
    public boolean empty(){
        return ll.isEmpty();
    }
    
    //打印栈元素
    public String toString(){
        return ll.toString();
    }
}

© 著作权归作者所有

一贱书生
粉丝 20
博文 724
码字总数 600123
作品 0
私信 提问
STL-关于栈和队列的面试题

题目分别为: 1.实现一个栈,要求实现Push(出栈)、Pop(入栈)、Min(返回最小值的操作)的时间复杂度为O(1)。 2.使用两个栈实现一个队列。 3.使用两个队列实现一个栈。 4.判断元素出栈、入...

han8040laixin
2017/12/13
0
0
数据结构-栈和队列面试题(上)

在数据结构的学习过程中,栈和队列的掌握是十分重要的。所以找了几个很热门的面试题试试手并小结一下。先回顾下栈和队列的特性:栈是后进先出,主要接口有PUSH,POP,TOP,而队列是先进先出,...

sssssuuuuu666
2017/12/05
0
0
前端也要懂的数据结构(1)--栈

图片来自网络 数据结构是开发人员的基础知识,前端开发人员也要对各种数据有了解。相信理解的越深入,越能发现他的强大。今天先和大家介绍一下最简单的数据结构栈。 1.栈的定义 栈是一种遵循...

魏永_Owen_Wei
2017/12/28
0
0
使用两个栈实现队列,使用两个队列实现栈。

我是一个栈,我的双胞胎弟弟叫队列。我的爸爸是数组,我的妈妈是链表。在上一篇文章中,向你们介绍了我的家族成员对于数据存储方面的能力和特性。还包括如何通过数组和链表来实现栈和队列。 ...

2018/03/25
0
0
自己动手实现java数据结构(三) 栈

1.栈的介绍   在许多算法设计中都需要一种"先进后出(First Input Last Output)"的数据结构,因而一种被称为"栈"的数据结构被抽象了出来。   栈的结构类似一个罐头:只有一个开口;先被放...

小熊餐馆
2018/12/06
0
0

没有更多内容

加载失败,请刷新页面

加载更多

偶遇 JDK 1.8 还未修复的 SecureRandom.getInstance("SHA1PRNG") 之 bug

楼主今天兴高采烈的在部署环境,下载 JDK,打包项目,上传至服务器。 配置 JDK ,打包上传项目楼主就不在这里重复了,读者自行解决哈! 1. 启动项目 java -jar xxxx.jar 令楼主没有想到的是:...

Ryan-瑞恩
13分钟前
3
0
【更新】Stimulsoft Reports v2019.3.1发布,新增对OData v4的支持功能

下载Stimulsoft Report.Ultimate v2019.3.1试用版 集所有报表解决方案于一体的综合性平台 Stimulsoft Reports.Ultimate是集所有报表解决方案于一体的综合性平台,拥有在JavaScript、ASP.NET...

xiaochuachua
13分钟前
0
0
JVM源码分析之javaagent原理完全解读

JVM源码分析之javaagent原理完全解读 概述 本文重点讲述javaagent的具体实现,因为它面向的是我们Java程序员,而且agent都是用Java编写的,不需要太多的C/C++编程基础,不过这篇文章里也会讲...

BryceLoski
19分钟前
0
0
git记住密码

git取消记住密码 git config --system --unset credential.helper git记住密码 git config --global credential.helper store...

大灰狼wow
20分钟前
1
0
java 面试知识点笔记(十四)异常体系

问:Error和Exception的区别? ps:Throwable上层是Object Error:程序无法处理的系统错误,编译器不做检查 Exception:程序可以处理的异常,捕获后可能恢复 RuntimeException:不可预知的,...

断风格男丶
23分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部