栈

发表于 分类于 阅读次数： 本文字数： 295 阅读时长 ≈ 1 分钟

Data Structures Experiment #4 - 设计并实现栈类。

栈可以由顺序表或者链表的方式去实现。通常，栈的操作是固定的，但是在编程过程中有时希望可以由自己控制到底使用链栈还是顺序栈。所以通常使用多态（什么是多态？）去编写链栈与顺序栈的代码。

  • void push_back(int data);
    将data入栈。
  • int top() const;
    询问栈顶元素的值并返回。
  • void pop();
    弹出栈顶元素。

SeqStack

0x01 构造函数

分配MAX_ELEMENTS 大小的内存空间。

“栈顶指针”初始化为0。

1
2
3
4
SeqStack::SeqStack(){
    SeqList = new int[MAX_ELEMENTS];
    data_top = 0;
}

0x02 push_back

判断栈满否。

栈未满则压入栈，“栈顶指针”上移。

1
2
3
4
5
6
7
8
void SeqStack::push_back(int data){
    if (data_top > MAX_ELEMENTS - 1)
        return;
    else {
        SeqList[data_top] = data;
        data_top++;
    }
}

0x03 top

判断栈空否。

栈不空则返回“栈顶指针”下一位的数值。

1
2
3
4
5
6
int SeqStack::top() const{
    if (data_top == 0)
        return 0;
    else
        return SeqList[data_top - 1];
}

0x04 pop

判断栈空否。

栈不空则“栈顶指针”下移。

1
2
3
4
5
6
void SeqStack::pop(){
    if (data_top == 0)
        return;
    else
        data_top--;
}

0x05 析构函数

释放内存。

1
2
3
4
SeqStack::~SeqStack(){
    delete[] SeqList;
    SeqList = NULL;
}

LinkStack

0x01 构造函数

栈顶指针初始化为空。

1
2
3
4
LinkStack::LinkStack(){
    head = NULL;
    length = 0;
}

0x02 push_back

链入栈。

1
2
3
4
5
6
7
void LinkStack::push_back(int data){
    StackNode *newNode = new StackNode;
    newNode->value = data;
    newNode->next = head;
    head = newNode;
    length++;
}

0x03 top

判断栈空否。

栈不空则返回栈顶指针处的数值。

1
2
3
4
5
6
int LinkStack::top() const{
    if (length == 0)
        return 0;
    else
        return head->value;
}

0x04 pop

判断栈空否。

栈不空则将栈顶元素弹出栈并释放内存。

1
2
3
4
5
6
7
8
9
10
11
void LinkStack::pop(){
    if (length == 0)
        return;
    else {
        StackNode *temp = head;
        head = head->next;
        delete temp;
        temp = NULL;
        length--;
    }
}

0x05 析构函数

逐结点释放内存。

1
2
3
4
5
6
7
8
9
10
11
LinkStack::~LinkStack(){
    for (int i = 0; i < length; i++) {
        StackNode *temp;
        temp = head;
        head = head->next;
        delete temp;
        temp = NULL;
    }
    delete head;
    head = NULL;
}