数据结构全解析之栈与队列的存储结构与实现

1 栈的多种存储结构以及实现

栈有两种实现方式一种是顺序存储结构、还有一种是链式存储结构。这两种存储结构对应两种存储的数据结构：数组和链表。数组和链表的相关内容可以参考本文其他章节的内容。

1.1 栈的顺序存储结构

前面我们说了栈是数据结构中线性表的特殊存在，所以栈的顺序存储方式也就是线性表的顺序存储的方式，也就是我们接下来要讲的顺序栈，因此顺序栈的实现形式也就是线性表顺序存储的实现形式-数组。因为栈底的变化最小，所以将数组下标为 0 的一端作为栈底，同时还要定义一个变量，用来表示栈顶元素在数组中的位置。

1.2 顺序栈的各类功能实现

/*
@author youDaily
*/
//属性定义和构造函数
public class SortStack {

    public Object[] data;   // 数组表示栈内元素
    public int maxSize;     // 栈空间大小
    public int top;         // 栈顶指针(指向栈顶元素)
    //初始化栈的长度
    public SortStack(int initialSize){
        if(initialSize>=0){
            this.data=new Object[initialSize];
            this.maxSize=initialSize;
            this.top=-1;
        }
        else{
            System.out.println("栈初始化失败!");
        }
    }
    //判断栈是否为空
    public boolean isEmpty(){
        return top == -1 ? true : false;
    }
    //判断是否栈满
    public boolean isFull(){
        return top == maxSize-1 ? true : false;
    }
    //入栈
    public void push(Object value){
        if(!isFull()){
            System.out.print(value+"入栈   ");
            data[++top]=value;
        }
        else{
            System.out.println("满栈，无法进行入栈操作!");
        }
    }

    /**
     * 
     * 先判断是否为空栈
     * @return
     */
    //元素出栈
    public Object pop(){
        Object num=null;
        if(!isEmpty()){
            num = data[top--];
            return num;
        }
        else{
            return "空栈，无法进行出栈操作!";
        }

    }
   // 获取栈顶元素
    public Object getPeek(){
        if(top>=0){
            return data[top];
        }
        else{
            return "栈顶指针为空，无栈顶元素!";
        }
    }
    //遍历栈内元素
    public void displayStack(){

        // 栈顶指针不为—1，栈内有元素，进行打印
        if(top>=0){
            for(int i=top;i>=0;i--){
                System.out.print(data[i] + " ");
            }
            System.out.println();
        }
        else{
            System.out.println("栈内元素为空！");
        }       
    }
    //获取栈顶指针为 n 的栈内元素
    public Object getPeekN(int n){
        if(n<top){
            return data[n];
        }
        else{
            return "error";
        }
    }
}

1.3 栈的链式存储结构

栈的链式结构是通过链表连接起来的。好了，我们现在再回忆一下栈的结构，栈是先进后出，所有的操作都在栈顶完成，包括插入和删除，所以要考虑一下讲栈顶放在整个链表的头部还是尾部。因为链表具体头结点，因此可以考虑将栈顶和头结点结合。我们将栈顶的元素放在一条链表的头部。所以通常来说，对于栈链来说，是不需要头结点的。

链式栈.png

而从计算机内存的角度看栈链，基本不存在栈满的情况，除非内存没有了可以使用的空间。更直观地解释栈链与数组栈之间的区别就是，一个是充分利用内存中的零碎空间，还有一个是占据内存中的大块空间。

1.4 栈链的各类功能实现

/*
@author youDaily
*/
//属性定义和构造函数
class InitStack{
    private int [] data = new int[1];  　　//存储元素值
    private InitStack nextStack;  　　　　　//存储下一地址
    public InitStack() {  　　　　　　　　　　//用于生成头结点
        this.data = null;
        this.nextStack = null;
    }
    public InitStack(int data) {  　　　　　//用于生成链栈结点
        this.data[0] = data;
        this.nextStack = null;
    }
}
//清空栈链
public void clearStack() {
    this.nextStack = null;  　　　　//令头结点的下一地址为空，链栈即被清空
 }
// 检查栈链是否为空
public int stackLength() {
    InitStack theStack = this.nextStack;  　　//获取头结点的下一地址即链栈的第一个结点
    int i = 0;  　　　　　　　　　　　　　　　　 　//初始化计数器
    for (i = 0; theStack != null; i++) {  　　//循环判断如不为空，则计数器加一
        theStack = theStack.nextStack;
    }
    return i;
}
// 获取栈顶元素
public int [] getTop() {
    if(this.nextStack == null) {  　　　　//判断是否为空栈
        return null;
    }
    return this.nextStack.data;
}
// 进行压栈
public void push(int input) {
     InitStack initStack = new InitStack(input);
     initStack.nextStack = this.nextStack;
     this.nextStack = initStack;
 }
//元素出栈
public int [] pop() {
    if (this.nextStack == null) {  　　　　　　　　　　//判断栈是否为空
        return null;
    }
    int [] i = this.nextStack.data;  　　　　　　　　 //获取栈顶元素值
    this.nextStack = this.nextStack.nextStack;  　　//删除栈顶元素
    return i;
}
//栈顶到栈底遍历栈
public String stackTraverse() {  　　　　　　　　//这里通过输出栈元素值来表示遍历

    InitStack theStack = this.nextStack;
    String s = "";

    while(theStack != null) {  　　　　　　　　　//循环遍历栈
        s = theStack.data[0] + "、" + s;
        theStack = theStack.nextStack;
    }

    if(s.length() == 0) {  　　　　　　　　　　　//如果未获得值，则直接输出空字符串
        return s;
    }
    return s.substring(0,s.length() - 1);  　//除去最后的顿号后返回字符串

2 队列的多种存储结构以及实现

和栈一样，队列也有两种实现的方式，顺序队列和链式队列。其中顺序队列中需要注意所谓的“溢出”问题。在接下来的内容中，我将详细讲述。

2.1 队列的顺序存储结构