正文

Java数据结构之栈的简单操作

︶ㄣ米米素材网 メ
米米素材网V管理员 / 阅读
0714

这篇文章主要介绍了Java数据结构之栈简单操作的相关资料,需要的朋友可以参考下,希望能够给你带来帮助

栈是先进后出的特殊线性表，只允许在表的末端进行插入和删除，后面将介绍两种实现栈的方式，分别是基于数组的实现、基于链表的实现。

栈的抽象定义

?
1
2
3
4
5
6
7
8
9
10
11
class Mystack
{
public:
    Mystack() {}
    virtual void push(int &x) = 0;
    virtual bool pop(int &x) = 0;
    virtual bool Top(int &x) const = 0;
    virtual bool IsEmpty()const = 0;
    virtual bool IsFull()const = 0;
    virtual int getSize()const = 0;
};

顺序栈-----------使用数组表示栈空间

定义：

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#pragma once
#include "Mystack.h"
#include <iostream>
#include <assert.h>
using namespace std;
const int stackIncreament = 20;
 
class SeqStack : public Mystack
{
public:
    SeqStack(int sz = 50);                 //建立一个空栈
    ~SeqStack() { delete[]elements; }      //析构函数
    //如果栈满，则溢出程序处理，否则插入x
    void push(int &x);                
    //如果栈空，则返回FALSE，否则使用x传递栈顶的值，top-1
    bool pop(int &x);
    //如果栈空，则返回FALSE，否则使用x传递栈顶的值
    bool Top(int &x);
    //判断栈是否为空
    bool IsEmpty()const {
        return (top == -1) ? true : false;
    }
    //判断栈是都为满
    bool IsFull()const {
        return (top == maxSize - 1) ? true : false;
    }
    //获取栈当前的size
    int getSize()const {
        return top + 1;
    }
    //将栈置空
    void MakeEmpty() {
        top = -1;
    }
    //重载 操作 <<
    friend ostream& operator<<(ostream& os, SeqStack& s);
 
private:
    int *elements;              //栈数组指针
    int top;                    //栈顶指针
    int maxSize;                //栈的最大容量
    void overflowProcess();     //溢出处理程序
};

实现：

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include "SeqStack.h"
 
SeqStack::SeqStack(int sz):top(-1),maxSize(sz)
{
    elements = new int[maxSize];        //创建栈的数组空间
    assert(elements == NULL);            //断言：动态分配是否成功
}
void SeqStack::push(int & x)
{
    //首先判断栈是否已满，满则转入溢出处理
    if(IsFull() == true){
        overflowProcess();
    }
    elements[++top] = x;    //将top+1，再插入值x
}
bool SeqStack::pop(int & x)
{
    //先判断是否为空，为空则返回FALSE
    if (IsEmpty() == true) {
        return false;
    }
    x = elements[top--];     //使用x返回top所指，再讲top-1
    return true;
}
bool SeqStack::Top(int & x)
{
    //空栈则为FALSE
    if (IsEmpty() == true) {
        return false;
    }
    //栈不为空，则返回栈顶元素的值
    x = elements[top];
    return true;
}
ostream& operator<<(ostream& os, SeqStack& s) {
    //输出栈中元素
    os << "top = " << s.top << endl;
    for (int i = 0; i <= s.top; ++i) {
        os << i << ": " << s.elements[i] << endl;
    }
    return os;
}
 
void SeqStack::overflowProcess()
{
    //栈溢出时，扩充栈的存储空间
    int *Newelement = new int[maxSize + stackIncreament];
    if (Newelement == NULL) {
        cout << "分配内存失败";
        exit(1);
    }
    for (int i = 0; i <= top; ++i) {
        Newelement[i] = elements[i];
    }
    delete[] elements;
    elements = Newelement;
}

总结

本篇文章就到这里了，希望能够给你带来帮助，也希望您能够多多关注米米素材网的更多内容！

原文链接：https://blog.csdn.net/q793145253/article/details/120478986