栈是先进后出的特殊线性表，只允许在表的末端进行插入和删除，后面将介绍两种实现栈的方式，分别是基于数组的实现、基于链表的实现。
栈的抽象定义
|
1 2 3 4 5 6 7 8 9 10 11 |
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 ; }; |
顺序栈-----------使用数组表示栈空间
定义：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
#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(); / / 溢出处理程序 }; |
实现：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
#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; } |
总结
本篇文章就到这里了，希望能够给你带来帮助，也希望您能够多多关注的更多内容！
原文链接：https://blog.csdn.net/q793145253/article/details/120478986