什么是堆栈
堆栈(英语: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; } }