什么是堆栈

堆栈（英语：stack），也可直接称栈。台湾作堆叠，在计算机科学中，是一种特殊的串行形式的数据结构，它的特殊之处在于只能允许在链结串行或阵列的一端（称为堆叠顶端指标，英语：top）进行加入资料（英语：push）和输出资料（英语：pop）的运算。另外堆叠也可以用一维阵列或连结串行的形式来完成。堆叠的另外一个相对的操作方式称为伫列。

由于堆叠数据结构只允许在一端进行操作，因而按照后进先出（LIFO, Last In First Out）的原理运作。

堆叠数据结构使用两种基本操作：推入（push）和弹出（pop）：

推入：将数据放入堆叠的顶端（阵列形式或串行形式），堆叠顶端top指标加一。
弹出：将顶端数据资料输出（回传），堆叠顶端资料减一。

类方法演示

程序分三个部分：头文件定义类（包括类数据和类方法原型）；类实现部分（类方法定义）；程序演示部分（演示压栈和出栈行为）

头文件stack.h

// stack.h -- class definition for the stack ADT
#ifndef STACK_H_
#define STACK_H_

typedef unsigned long Item;

class Stack {
private:
        enum {MAX = 10};        // constant specific to class
        Item items[MAX];        // holds stack items
        int top;                // index for top stack item
public:
        Stack(void);
        bool isempty(void) const;
        bool isfull(void) const;
        // push() returns false if stack already is full, true otherwise
        bool push(const Item & item);   // add item to stack
        // pop() returns false if stack already is empty, true otherwise
        bool pop(Item & item);          // pop top into item
};

#endif//STACK_H_

类方法定义

// stack.cpp -- Stack member functions
#include "stack.h"

Stack::Stack(void)      // create an empty stack
{
        top = 0;

        return;
}

bool Stack::isempty(void) const
{
        return top == 0;
}

bool Stack::isfull(void) const
{
        return top == MAX;
}

bool Stack::push(const Item & item)
{
        if (top < MAX) {
                items[top++] = item;
                return true;
        } else {
                return false;
        }
}

bool Stack::pop(Item & item)
{
        if (top > 0) {
                item = items[--top];
                return true;
        } else {
                return false;
        }
}

继续阅读 →