特殊线性表———-栈（1）

栈是先进后出的特殊线性表，只允许在表的末端进行插入和删除，后面将介绍两种实现栈的方式，分别是基于数组的实现、基于链表的实现。

栈的抽象定义

class Mystack { public: 	Mystack() {} 	virtual void push(int &x) = 0; 	virtual bool pop(int &x) = 0; 	virtual bool Top(int &x) const = 0; 	virtual bool IsEmpty()const = 0; 	virtual bool IsFull()const = 0; 	virtual int getSize()const = 0; };   

顺序栈-----------使用数组表示栈空间

定义：

#pragma once #include "Mystack.h" #include <iostream> #include <assert.h> using namespace std;  const int stackIncreament = 20;   class SeqStack : public Mystack { public: 	SeqStack(int sz = 50);                 //建立一个空栈 	~SeqStack() { delete[]elements; }      //析构函数  	//如果栈满，则溢出程序处理，否则插入x 	void push(int &x);                   	//如果栈空，则返回FALSE，否则使用x传递栈顶的值，top-1 	bool pop(int &x);  	//如果栈空，则返回FALSE，否则使用x传递栈顶的值 	bool Top(int &x);  	//判断栈是否为空 	bool IsEmpty()const { 		return (top == -1) ? true : false; 	}  	//判断栈是都为满 	bool IsFull()const { 		return (top == maxSize - 1) ? true : false; 	}  	//获取栈当前的size 	int getSize()const { 		return top + 1; 	}  	//将栈置空 	void MakeEmpty() { 		top = -1; 	}  	//重载 操作 << 	friend ostream& operator<<(ostream& os, SeqStack& s);   private: 	int *elements;				//栈数组指针 	int top;					//栈顶指针 	int maxSize;				//栈的最大容量 	void overflowProcess();		//溢出处理程序 };   

实现：

#include "SeqStack.h"   SeqStack::SeqStack(int sz):top(-1),maxSize(sz) { 	elements = new int[maxSize];		//创建栈的数组空间 	assert(elements == NULL);            //断言：动态分配是否成功  }  void SeqStack::push(int & x) { 	//首先判断栈是否已满，满则转入溢出处理 	if(IsFull() == true){ 		overflowProcess(); 	}  	elements[++top] = x;    //将top+1，再插入值x }  bool SeqStack::pop(int & x) { 	//先判断是否为空，为空则返回FALSE 	if (IsEmpty() == true) { 		return false; 	}  	x = elements[top--];     //使用x返回top所指，再讲top-1 	return true; }  bool SeqStack::Top(int & x) { 	//空栈则为FALSE 	if (IsEmpty() == true) { 		return false; 	}  	//栈不为空，则返回栈顶元素的值 	x = elements[top]; 	return true; }  ostream& operator<<(ostream& os, SeqStack& s) { 	//输出栈中元素 	os << "top = " << s.top << endl; 	for (int i = 0; i <= s.top; ++i) { 		os << i << ": " << s.elements[i] << endl; 	} 	return os; }   void SeqStack::overflowProcess() { 	//栈溢出时，扩充栈的存储空间 	int *Newelement = new int[maxSize + stackIncreament]; 	if (Newelement == NULL) { 		cout << "分配内存失败"; 		exit(1); 	} 	for (int i = 0; i <= top; ++i) { 		Newelement[i] = elements[i]; 	} 	delete[] elements; 	elements = Newelement; }