Tim的资源站

一、链栈的基本概念

栈也可以用链式存储方式实现。一般链栈用单链表表示，其结点结构与单链表的结构相同。即结点为：

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

class StackNode {   // 定义链栈的结点
  public DataType data;
  StackNode *next;

  StackNode() {
    next = NULL;
  }
}

由于栈的删除、插入等操作主要是在栈顶进行，而在链表的表头进行插入和删除操作比较方便。所以，我们把表头作为栈顶。存储结构如下图所示：

栈的链式存储：

二、链栈的实现

class LinkStack {
  private:
    StackNode *top;

  public:
    LinkStack() {   // 构造一个新的空栈
      top = NULL;
    }

    ~LinkStack() {  // 栈顶指针赋空表示为空栈
      StackNode *p;
      while(top) {
        p = top;
        top = top->next;
        delete p;
      }
      top = NULL;
    }

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

（一）判断栈是否为空

算法思想：判断top是否为空，为空则为空栈，返回1，否则返回0。
实现如下：

int LinkStack::Empty_Stack() {  // 判断链表是否为空
  return (!top)
}

（二）入栈操作

算法思想：首先为链栈分配空间，若成功，将入栈元素赋值到申请的链栈结点，并插入栈顶，使其成为栈顶元素，成功返回1；否则失败，返回0。
实现如下：

int LinkStack::Push_Stack(DataType e) {   // 链栈入栈操作
  StackNode *p = new StackNode;   // 申请结点

  if(p) {   // 申请结点成功
    p->data = e;
    p->next = top;
    top = p;    // 修改栈顶指针
    return 1;
  } else {
    return 0;
  }
}

（三）出栈操作

算法思想：首先判断链栈是否为空，若非空，则取出栈顶元素，以引用参数e返回，并删除这个结点，成功返回1；否则，失败返回0。
实现如下：

int LinkStack::Pop_Stack(int &e) {  // 链栈的出栈操作
  StackNode *p;

  if (top) {
    p = top;
    e = p->data;
    top = top->data;  // 修改栈顶指针
    delete p;   // 删除结点
    return 1;
  } else {
    return 0;
  }
}

（四）取栈顶元素操作

算法思想：首先判断栈是否为空，若非空，则取出栈顶元素，以引用参数e返回，成功返回1；否则，失败返回0。
实现如下：

int LinkStack::GetTop_Stack(DataType &e) {  // 链栈取栈顶元素
  if (top) {
    e = p->data;
    return 1;
  } else {
    return 0;
  }
}