链栈

一、链栈的基本概念

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

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;
  }
}
用户头像
登录后发表评论