# 顺序栈****
**$栈是操作受限的**线性表**，插入删除数据元素**只能在线性表的一端**进行$**
## 栈类的定义 c++版异常捕获优化
#include<iostream>
using namespace std;
const int MAX_SIZE = 100;
class Stack
{
private:
char* data; //线性表
int size;
int top;
public:
Stack();
Stack(int s); //有参构造函数
~Stack();
void push(char ch); //入栈
char pop(); //出栈
char getTop(); //弹出栈顶
bool isEmpty();
bool isFull();
class Empty {};
class Full {};
};
Stack::Stack()
{
size = MAX_SIZE;
top = -1;
data = new char[MAX_SIZE]; //构造最大空间
}
Stack::Stack(int s) //有参构造函数
{
size = s;
top = -1;
data = new char[size];
}
Stack::~Stack() //析构函数
{
delete[]data;
}
void Stack::push(char ch) //入栈
{
if (isFull())
{
throw Full();
}
else
{
data[++top] = ch;
}
}
char Stack::pop() //出栈
{
if (isEmpty())
{
throw Empty();
}
else
{
return data[top--];
}
}
char Stack::getTop() //弹出栈顶
{
if (!isEmpty())
{
return data[top];
}
}
bool Stack::isEmpty() //栈空
{
if (top == -1)
return true;
else
return false;
}
bool Stack::isFull() //栈满
{
if (top == size - 1)
return true;
else
return false;
}
int main()
{
try {
Stack s1;
}
catch (Stack::Full) //异常内部类捕获
{
cout << "Full!" << endl;
}
catch (Stack::Empty)
{
cout << "Empty" << endl;
}
return 0;
}
## 栈类的定义c语言版
#include<stdio.h>
#include<stdlib.h>
#define MAX_SIZE 100
typedef struct Stack //结构体
{
char* data;
int size;
int top;
};
void initStack(Stack& s) //初始化
{
s.data = (char*)malloc(sizeof(char) * MAX_SIZE);
if(!s.data)
exit(0);
s.size = MAX_SIZE;
s.top = -1;
}
void destroyStack(Stack& s)
{
free(s.data); //内存回收
}
void push(Stack s, char ch)
{
if (!isFull(s))
{
s.data[++s.top] = ch;
}
}
char pop(Stack s) //出栈
{
if (!isEmpty(s))
{
return s.data[s.top--];
}
}
char getTop(Stack s) //获取栈顶元素
{
if (!isEmpty(s))
{
return s.data[s.top];
}
}
bool isEmpty(Stack s) //栈空
{
if (s.top == -1)
return true;
else
return false;
}
bool isFull(Stack s) //栈满
{
if (s.top == size-1)
return true;
else
return false;
}
## **顺序栈的应用 特殊字符的处理**
``源代码
#include<string>
#include<iostream>
using namespace std;
const int MAX_SIZE = 100;
class Stack
{
private:
char* data; //线性表
int size;
int top;
public:
Stack();
Stack(int s); //有参构造函数
~Stack();
void push(char ch); //入栈
char pop(); //出栈
char getTop(); //弹出栈顶
bool isEmpty();
bool isFull();
void setNull();
void reversedisplay(); //为了更好的正向输出栈
};
Stack::Stack()
{
size = MAX_SIZE;
top = -1;
data = new char[MAX_SIZE]; //构造最大空间
}
Stack::Stack(int s) //有参构造函数
{
size = s;
top = -1;
data = new char[size];
}
Stack::~Stack() //析构函数
{
delete[]data;
}
void Stack::push(char ch) //入栈
{
if (!isFull())
{
data[++top] = ch;
}
}
char Stack::pop() //出栈
{
if (!isEmpty())
{
return data[top--];
}
}
char Stack::getTop() //弹出栈顶
{
if (!isEmpty())
{
return data[top];
}
}
bool Stack::isEmpty() //栈空
{
if (top == -1)
return true;
else
return false;
}
bool Stack::isFull() //栈满
{
if (top == size - 1)
return true;
else
return false;
}
void Stack::setNull()
{
top = -1;
}
void Stack::reversedisplay()//展示
{
int len = top;
char strx[100];
for (int i = 0;i <= len;i++)
{
strx[len - i] = pop();
}
strx[len + 1] = '\0';
if (top == -1)
cout << "栈为空" << endl;
else
cout << strx;
}
int main()
{
char str=0;
Stack s1;
while (str!= '#')
{
str = getchar();
switch (str) {
case '<':
{
s1.pop();
break;
}
case '@':
{
s1.setNull();
break;
}
case '\n':
{
s1.reversedisplay();
break;
}
case '#':
{
s1.reversedisplay();
break;
}
default:
{
s1.push(str);
break;
}
}
}
return 0;
}
## 回文字符串判断``
上接stack类定义
int main()
{
Stack s1;
int len=0;
char strx[100];
cin >> strx;
len = strlen(strx);
for (int i = len / 2 - 1;i >= 0;i--) //把前一半的字符从后到前压栈
{
s1.push(strx[i]);
}
bool flag = true;
for(int i=len-1;i>len/2;i--) //出栈的时候和字符串后一半从后往前捋一样，这样不用理会中间的那个
{
if (s1.pop() != strx[i])
{
flag = false;
break;
}
}
if (flag)
{
cout << "是回文字符串" << endl;
}
else
cout<< "不是回文字符串" << endl;
return 0;
}
## 用类模板实现顺序栈
#include<iostream>
using namespace std;
const int MAX_SIZE = 100;
template <class T>
class Stack
{
private:
T* data; //线性表
int size;
int top;
public:
Stack();
Stack(int s); //有参构造函数
~Stack();
void push(T ch); //入栈
T pop(); //出栈
T getTop(); //弹出栈顶
bool isEmpty();
bool isFull();
class Empty {};
class Full {};
};
template <class T>
Stack<T>::Stack()
{
size = MAX_SIZE;
top = -1;
data = new T[MAX_SIZE]; //构造最大空间
}
template <class T>
Stack<T>::Stack(int s) //有参构造函数
{
size = s;
top = -1;
data = new T[size];
}
template <class T>
Stack<T>::~Stack() //析构函数
{
delete[]data;
}
template <class T>
void Stack<T>::push(T ch) //入栈
{
if (isFull())
{
throw Full();
}
else
{
data[++top] = ch;
}
}
template <class T>
T Stack<T>::pop() //出栈
{
if (isEmpty())
{
throw Empty();
}
else
{
return data[top--];
}
}
template <class T>
T Stack<T>::getTop() //弹出栈顶
{
if (!isEmpty())
{
return data[top];
}
}
template <class T>
bool Stack<T>::isEmpty() //栈空
{
if (top == -1)
return true;
else
return false;
}
template <class T>
bool Stack<T>::isFull() //栈满
{
if (top == size - 1)
return true;
else
return false;
}
int main()
{
try {
Stack<int> s1;
Stack<char> s2;
}
catch (Stack<int>::Full) //不同异常内部类捕获，注意增加
{
cout << "Full!" << endl;
}
catch (Stack<char>::Empty)
{
cout << "Empty" << endl;
}
return 0;
}
## 两栈共享存储空间
#include<iostream>
using namespace std;
const int MAX_SIZE = 100;
template <class T>
class Stack
{
private:
T* data; //线性表
int size;
int top1,top2;
public:
Stack();
Stack(int s); //有参构造函数
~Stack();
void push(int n,T ch); //入栈
T pop(int n); //出栈
T getTop(int n); //弹出栈顶
bool isEmpty(int n);
bool isFull(int n);
class Empty {}; //异常内部类
class Full {};
class numerror{}; //数字输入异常类
};
template <class T>
Stack<T>::Stack()
{
size = MAX_SIZE;
top1 = -1;
top2 = size;
data = new T[MAX_SIZE]; //构造最大空间
}
template <class T>
Stack<T>::Stack(int s) //有参构造函数
{
size = s;
top1 = -1;
top2 = size;
data = new T[size];
}
template <class T>
Stack<T>::~Stack() //析构函数
{
delete[]data;
}
template <class T>
void Stack<T>::push(int n,T ch) //入栈
{
if (isFull(n))
{
throw Stack<T>::Full();
}
else
{
if (n == 1)
data[++top1] = ch;
else if (n == 2)
data[--top2] = ch;
else
throw Stack<T>::numerror();
}
}
template <class T>
T Stack<T>::pop(int n) //出栈
{
if (isEmpty(n))
{
throw Stack<T>::Empty();
}
else
{
if (n == 1)
return data[top1--];
else if (n == 2)
return data[top2++];
else
throw Stack<T>::numerror();
}
}
template <class T>
T Stack<T>::getTop(int n) //弹出栈顶
{
if (!isEmpty(n))
{
if (n == 1)
return data[top1];
else if (n == 2)
return data[top2];
else
throw Stack<T>::numerror();
}
}
template <class T>
bool Stack<T>::isEmpty(int n) //栈空
{
if (n == 1)
{
if (top1 == -1)
return true;
else
return false;
}
else if(n==2)
{
if (top2 == size)
return true;
else
return false;
}
}
template <class T>
bool Stack<T>::isFull(int n) //栈满
{
if (top1 ==top2 - 1)
return true;
else
return false;
}
int main()
{
try {
Stack<int> s1;
Stack<char> s2;
s1.push(2,2);
s1.push(2, 3);
cout << s1.pop(2) << endl;
cout<<s1.pop(2);
}
catch (Stack<int>::Full) //不同异常内部类捕获 可视情况添加
{
cout << "Full!" << endl;
}
catch (Stack<char>::Empty)
{
cout << "Empty" << endl;
}
catch (Stack<int>::numerror)
{
cout << "number erroe!!" << endl;
}
return 0;
}
# 链栈
**<u><mark>链头作为栈顶，不需要设置头节点</u>**</mark>
#include<iostream>
using namespace std;
template<class T> //结构体模板
struct node
{
T data;
struct node* next;
};
template<class T> //链栈模板类
class LinkStack
{
private:
struct node<T>* top;
public:
LinkStack();
~LinkStack();
void push(T x);
T pop();
T getTop();
bool isEmpty(); //不需要判满，因为不会满
};
template<class T> //构造函数
LinkStack<T>::LinkStack()
{
top = NULL;
}
template<class T> //析构函数 清除链表
LinkStack<T>::~LinkStack()
{
struct node<T>* p=NULL;
while (top)
{
p = top->next;
delete top;
top = p;
}
}
template<class T> //获取栈顶元素
T LinkStack<T>::getTop()
{
if (top == NULL)
return -1;
else
{
T x = top->data;
return x;
}
}
template<class T> //压栈
void LinkStack<T>::push(T x)
{
struct node<T>* s = new struct node<T>;
s->data = x;
s->next = top;
top = s;
}
template<class T> //出栈
T LinkStack<T>::pop()
{
if (top == NULL)
{
return -1; //抛出异常
}
T x = top->data;
struct node<T>* p = top;
top = top->next;
delete p;
return x;
}
template<class T>
bool LinkStack<T>::isEmpty()
{
if (top == NULL)
return true;
else
return false;
}
int main()
{
LinkStack<int> s1;
s1.push(2);
s1.push(3);
cout << s1.pop()<<endl;
cout << s1.pop()<<endl;
return 0;
}