顺序栈和双向顺序栈的操作

2023-10-15 09:58:46

一、顺序栈

1.定义结构：

#include<stdio.h>
#include<stdlib.h>            //malloc和realloc函数的库 
#define maxsize 100           //宏不需要加';'
typedef struct  {
	int data[maxsize];
	int top;
}myStack,*Stack;

顺序栈类似于顺序表，栈中的元素可以用一个一维数组来保存，同时也要有最大值；而且还要包括一个栈顶top指针，因为栈底指针可任意为一个端点，所以可省略。

2.判空栈：

//判空栈
 int Empty(Stack L){
 	if(L->top==-1) return 1;   //为空栈
 	else return 0;            //不为空栈
 }

判空栈需要注意的是：栈顶指针刚开始是为-1

栈满对于顺序栈来说就是等于maxsize,在此不多说。

3.计算栈的长度：

int length(myStack *s)		//计算栈中元素的个数 
{
	
	printf("\n此时栈的长度为%d\n",s->top+1);
}

顺序栈的长度=top指针+1的数。

4.取栈顶元素：

//取栈顶元素
int get(myStack *s){
	if(Empty(s)) printf("栈空！"); //栈空 
	else printf("栈顶元素为：%d\n",s->data[s->top]);  //因为data存放在一维数组所以取的时候遵循数组的写法
}

5.初始化：

//初始化栈
 int Init(myStack *&s) {
 	s=(myStack *)malloc(sizeof(myStack));  //定义空间结点
 	s->top=-1;               //栈空：top==-1
    return 1;
 }

6.入栈：

 //入栈 
int push(myStack *&s, int e)  //元素e入栈 
{
	if(s -> top == maxsize - 1)
		return 0;
	else
	{
		s -> top++;				//栈顶指针加一 
		s -> data[s -> top] = e;//新插入的元素进栈 
		return 1;
	 } 
}

7.出栈：

//出栈
 void pop(Stack L){
 	int i=0 ;
 	if(Empty(L)) printf("栈空！");  //栈空
 	while(i<=L->top){                     //i<栈顶时，输出，栈顶-- 
 	printf("%d ",L->data[L->top]);
 	L->data[L->top]=0;               //将出栈的元素位置赋值0 
 	L->top--;
 	}
 }

这里根据自己思路写的，也能实现，将出栈的元素赋值为0，在遍历的时候以这个条件为基本在视觉效果较好的情况下遍历。

8.总体main函数：

int main(){
	myStack *s;				 //定义栈 
    if(Init(s)==1){           //初始化栈
		printf("初始化成功!\n"); 
	}
	printf("-----进行1-5的入栈：\n");
	printf("入栈顺序为: ") ;
	for(int i=1;i<=5;i++){
		printf("%d ",i);
		push(s,i);
	}
	length(s);                 //求栈长 
	get(s);                   //取栈顶元素 
	printf("-----进行1-5的出栈：\n");
    printf("出栈顺序为： ");
	pop(s);                 //出栈 
    length(s);              //求栈长 
    }

9.运行如图：

二、双向栈（左栈和右栈）共享一个空间

双向栈用于存储空间较大时，顺序栈无法满足，从而导致溢出或者空闲情况。

特性：栈底指针不变，栈顶指针动态变化；左右两个栈的最大空间均大于maxsize/2.

1.结构定义：

#include<stdio.h>
#include<stdlib.h>
#define maxsize 10             //宏不需要加';' 
typedef struct {
	int data[maxsize];
	int left;                          //左栈top 
	int right;                         //右栈top 
}DoubleStack,*Double;

2.初始化：

左栈和右栈的起始地都是从有效空间后一位开始的，左栈从前往后是递增，右栈是从后往前是递增。

//初始化
 int Init(Double &L){
 	L=(Double)malloc(sizeof(DoubleStack));
	if(L==NULL) return -1;
	L->left=-1;                 //左栈有效位后一位：-1 
	L->right=maxsize;           //右栈有效位后一位：maxsize 
	return 1; 
 }

3.入栈：

入栈要存在一个status的判断，个人定义为1时是左栈，为2时是右栈。

//入栈
int push(Double &L,int status,int x){   //status=1代表左数，=2代表右树 
	if(L->left+1==L->right){
		printf("栈满！");
		return -1;
	} 
	if(status==1){
		L->left++;            //左指针往后
		L->data[L->left]=x;   //赋值
	}else if(status==2){
		L->right--;           //右指针往前
		L->data[L->right]=x;   //赋值
	}
}

4.出栈：

出栈元素的值个人先将它输出在定义为0，在遍历时借用这个条件可以输出视觉感官较好的形式。

//出栈
int pop(Double &L,int status) {
	if(status==1){
		if(L->left<0) {
			printf("左栈为空！\n"); return -1;
		}else{
			printf("出%d ",L->data[L->left]);    //输出要出栈的元素 
			L->data[L->left]=0;                  //将data[L->left]赋值0 
			L->left--;
		}
	}else if(status==2){
		if(L->right>maxsize-1){
			printf("右栈为空！\n"); return -1;
		}else{
			printf("出%d ",L->data[L->right]);   //输出要出栈的元素
			L->data[L->right]=0;                 //将data[L->right]赋值0 
			L->right++;
		}
	}
}

5.遍历：

如果元素的值为0，则输出[]。

//遍历栈 
 void Print(Double &L) {
 	int i,j;
 	for(i=0;i<=maxsize-1;i++){     
 		if(L->data[i]!=0){                 //如果元素出栈则出栈函数赋值为0；输出[] 
 			printf("%d ",L->data[i]);
		 }else{
		 	printf("[]");
		 } 
	 }
 }

6.main函数：

int main(){
	DoubleStack *s;
	char L,R;
	if(Init(s)==1){
		printf("初始化成功！\n");
	}
	printf("进行1-5的入栈（左右同时）：\n");
	for(int i=1;i<=5;i++){         //for循环来输入栈 
		push(s,1,i);               //1代表左栈 
		push(s,2,i);               //2代表右栈 
	}
	printf("此时栈的元素为：");
	Print(s);
	printf("\n进行一次左栈出栈：\n"); 
	pop(s,1);
	printf("\n进行一次右栈出栈：\n"); 
	pop(s,2); 
	printf("\n此时栈的元素为：");
	Print(s); 
}

7.运行如图：

在此声明：本文两个图是借用其他博主的图。

码农公寓