[C++知识库]特殊线性表----------栈（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;
}