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; }
总结
本篇文章就到这里了,希望能够给你带来帮助,也希望您能够多多关注的更多内容!