顺序栈基本操作的实现

前面已经讨论过链式栈的实现。与链式栈不同,顺序栈通过数组来描述栈,在数据读取时间上相比于链式栈有一些优势。我们在实际应用时要视情况选择适合的实现方式来实现栈。

#include <bits/stdc++.h>
using namespace std;

class SeqStack
{
public:
    SeqStack(int cnt);
    bool pop(); //出栈
    bool push(int num); //压栈
    bool isFull();
    bool isEmpty();
    int getLength(); //取栈的长度
    void show();
    ~SeqStack()
    {
        delete [] p;
    }
private:
    int top; //栈顶位置
    int bottom; //栈底位置,此处不存放有效值
    int * p; //顺序栈数组的首地址
    int cnt; //顺序栈的最大长度
};

SeqStack::SeqStack(int cnt)
{
    p = new int[cnt+1]();
    bottom = top = 0;
    this->cnt = cnt;
}

bool SeqStack::isEmpty()
{
    if (bottom == top)
        return true;
    else
        return false;
}

bool SeqStack::isFull()
{
    if (top == cnt)
        return true;
    else
        return false;
}

int SeqStack::getLength()
{
    return top;
}

bool SeqStack::push(int num)
{
    if (this->isFull())
    {
        cout<<"顺序栈已满,无法压栈!"<<endl;
        return false;
    }
    top++;
    *(p+top) = num;
    return true;
}

bool SeqStack::pop()
{
    if (this->isEmpty())
    {
        cout<<"顺序栈为空,无法出栈!"<<endl;
        return false;
    }
    top--;
    return true;
}

void SeqStack::show()
{
    if (this->isEmpty())
    {
        cout<<"顺序栈为空,无法遍历!"<<endl;
        return;
    }
    for (int i = 1; i<=top; i++)
    {
        printf("%d ",*(p+i));
    }
    printf("\n");
}

int main()
{
    SeqStack stack(5);
    for (int i = 1; i<=5; i++)
    {
        stack.push(i);
    }
    stack.push(6);
    stack.show();
    stack.pop();
    stack.show();
    for (int i = 5; i>=1; i--)
    {
        stack.pop();
    }
    stack.show();
    return 0;
}

main函数中测试代码的运行结果如下:

发表评论

电子邮件地址不会被公开。 必填项已用*标注