一、栈的定义

栈(stack)是限定仅在表尾进行插入和删除操作的线性表,把允许插入和删除的一端称为栈顶(top),另一端称为栈底(buttom),不含任何数据元素的栈称为空栈,栈又称为先进后出(Last in First Out)的线性表,简称 LIFO 结构

二、栈的操作

  • 栈的初始化

  •  栈的清空

  • 栈的销毁

  • 栈是否为空栈

  • 栈是否为栈满

  • 获取栈顶元素

  • 栈的插入操作,又叫做入栈,压栈,进栈

  • 栈的删除操作,又叫做出栈,弹栈

 三、栈的抽象数据类型

ADT 顺序栈
    Date
        栈顶表示
        存放栈元素组
        栈元素个数的最大数
    Option
        seqstack
            输入:栈元素个数的最大数
        ~seqstack
            删除存储栈元素的数组
        push
            输入:要进栈的项item
            前置条件:栈末满
            动作:把item压入栈顶
            输出:无
            后置条件:栈顶增加了一个新元素,栈顶指示加1
        pop
            输入:无
            前置条件:栈非空
            动作:弹出栈顶元素
            输出:返回栈顶元素的值
            后置条件:删除栈顶元素,栈顶指示减1
        getTop
            输入:无
            前置条件:栈非空
            动作:取栈顶元素值
            输出:返回栈顶数据元素
            后置条件:无
        empty
            输入:无
            前置条件:无
            动作:检查栈顶指示是否等于-1
            输出:栈空时返回1,否则返回0
            后置条件:无
        full
            输入:无
            前置条件:无
            动作:检查栈顶指示是否等于maxsize-1
            输出:栈满时返回1,否则返回0
            后置条件:无
        clear
            输入:无
            前置条件:无
            动作:清空栈
            输出:无
            后置条件:栈顶指示为-1
        length
            动作:返回 top + 1
End ADT 顺序栈

四、栈的实现

// 栈的顺序存储结构
#include <iostream>
#include <cstdlib>
using namespace std;
#define MAX_SIZE = 0xFFFF;
template<typename T>
class SeqStack {
public:
 SeqStack();
 SeqStack(int size);
 SeqStack(T data[], int size);
 virtual ~SeqStack();
 void push(const T &item);
 T pop();
 T getTop();
 bool empty() const;
 bool full() const;
 void clear();
 int length() const;
protected:
 // 栈顶指示
 int top;
 // 数组名
 T *stack;
 // 栈最大可容纳元素个数
 int maxSize;
};
template<typename T>
SeqStack<T>::SeqStack(): top(-1), maxSize(MAX_SIZE){
 this->stack = new T[MAX_SIZE];
 if (this->stack == nullptr) {
  cout << "动态存储分配失败!" << endl;
  return;
 }
}
template<typename T>
SeqStack<T>::SeqStack(int size) : top(-1), maxSize(size) {
 this->stack = new T[MAX_SIZE];
 if (this->stack == nullptr) {
  cout << "动态存储分配失败!" << endl;
  return;
 }
}
template<typename T>
SeqStack<T>::SeqStack(T data[], int size) : top(-1), maxSize(size) {
 this->stack = new T[size];
 if (this->stack == nullptr) {
  cout << "动态存储分配失败!" << endl;
  return;
 }
 for (int i = 0; i < this->maxSize; i++) {
  this->stack[i] = data[i];
 }
 this->top += this->maxSize;
}
template<typename T>
SeqStack<T>::~SeqStack() {
 delete []stack;
}
template<typename T>
void SeqStack<T>::push(const T &item) {
 if (this->full()) {
  cout << "栈已满,不能压栈!" << endl;
  return;
 }
 this->top++;
 this->stack[this->top] = item;
}
template<typename T>
T SeqStack<T>::pop() {
 if (this->empty()) {
  cout << "栈已空" << endl;
 }
 else {
  T data = this->stack[this->top];
  this->top--;
  return data;
 }
}
template<typename T>
T SeqStack<T>::getTop() {
 if (this->empty()) {
  cout << "栈已空" << endl;
 }
 else {
  return this->stack[this->top];
 }
}
template<typename T>
bool SeqStack<T>::empty() const {
 return this->top == -1;
}
template<typename T>
bool SeqStack<T>::full() const {
 return this->top == this->maxSize - 1;
}
template<typename T>
void SeqStack<T>::clear() {
 this->top = -1;
}
template<typename T>
int SeqStack<T>::length() const {
 return this->top + 1;
}
int main() {
 int data[5] = { 1, 2 ,3, 4, 5 };
 SeqStack<int> stack(data, 5);
 cout << "入栈元素: ";
 for (int i = 0; i < 5; i++) {
  cout << data[i] << " ";
 }
 cout << endl;
 cout << "栈的元素个数: " << stack.length() << endl;
 cout << "栈顶元素: " << stack.getTop() << endl;
 cout << "是否栈满: " << stack.full() << endl;
 cout << "是否栈空: " << stack.empty() << endl;
 cout << "出栈元素: ";
 while (!stack.empty())
 {
  cout << stack.pop() << " ";
 }
 cout << endl;
 cout << "栈的元素个数: " << stack.length() << endl;
 cout << "栈顶元素: " << stack.getTop() << endl;
 cout << "是否栈满: " << stack.full() << endl;
 cout << "是否栈空: " << stack.empty() << endl;
 system("pause");
 return 0;
}


                                        关注【游戏讲坛】微信公众号,获取最新动态!