Tim的资源站

一、顺序栈的概念

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

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

类似于顺序表的定义，要分配一块连续的存储空间存储栈中的元素，栈底的位置可以固定在数组的任何一端（一般情况下，在下标为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;
  }
}