欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Java数据结构之栈的详解

程序员文章站 2022-06-24 11:11:57
目录栈是先进后出的特殊线性表,只允许在表的末端进行插入和删除,后面将介绍两种实现栈的方式,分别是基于数组的实现、基于链表的实现。栈的抽象定义class mystack{public:mystack()...

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

栈的抽象定义

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;
}

总结

本篇文章就到这里了,希望能够给你带来帮助,也希望您能够多多关注的更多内容!

相关标签: Java 详解