【数据结构三】---栈

在学习的过程中有时会遇到一种数据结构也就是栈，这里对栈做个详细的了解。在完善这篇博客的过程中主要参考了这两篇博文：http://www.cnblogs.com/QG-whz/p/5170418.html#_label1_1和http://blog.csdn.net/javazejian/article/details/53362993在这里注明出处，所涉及到的代码皆由我用java实现。第一次修改日期是2017.8.02下午

栈简介

栈的特点

栈(Stack)是一种线性存储结构，也可以称做一种操作受限的特殊的线性表，其插入和删除操作只允许在线性表的一端进行，一般而言，把允许操作的一端称为栈顶(Top)，不可操作的一端称为栈底(Bottom)，栈顶也就是线性序列的末端。

总结有如下两个特点：
1，栈中的数据元素遵守”后进先出”( Last In Out First)的原则，简称LIFO结构。
2，限定只能在栈顶进行插入和删除操作。

栈的相关概念

1，栈顶与栈底：允许元素插入与删除的一端称为栈顶（TOP），另一端称为栈底（BOTTOM）。
2，压栈：栈的插入操作，叫做进栈，也称压栈、入栈(PUSH)。
3，弹栈：栈的删除操作，也叫做出栈（POP）。

栈的基本运算

1，入栈（push）

在压栈的过程中，栈顶的位置一直在”向上“移动，而栈底是固定不变的。

2，出栈(pop)

出栈的顺序为3、2、1 ，顺序与入栈时相反，这就是所谓的”后入先出“。
在弹栈的过程中，栈顶位置一直在”向下“移动，而栈底一直保持不变。

3，求栈的大小(size)
4，判断栈是否为空（isEmpty）
5，获取栈顶元素的值（top）

栈的实现方式

java中Stack类的使用

    /** * Stack类 * 栈：桶型或箱型数据类型，后进先出，相对堆Heap为二叉树类型，可以快速定位并操作 * Stack<E>，支持泛型 * public class Stack<E> extends Vector<E> * Stack的方法调用的Vector的方法，被synchronized修饰，为线程安全(Vector也是) * Stack methods： * push : 把项压入堆栈顶部 ，并作为此函数的值返回该对象 * pop : 移除堆栈顶部的对象，并作为此函数的值返回该对象 * peek : 查看堆栈顶部的对象，，并作为此函数的值返回该对象，但不从堆栈中移除它 * empty : 测试堆栈是否为空 * search : 返回对象在堆栈中的位置，以 1 为基数 * size:返回栈的大小 * */

    package ca.map;  

    import java.util.Stack;  

    public class StackX {  
        public static void main(String[] args) {  
            stackMethod();  
        }  
        //stack operate 
        public static void stackMethod(){  
            //定义一个Integer泛型的Stack 
            Stack<Integer> stack = new Stack<Integer>();  
            System.out.println("新建栈stack是否为空 : "+(stack.empty() ? "空" : stack.size()));  
            //push : 把项压入堆栈顶部，返回值泛型指定的类型 
            //此处将1到5压入栈中 
            stack.push(1);  
            stack.push(2);  
            stack.push(3);  
            stack.push(4);  
            stack.push(5);  
            System.out.println("将1到5按顺序压入栈中后为："+stack);  
            //empty : 测试堆栈是否为空，size() == 0，返回值boolean 
            System.out.println("值为1~5的栈中stack是否为空 : "+(stack.empty() ? "空" : stack.size()));  
            //search : 返回对象在堆栈中的位置，以 1 为基数，参数：search(Object o) ，返回值int 
            int oStack = stack.search(3);  
            System.out.println("查找栈stack中对象3的位置elementId为 : "+oStack);  
            //peek : 查看堆栈顶部的对象，但不从堆栈中移除它，返回值泛型指定的类型 
            int topElement =stack.peek();  
            System.out.println("查看stack的栈顶元素为 : "+topElement);  
            System.out.println("peek操作stack后为 : "+stack);  
            //pop : 移除堆栈顶部的对象，并作为此函数的值返回该对象，返回值泛型指定的类型 
            int oRemove = stack.pop();  
            System.out.println("移除stack栈顶的元素为 : "+oRemove);  
            System.out.println("pop操作移除stack栈顶元素后为 : "+stack);  
        }  
    }

测试结果

新建栈stack是否为空 : 空
将1到5按顺序压入栈中后为：[1, 2, 3, 4, 5]
值为1~5的栈中stack是否为空 : 5
查找栈stack中对象3的位置elementId为 : 3
查看stack的栈顶元素为 : 5
peek操作stack后为 : [1, 2, 3, 4, 5]
移除stack栈顶的元素为 : 5
pop操作移除stack栈顶元素后为 : [1, 2, 3, 4]

若集合为空，返回 []
若集合不为空则 [ 加上迭代元素加上 , 最后集合无元素加上 ] eg：[1, 2, 3, 4]
栈按照存储结构有两种实现方式。

数组实现

栈的创建和常用方法代码：

package stack;

import java.util.EmptyStackException;

public class MyStackArray<T> {
    public T[] array = null; // 存放元素的数组
    public  int initalSize = 5; // 栈的容量大小，默认为10
    public int top = -1; // 栈顶指针 ，-1表示空栈，因为数组下标从0开始。
    public int curSize;  //表示栈的当前实际容量是多大

    public MyStackArray() {
        this(5);
    }

    @SuppressWarnings("unchecked")
    public MyStackArray(int Size) { // 构造函数，用于初始化栈大小
        if (Size >= 0) {
            this.initalSize= Size; // 栈的容量为该值
            array = (T[]) new Object[Size]; // 存放栈元素数组大小的值也为该值
            top = -1; // 如果栈顶指针指向-1，表示空栈，
            curSize = 0;
        } else {
            throw new RuntimeException("初始化大小不能小于0：" + Size);
        }
    }

    // 判断该栈是否为空
    public boolean isEmpty() {
        return top == -1 ? true : false; // 如果栈顶指针指向-1，表示空栈
    }

    // 扩充栈的的容量
    @SuppressWarnings("unchecked")
    public void expandCapacity() {
        // 如果需要拓展的容量比现在数组的容量还小,则无需扩容
        T[] old = array;
        array = (T[]) new Object[curSize * 2 + 1];
        initalSize = curSize * 2 + 1;
        // 复制元素
        for (int i = 0; i < top; i++)
            array[i] = old[i];

    }

    // 进栈,先判断栈是否已经满了
    public void push(T data) {
        if (top == initalSize-1) {
            expandCapacity(); // 如果栈已经满了，则扩充容量
        }
        // 从栈顶添加元素
        array[++top] = data; // 没满的话top指向的下一个元素为该元素，数组扩充

        curSize++;

    }

    // 出栈,首先判断是否为空栈，为空则报异常
    public T pop() {
        if (isEmpty())
            new EmptyStackException();
        curSize--;
        return array[top--]; // 返回要删除的元素
    }

    // 查看栈顶元素但不移除
    public T peek() {
        if (isEmpty())
            new EmptyStackException();
        return array[top];
    }
      //返回对象在堆栈中的位置，以 1 为基数
    public int search(T data){
        int i = top;
        while(top != -1){
            if(peek() != data){
                top--;
            }else{
                break;
            }
        }
        int result = top+1;
        top = i; //top返回栈顶位置
        return result;      
    }

}

测试代码：

package stack;

public class Stack {

    public static void main(String[] args) {
        MyStackArray<Integer> s = new MyStackArray<Integer>();
        s.push(1);
        s.push(5);
        s.push(3);
        s.push(4);
        System.out.println("栈的容量"+ s.initalSize);
        System.out.println("栈顶元素"+s.peek());
        System.out.println("搜索元素的位置" +s.search(5));
        System.out.println("出栈元素是"+s.pop());
        System.out.println("出栈一次后栈顶" +s.peek());
        s.push(8);
        s.push(9);
        System.out.println("栈顶元素"+s.peek());
        System.out.println("栈的容量"+ s.initalSize);
        s.push(10);
        System.out.println("栈顶元素"+s.peek());
        System.out.println("栈的容量"+ s.initalSize);


    }

}

测试结果

栈的容量5
栈顶元素4
搜索元素的位置2
出栈元素是4
出栈一次后栈顶3
栈顶元素9
栈的容量5     //注意，在这个地方由于增加元素超过总容量，所以自动扩容
栈顶元素10
栈的容量11

单链表实现

链表类代码

package stack;

public class Node<T> {
    public T val;
    public Node<T> next = null;

    public Node(T val, Node<T> next) {   //构造方法，创建一个新节点
        this.val = val;
        this.next = next;
    }

}

单链表组成的栈代码

package stack;

public class MyStackList<T> {
    public Node<T> top; // 栈顶元素
    public int curSize;

    // 判断该栈是否为空
    public boolean isEmpty() {
        return curSize == 0 ? true : false;
    }

    // 进栈,先判断栈是否已经满了
    public void push(T val) {
        if (val == null) {
            System.out.println("新加节点的数据不能为null");
        }
        if (top == null) {
            top = new Node<T>(val, null); // 如果当前为空栈，无节点，则进来的节点为第一个节点
        } else if (top.val == null) {
            top.val = val; // 如果当前top不为null，但是其中的数据为null，则只需把当前的数据赋给栈顶就好
        } else {
            Node<T> newNode = new Node<T>(val, top);
            top = newNode; // 更新栈顶
        }
        curSize++;

    }

    // 出栈,首先判断是否为空栈，为空则报异常
    public T pop() {
        if (isEmpty()) {
            System.out.println("栈为空");
        }
        T oldData = top.val;
        top = top.next;
        curSize--;
        return oldData;

    }

    // 查看栈顶元素但不移除
    public T peek() {
        if (isEmpty()) {
            System.out.println("栈为空");
        }
        return top.val;

    }

    // 返回对象在堆栈中的位置，以 1 为基数
    public int search(T data) {
        int count = curSize;

        Node<T> temp = top;
        while (temp != null) {
            if (temp.val == data)
                return count;
            count--;
            temp = temp.next;
        }

        return -100000;

    }

}

测试代码

package stack;

public class ListStack {

    public static void main(String[] args) {
        MyStackList<Integer> s = new MyStackList<Integer>();
        s.push(1);
        s.push(5);
        s.push(3); 
        s.push(3); 
        System.out.println("栈的容量"+ s.curSize);
        s.pop(); 
        System.out.println("栈的容量"+ s.curSize);
        System.out.println("栈顶元素"+s.peek());
        System.out.println("搜索元素的位置" +s.search(1));
        System.out.println("出栈元素是"+s.pop());
        System.out.println("出栈两次后栈顶" +s.peek());
        s.push(8);
        s.push(9);
        System.out.println("栈顶元素"+s.peek());
        System.out.println("栈的容量"+ s.curSize);
        s.push(10);
        System.out.println("栈顶元素"+s.peek());
        System.out.println("栈的容量"+ s.curSize);
    }

}

测试结果

栈的容量4
栈的容量3
栈顶元素3
搜索元素的位置1
出栈元素是3
出栈两次后栈顶5
栈顶元素9
栈的容量4
栈顶元素10
栈的容量5

两种实现的时间复杂度比较

顺序栈复杂度如下：

链式栈复杂度如下：

由此可知栈的主要操作都可以在常数时间内完成，这主要是因为栈只对一端进行操作，而且操作的只是栈顶元素。

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();
    }
}

【数据结构 三】---栈

栈简介

栈的特点

栈的相关概念

栈的基本运算

栈的实现方式

java中Stack类的使用

数组实现

单链表实现

两种实现的时间复杂度比较

LinkedList实现栈

【数据结构三】---栈