数据结构 - 顺序栈的基本操作(C语言)

ゞ浴缸里的玫瑰 2022-06-04 09:58 271阅读 0赞

**顺序栈**：利用顺序存储方式实现的栈。

**顺序栈的定义**：

(1)：栈中元素用一个预设的足够长度的一维数组来实现：DataType data\[MAXSIZE\]。

(2)：栈底位置可以设置在数组的任何一个端点，而栈顶随着插入和删除而变化。

(3)：用int top 作为栈顶的指针，指明当前栈顶位置。通常：0下标设为栈底，空栈时top=-1;入栈时栈顶指针+1，出栈时栈顶指针-1。

**顺序栈的存储结构如下**：

typedef int DataType;
    
    typedef struct				/*顺序栈的存储结构*/ 
    {
    	DataType data[MAXSIZE];
    	int top;
    }SeqStack;

完整代码如下：

#include <stdio.h>
    #include <stdlib.h>
    
    #define TRUE 1
    #define ERROR 0 
    
    #define MAXSIZE 100
    
    typedef int DataType;
    
    typedef struct				/*顺序栈的存储结构*/ 
    {
    	DataType data[MAXSIZE];
    	int top;
    }SeqStack;
    
    SeqStack *Init_SeqStack();		/*置空栈*/
    
    int Empty_SeqStack(SeqStack *s);	/*判栈空*/
    
    int Push_SeqStack(SeqStack *s,DataType x);		/*入栈*/
    
    DataType Pop_SeqStack(SeqStack *s);		/*出栈*/
    
    DataType Top_SeqStack(SeqStack *s);		/*取栈顶元素*/
    
    void Print_SeqStack(SeqStack *s);	/*打印栈内元素*/ 
    
    int main()
    {
    	SeqStack *s;
    	/*---------------顺序栈的初始化---------------*/ 
    	s = Init_SeqStack();
    	
    	/*----------------顺序栈-入栈-----------------*/ 
    	int x;				/*循环输入顺序栈元素用*/ 
    	DataType top;		/*存放栈顶元素用*/ 
    	printf("请输入顺序栈的数据,按-1结束："); 
    	scanf("%d",&x);
    	while(Push_SeqStack(s,x)){
    		scanf("%d",&x);
    		if(x==-1) break; 
    	}
    	printf("\n入栈后栈内元素如下："); 
    	Print_SeqStack(s);
    	printf("\n");
    	
    	/*-------------顺序栈-取栈顶元素--------------*/ 
    	top=Top_SeqStack(s);
    	printf("\n栈顶元素为：%d.\n\n",top);
    	printf("\n取栈顶后栈内元素如下：");
    	Print_SeqStack(s); 
    	
    	return 0;
    }
    
    SeqStack *Init_SeqStack()		/*置空栈*/
    {
    	SeqStack *s = (SeqStack *)malloc(sizeof(SeqStack));
    	s->top=-1;
    	return s;	/*返回栈顶指针*/ 
    }
    
    int Empty_SeqStack(SeqStack *s)		/*判栈空*/
    {
    	if(s->top==-1) return TRUE;
    	else return ERROR;
    }
    
    int Push_SeqStack(SeqStack *s,DataType x)		/*入栈*/
    {
    	if(s->top == MAXSIZE -1){
    		printf("栈满,不能入栈！\n");
    		return ERROR;
    	}
    	else{
    		s->data[++s->top] = x;
    		return TRUE;
    	}
    }
    
    DataType Pop_SeqStack(SeqStack *s)		/*出栈*/
    {
    	if(Empty_SeqStack(s)){
    		printf("栈空,不能出栈操作!\n");
    		return ERROR;
    	}
    	else{
    		return s->data[s->top--];
    	}
    }
    
    DataType Top_SeqStack(SeqStack *s)		/*取栈顶元素*/
    {
    	if(Empty_SeqStack(s)){
    		printf("栈空,不能出栈操作!\n");
    		return ERROR;
    	}
    	else{
    		 return s->data[s->top];	/*仅是取栈顶元素,不需要s->top--*/ 
    	}
    }
    
    void Print_SeqStack(SeqStack *s)	/*打印栈内元素*/
    {
    	int count=0;  /*充当计数器，当count==s->top结束*/
    	
    	if(Empty_SeqStack(s)){
    		printf("栈空,不能出栈操作!\n");
    		return;
    	}
    	while(count<=s->top){	 /*判断条件不能是count!=s->top,想想为什么？*/ 
    		printf("%d ",s->data[count++]);
    	}
    	printf("\n");
    }

运行结果如下：

![20171211112510160][]

**注意**：这里的取栈顶元素仅仅时查看栈顶元素，并没有top--。

[20171211112510160]: /images/20220604/39310745cbba491d96a29a0292cb44e6.png