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

一、顺序栈

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

 

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.运行如图:

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

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

上一篇:蓝桥杯等差素数列


下一篇:堆栈