顺序栈

一、顺序栈的概念

栈的存储与一般线性表的存储类似,主要分为两种:顺序存储和链式存储。

通过顺序存储方式实现的栈称之为顺序栈。

类似于顺序表的定义,要分配一块连续的存储空间存储栈中的元素,栈底的位置可以固定在数组的任何一端(一般情况下,在下标为0的一端),而栈顶随着插入和删除动态变化,我们可以用一个变量来记录当前栈顶的位置(实际上是栈顶元素的下一个位置),存储结构如下所示:

顺序栈的存储结构:
顺序栈的存储结构

二、顺序栈的实现

typedef int DataType; // 以整型为栈的数据类型

class SeqStack {
  private:
    DataType *base;   // 栈底指针
    DataType *top;    // 栈顶指针始终指向栈顶元素的后一个位置
    int size;         // 栈的大小

  public:
    SeqStack(int stacksize = 100) {   // 构造了一个空栈,默认大小为100个单元
      base = new DataType [staticsize];
      top = base;   // 指向栈顶元素的后一位置
      size = stacksize;
    }

    ~SeqStack() {   // 销毁一个已存在的栈
      delete[] base;
      top = NULL;
      base = NULL;
    }

    int Empty_Stack();  // 判断栈是否为空
    int Push_Stack(DataType e);   // 将元素e插入栈顶
    int Pop_Stack(DataType &e);   // 从栈顶删除一个元素到e中返回
    int GetTop_Stack(DataType &e);  // 从栈顶取出一个元素到e中返回
}

(一)判断栈是否为空

算法思想: 判断top是否小于等于base,小于等于则为空栈,返回1,否则返回0。
实现如下:

int SeqStack::Empty_Stack() {
  return (top <= base)
}

(二)入栈操作

算法思想:首先判断栈是否已满,若满则失败,返回0;否则,由于栈的top指向栈顶元素的后一个位置,将入栈元素赋到top的位置,再将top+1指向新的位置,成功返回1。
实现如下:

int Push_Stack(DataType e) {
  if (top - base < size) {  // 判断栈是否为满
    *top = e;
    top++;
    return 1;
  } else {
    return 0;
  }
}

(三)出栈操作

算法思想:首先判断栈是否为空,若空则失败,返回0;否则,由于栈的top指向栈顶元素的后一位置,要先修改top为top-1,在将其所指向的元素以引用参数e返回,成功返回1。
实现如下:

int SeqStack::Pop_Stack(DataType &e) {
  if (top > base) { // 判断栈是否为空
    top--;
    e = *top;
    return 1;
  } else {
    return 0;
  }
}

(四)取栈顶元素操作

算法思想:首先判断栈是否为空,若空则失败,返回0;否则,由于栈的top指向栈顶元素的后一位置,返回top-1所指单元的值,栈不发生变化。
实现如下:

int SeqStack::GetTop_Stack(DataType &e) {
  if (top > base) { // 判断栈是否为空
    e = *(top - 1);
    return 1;
  } else {
    return 0;
  }
}
用户头像
登录后发表评论