|
《数据结构》顺序栈，链栈操作与完整代码
前言
栈
限定仅在表尾进行插入或删除操作的线性表，表尾称之为栈顶，表头称之为栈尾，遵循先进后出原则
顺序栈?
初始化栈?
#include<iostream>>
using namespace std;
#define MAXSIZE 1005
typedef struct{
int *base; //栈底指针
int *top; //栈头指针
int stacksize;/栈最大容量
}SqStack;
int InitStack(SqStack *s)
{
s->base = new int[MAXSIZE];//为栈动态分配最大容量为MAXSIZE的数组空间
if(!s->base) return 0;
s->top = s->base; //top初始为base,空栈
s->stacksize = MAXSIZE;
return 1;
}
入栈
判断栈是否满，满了就返回ERROR
将新元素压入栈，栈顶指针+1
int Push(SqStack *s,int e)
{
if(s->top-s->base==s->stacksize)
{
cout<<"ERROR"<<endl;
return 0;
}
*s->top++=e; //*s.top=e;s.top++;
return 1;
}
?出栈
判断是否空，空就返回0
栈顶元素-1，栈顶元素出栈
int Pop(SqStack *s,int *e)
{
if(s->top==s->base) return 0;
*e = *--s->top; //--s.top;e=*s.top
return 1;
}
?取栈顶元素
int GetTopStack(SqStack *s, int *e) {
if (s->top == s->base) {
return 0;
}
*e = *(s->top - 1);
return *e;
}
?遍历
int StackTraverse(SqStack *s) {
int *p;
if (s->top == s->base) {
cout<<"Stack is NULL."<<endl;
return 0;
}
p = s->top;
// 由栈顶依次向下遍历
while (p > s->base) {
p--;
cout<< *p <<" ";
}
cout<<endl;
return 1;
}
?判断是否为空
bool EmptyStack(SqStack *s)
{
if(s->base == s->top) return true;
else return false;
}
?求表长
int StackLength(SqStack *s)
{
return (s->top - s->base);
}
?清除表
void ClearStack(SqStack *s)
{
if(s->base) s->top=s->base;
cout<<"----------------clear success-----------------"<<endl;
}
?完整代码
#include<iostream>>
using namespace std;
#define MAXSIZE 1005
typedef struct{
int *base;
int *top;
int stacksize;
}SqStack;
int InitStack(SqStack *s)
{
s->base = new int[MAXSIZE];
if(!s->base) return 0;
s->top = s->base;
s->stacksize = MAXSIZE;
return 1;
}
bool EmptyStack(SqStack *s)
{
if(s->base == s->top) return true;
else return false;
}
int StackLength(SqStack *s)
{
return (s->top - s->base);
}
void ClearStack(SqStack *s)
{
if(s->base) s->top=s->base;
cout<<"----------------clear success-----------------"<<endl;
}
int Push(SqStack *s,int e)
{
if(s->top-s->base==s->stacksize)
{
cout<<"ERROR"<<endl;
return 0;
}
*s->top++=e; //*s.top=e;s.top++;
return 1;
}
int Pop(SqStack *s,int *e)
{
if(s->top==s->base) return 0;
*e = *--s->top; //--s.top;e=*s.top
return 1;
}
int GetTopStack(SqStack *s, int *e) {
if (s->top == s->base) {
return 0;
}
*e = *(s->top - 1);
return *e;
}
int StackTraverse(SqStack *s) {
int *p;
if (s->top == s->base) {
cout<<"Stack is NULL."<<endl;
return 0;
}
p = s->top;
// 由栈顶依次向下遍历
while (p > s->base) {
p--;
cout<< *p <<" ";
}
cout<<endl;
return 1;
}
int main()
{
SqStack q,*s;
s = &q;
InitStack(s);
int n,e;
cout<<"the num you come in:"<<endl;
cin>>n;
cout<<"come in the data"<<endl;
for(int i=0;i<n;i++)
{
cin>>e;
Push(s,e);
}
int l = StackLength(s);
cout<<"表长为；"<<l<<endl;
e = GetTopStack(s, &e);
cout<<"the top data is "<<e<<endl;
StackTraverse(s);
cout<<"come the top data"<<endl;
if(e = Pop(s,&e)){
cout<<"come out success"<<endl;
StackTraverse(s);
}
return 0;
}
?链栈
初始化
#include<iostream>
using namespace std;
typedef struct Node {
int data;
struct Node *next;
}StackNode, *PStackNode;
typedef struct{
PStackNode top;
int count;
}LinkStack, *PLinkStack;
//初始化
PLinkStack InitLinkStack(){
PLinkStack S;
S = new LinkStack;
if(!S){
return NULL;
}
S->top = NULL;
S->count = 0;
return S;
}
入栈
//入栈
void PushLinkStack(PLinkStack S, int e){
PStackNode p;
p = new StackNode;
if(!p){
return;
}
p->data = e;
p->next = S->top;//p的指针域指向S->top
S->top = p;
S->count++;
}
出栈
//出栈
int PopLinkStack(PLinkStack S, int *e){
PStackNode p;
if(EmptyLinkStack(S)){
cout<<"Stack NULL!"<<endl;
return 0;
}
*e = S->top->data;
p = S->top;//p暂时储存栈顶
S->top = S->top->next;//修改栈顶元素，指向新的栈顶元素
delete p;
return 1;
}
判断是否为空
//判断是否空
int EmptyLinkStack(PLinkStack S){
return (S->top== NULL);
}
获取栈顶元素
//获取栈顶元素
int GetTopLinkStack(PLinkStack S, int *e){
if(EmptyLinkStack(S)){
cout<<"Stack NULL!"<<endl;
return 0;
}
*e = S->top->data;
return *e;
}
遍历
//遍历
void PrintLinkStack(PLinkStack S){
PStackNode p;
if(EmptyLinkStack(S)){
cout<<"Stack NULL!"<<endl;
return;
}
p = S->top;
while(p){
cout<<p->data<<" ";
p = p->next;
}
cout<<endl;
}
栈大小
//栈大小
int LengthLinkStack(PLinkStack S){
if(!S){
return 0;
}
return S->count;
}
完整代码
#include<iostream>
using namespace std;
typedef struct Node {
int data;
struct Node *next;
}StackNode, *PStackNode;
typedef struct{
PStackNode top;
int count;
}LinkStack, *PLinkStack;
//初始化
PLinkStack InitLinkStack(){
PLinkStack S;
S = new LinkStack;
if(!S){
return NULL;
}
S->top = NULL;
S->count = 0;
return S;
}
//判断是否空
int EmptyLinkStack(PLinkStack S){
return (S->top== NULL);
}
//入栈
void PushLinkStack(PLinkStack S, int e){
PStackNode p;
p = new StackNode;
if(!p){
return;
}
p->data = e;
p->next = S->top;
S->top = p;
S->count++;
}
//出栈
int PopLinkStack(PLinkStack S, int *e){
PStackNode p;
if(EmptyLinkStack(S)){
cout<<"Stack NULL!"<<endl;
return 0;
}
*e = S->top->data;
p = S->top;
S->top = S->top->next;
delete p;
return 1;
}
//获取栈顶元素
int GetTopLinkStack(PLinkStack S, int *e){
if(EmptyLinkStack(S)){
cout<<"Stack NULL!"<<endl;
return 0;
}
*e = S->top->data;
return *e;
}
//遍历
void PrintLinkStack(PLinkStack S){
PStackNode p;
if(EmptyLinkStack(S)){
cout<<"Stack NULL!"<<endl;
return;
}
p = S->top;
while(p){
cout<<p->data<<" ";
p = p->next;
}
cout<<endl;
}
//栈大小
int LengthLinkStack(PLinkStack S){
if(!S){
return 0;
}
return S->count;
}
int main()
{
PLinkStack S;
int n,e;
cout<<"input the number of datas :";
cin>>n;
cout<<endl;
S = InitLinkStack();
cout<<"input datas :";
for(int i=0;i<n;i++){
cin>>e;
PushLinkStack(S, e);
}
cout<<"The Stack is:"<<endl;
PrintLinkStack(S);
cout<<endl;
PopLinkStack(S, &e);
cout<<"The pop data is:"<<e<<endl;
GetTopLinkStack(S, &e);
cout<<"Come out and The top data is:"<<e<<endl;
cout<<"The new Stack is:";
PrintLinkStack(S);
cout<<endl;
cout<<"The Length is:"<<LengthLinkStack(S)<<endl;
return 0;
}
|