C语言：指针四（栈）

大家好，我是不许
今天给大家详细介绍一下数据结构中栈的知识，非常详细。大家快来学习吧！如果觉得写的不错欢迎三连（点赞、收藏加评论）


文章目录

- 一、什么是栈
- 二、栈中的基本运算
- 三、栈的分类
- - 3.1顺序栈
  - 3.2链栈
  - 3.3顺序栈与链栈的区别
- 四、多栈共享技术
- - 4.1什么是多栈共享技术
  - 4.2两个顺序栈共享空间

一、什么是栈

1.1栈的定义：

栈（Stack）作为一种限定性线性表，是将线性表的插入和删除操作限制为仅在表的一端进行，通常将表中允许进行插入、删除操作的一端称为栈顶（Top），因此栈顶的当前位置是动态变化的，它由一个称为栈顶指针的位置指示器来指示。同时，另一端被称为栈底（Bottom）。当栈中没有元素时称为空栈。栈的插入操作被形象地称为进栈或者入栈，删除操作被称为出栈或者退栈。

二、栈中的基本运算

2.1栈的初始化
定义栈s：

SeqStack* s

申请空间：

s = (SeqStack*)malloc(sizeof(SeqStack))

SeqStack* Init_SeqStack(){
    SeqStack* s;
    s = (SeqStack*)malloc(sizeof(SeqStack));
    if(!s){
        printf("空间不足n");
        return NULL;
    }else{
        s->top = -1;
        return s;
    }
}

2.2判断栈是否为空

int Empty_SeqStack(SeqStack* s){ 
    if(s->top == -1)
        return 1;
    else
        return 0;
}

2.3入栈操作

int Push_SeqStack(SeqStack* s, DataType x){
    if(s->top == MAXSIZE - 1)
        return 0;
    else{
        s->top++;
        s->data[s->top] = x;
        return 1;
    }
}

2.4出栈操作

int Pop_SeqStack(SeqStack* s, DataType* x){
    if(Empty_SeqStack(s))
        return 0;
    else{
        *x = s->data[s->top];
        s->top--;
        return 1;
    }
}

2.5整体代码

#include 
#include 
 
#define DataType int
#define MAXSIZE 1024
 
typedef struct{
    DataType data[MAXSIZE];
    int top;
}SeqStack;
 
SeqStack* Init_SeqStack(){  //栈初始化
    SeqStack* s;
    s = (SeqStack*)malloc(sizeof(SeqStack));
    if(!s){
        printf("空间不足n");
        return NULL;
    }else{
        s->top = -1;
        return s;
    }
}
 
int Empty_SeqStack(SeqStack* s){  //判栈空
    if(s->top == -1)
        return 1;
    else
        return 0;
}
 
int Push_SeqStack(SeqStack* s, DataType x){  //入栈
    if(s->top == MAXSIZE - 1)
        return 0;//栈满不能入栈
    else{
        s->top++;
        s->data[s->top] = x;
        return 1;
    }
}
 
int Pop_SeqStack(SeqStack* s, DataType* x){  //出栈
    if(Empty_SeqStack(s))
        return 0;//栈空不能出栈
    else{
        *x = s->data[s->top];
        s->top--;
        return 1;
    }//栈顶元素存入*x，返回
}
 
DataType Top_SeqStack(SeqStack* s){  //取栈顶元素
    if(Empty_SeqStack(s))
        return 0;//栈空
    else
        return s->data[s->top];
}
 
int Print_SeqStack(SeqStack* s){
    int i;
    printf("当前栈中的元素:n");
    for(i = s->top; i >= 0; i--)
        printf("%3d", s->data[i]);
    printf("n");
    return 0;
}
 
int main(){
    SeqStack* L;
    int n, num, m;
    int i;
     
    L = Init_SeqStack();
     
    printf("初始化完成n");
    printf("栈空：%dn", Empty_SeqStack(L));
    printf("请输入入栈元素个数：n");
    scanf("%d", &n);
    printf("请输入要入栈的%d个元素：n", n);
     
    for(i = 0; i < n; i++){
        scanf("%d", &num);
        Push_SeqStack(L, num);
    }
     
    Print_SeqStack(L);
     
    printf("栈顶元素：%dn", Top_SeqStack(L));
    printf("请输入要出栈的元素个数（不能超过%d个）：n", n);
    scanf("%d", &n);
    printf("依次出栈的%d个元素：n", n);
     
    for(i = 0; i < n; i++){
        Pop_SeqStack(L, &m);
        printf("%3d", m);
    }
     
    printf("n");
    Print_SeqStack(L);
    printf("栈顶元素：%dn", Top_SeqStack(L));
     
    return 0;
}

运行结果
初始化完成
栈空：1
请输入入栈元素个数：
3
请输入要入栈的3个元素：
1 2 3
当前栈中的元素:
3 2 1
栈顶元素：3
请输入要出栈的元素个数（不能超过3个）：
2
依次出栈的2个元素：
3 2
当前栈中的元素:
1
栈顶元素：1
请按任意键继续. . .

三、栈的分类 3.1顺序栈

定义

顺序栈是用顺序存储结构实现的栈。

说白了，就是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时由于栈操作的特殊性，还必须附设一个位置指针top（栈顶指针）来动态指示栈顶元素在顺序栈中的位置。通常以top=-1表示空栈。

3.1.1定义结构体

typedef struct
{
	ElemType data[MAXSIZE];
	int top; 
}SeqStack;

3.1.2初始化

Status initStack(SeqStack **stack)
{
	*stack = (SeqStack *)malloc(sizeof(SeqStack));
	(*stack)->top = -1;

	return TRUE;
}

3.1.3进栈操作

Status push(SeqStack *stack, const ElemType e)
{
	if (stack->top == MAXSIZE - 1) // 判断是否栈满
	{
		return FALSE;
	}
	stack->top++; // 栈顶指针加1
	stack->data[stack->top] = e; // 将新插入元素赋值给栈顶空间

	return TRUE;
}

3.1.4出栈操作

Status pop(SeqStack *stack, ElemType *e)
{
	if (stack->top == -1) // 判断是否空栈
		return FALSE;

	*e = stack->data[stack->top];   // 将要删除的栈顶元素赋值给e
	stack->top--;               // 栈顶指针减1

	return TRUE;
}

3.1.5遍历操作

Status traverseStack(SeqStack *stack)
{
	for (int i = 0; i <= stack->top; i++)
		printf("%d ", stack->data[i]);
	printf("n");

	return TRUE;
}

3.1.6清空操作

Status clearStack(SeqStack *stack)
{
	stack->top = -1;

	return TRUE;
}

3.1.7判断是否为空

Status isEmpty(SeqStack *stack)
{
	return stack->top == -1 ? TRUE : FALSE;
}

3.1.8获取栈顶元素

Status getTop(SeqStack *stack, ElemType *e)
{
	if (stack->top == -1)
		return FALSE;
	else
		*e = stack->data[stack->top];

	return TRUE;
}

3.1.9获取栈长度

int getLength(SeqStack *stack)
{
	return stack->top + 1;
}

3.1.10完整代码

#include 
#include  

#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 

typedef int Status;
typedef int ElemType; 


typedef struct
{
	ElemType data[MAXSIZE];
	int top; 
}SeqStack;

// Status initStack(SeqStack **stack); // 初始化栈操作
// Status push(SeqStack *stack, const ElemType e); // 进栈操作
// Status pop(SeqStack *stack, ElemType *e); // 出栈操作
// Status traverseStack(SeqStack *stack); // 遍历栈操作
// Status clearStack(SeqStack *stack); // 清空栈操作
// Status isEmpty(SeqStack *stack); // 判断是否为空
// Status getTop(SeqStack *stack, ElemType *e); // 获得栈顶元素
// int getLength(SeqStack *stack); // 获取栈的长度

// 初始化栈操作
Status initStack(SeqStack **stack)
{
	*stack = (SeqStack *)malloc(sizeof(SeqStack));
	(*stack)->top = -1;

	return TRUE;
}

// 进栈操作
Status push(SeqStack *stack, const ElemType e)
{
	if (stack->top == MAXSIZE - 1) // 判断是否栈满
	{
		return FALSE;
	}
	stack->top++; // 栈顶指针加1
	stack->data[stack->top] = e; // 将新插入元素赋值给栈顶空间

	return TRUE;
}

// 出栈操作
Status pop(SeqStack *stack, ElemType *e)
{
	if (stack->top == -1) // 判断是否空栈
		return FALSE;

	*e = stack->data[stack->top];   // 将要删除的栈顶元素赋值给e
	stack->top--;               // 栈顶指针减1

	return TRUE;
}

// 遍历栈操作
Status traverseStack(SeqStack *stack)
{
	for (int i = 0; i <= stack->top; i++)
		printf("%d ", stack->data[i]);
	printf("n");

	return TRUE;
}

// 清空栈操作
Status clearStack(SeqStack *stack)
{
	stack->top = -1;

	return TRUE;
}

// 判断是否为空
Status isEmpty(SeqStack *stack)
{
	return stack->top == -1 ? TRUE : FALSE;
}

// 获得栈顶元素
Status getTop(SeqStack *stack, ElemType *e)
{
	if (stack->top == -1)
		return FALSE;
	else
		*e = stack->data[stack->top];

	return TRUE;
}

// 获取栈的长度
int getLength(SeqStack *stack)
{
	return stack->top + 1;
}

int main()
{
	// 初始化栈
	SeqStack *stack;
	if (initStack(&stack) == TRUE)
		printf("初始化顺序栈成功！nn");

	// 入栈操作	
	for (int j = 1; j <= 10; j++)
		push(stack, j);
	printf("入栈操作（0-10）!nn");

	// 出栈操作	
	int e;
	pop(stack, &e);
	printf("弹出的栈顶元素e=%dnn", e);

	// 遍历栈
	printf("遍历栈，栈中元素依次为：");
	traverseStack(stack);
	printf("n");

	// 获得栈顶元素
	getTop(stack, &e);
	printf("栈顶元素 e=%d 栈的长度为%dnn", e, getLength(stack));

	// 判断是否为空栈
	printf("栈空否：%d(1:空 0:否)nn", isEmpty(stack));

	// 清空栈
	clearStack(stack);
	printf("清空栈后，栈空否：%d(1:空 0:否)nn", isEmpty(stack));

	return 0;
}

运行结果
初始化顺序栈成功！
入栈操作（0-10）!
弹出的栈顶元素e=10
遍历栈，栈中元素依次为：1 2 3 4 5 6 7 8 9
栈顶元素 e=9 栈的长度为9
栈空否：0(1:空 0:否)
清空栈后，栈空否：1(1:空 0:否)
请按任意键继续. . .

3.2链栈

定义

链栈是采用链表作为存储结构实现的栈。

3.2.1栈的初始化

Status initStack(LinkStack **stack)
{
	// 注意要给链栈分配内存
	*stack = (LinkStack *)malloc(sizeof(LinkStack));
	(*stack)->top = NULL; // 链栈的空其实就是 top=NULL 的时候
	(*stack)->count = 0;

	return TRUE;
}

3.2.2进栈操作

Status push(LinkStack *stack, ElemType e)
{
	StackNode  *s = (StackNode  *)malloc(sizeof(StackNode));
	s->data = e;
	s->next = stack->top; // 把当前的栈顶元素赋值给新结点的直接后继，见图中①
	stack->top = s; // 将新的结点s赋值给栈顶指针，见图中②
	stack->count++;

	return TRUE;
}

3.2.3出栈操作

Status pop(LinkStack *stack, ElemType *e)
{
	StackNode  *p;
	if (isEmpty(stack))
		return FALSE;
	*e = stack->top->data;
	p = stack->top; // p用来存储要删除的栈顶结点，见图中③
	stack->top = stack->top->next; // 使得栈顶指针下移一位，指向后一结点，见图中④
	free(p); // 释放结点p
	stack->count--;

	return TRUE;
}

3.2.4遍历

Status traverseStack(LinkStack *stack)
{
	StackNode  *p;
	p = stack->top;
	while (p)
	{
		printf("%d ", p->data);
		p = p->next;
	}
	printf("n");

	return TRUE;
}

3.2.5清除

Status clearStack(LinkStack *stack)
{
	StackNode  *p;
	StackNode  *q;
	p = stack->top;
	while (p)
	{
		q = p;
		p = p->next;
		free(q);
	}
	stack->count = 0;

	return TRUE;
}

3.2.6判断是否为空

Status isEmpty(LinkStack *stack)
{
	return stack->count == 0 ? TRUE : FALSE;
}

3.2.7获取栈顶元素

Status getTop(LinkStack *stack, ElemType *e)
{
	if (stack->top == NULL)
		return FALSE;
	else
		*e = stack->top->data;

	return TRUE;
}

3.2.8获取栈长度

int getLength(LinkStack *stack)
{
	return stack->count;
}

3.2.9整体代码

#include 
#include  

#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 

typedef int Status;
typedef int ElemType; 


typedef struct StackNode
{
	ElemType data;
	struct StackNode *next;
}StackNode;


typedef struct
{
	StackNode  *top;
	int count;
}LinkStack;

// Status initStack(LinkStack **stack); // 初始化栈操作
// Status push(LinkStack *stack, const ElemType e); // 进栈操作
// Status pop(LinkStack *stack, ElemType *e); // 出栈操作
// Status traverseStack(LinkStack *stack); // 遍历栈操作
// Status clearStack(LinkStack *stack); // 清空栈操作
// Status isEmpty(LinkStack *stack); // 判断是否为空
// Status getTop(LinkStack *stack, ElemType *e); // 获得栈顶元素
// int getLength(LinkStack *stack); // 获取栈的长度

// 初始化栈操作
Status initStack(LinkStack **stack)
{
	// 注意要给链栈分配内存
	*stack = (LinkStack *)malloc(sizeof(LinkStack));
	(*stack)->top = NULL; // 链栈的空其实就是 top=NULL 的时候
	(*stack)->count = 0;

	return TRUE;
}

// 进栈操作
Status push(LinkStack *stack, ElemType e)
{
	StackNode  *s = (StackNode  *)malloc(sizeof(StackNode));
	s->data = e;
	s->next = stack->top; // 把当前的栈顶元素赋值给新结点的直接后继，见图中①
	stack->top = s; // 将新的结点s赋值给栈顶指针，见图中②
	stack->count++;

	return TRUE;
}

// 出栈操作
Status pop(LinkStack *stack, ElemType *e)
{
	StackNode  *p;
	if (isEmpty(stack))
		return FALSE;
	*e = stack->top->data;
	p = stack->top; // p用来存储要删除的栈顶结点，见图中③
	stack->top = stack->top->next; // 使得栈顶指针下移一位，指向后一结点，见图中④
	free(p); // 释放结点p
	stack->count--;

	return TRUE;
}

// 遍历栈操作
Status traverseStack(LinkStack *stack)
{
	StackNode  *p;
	p = stack->top;
	while (p)
	{
		printf("%d ", p->data);
		p = p->next;
	}
	printf("n");

	return TRUE;
}

// 清除栈操作
Status clearStack(LinkStack *stack)
{
	StackNode  *p;
	StackNode  *q;
	p = stack->top;
	while (p)
	{
		q = p;
		p = p->next;
		free(q);
	}
	stack->count = 0;

	return TRUE;
}

// 判断是否为空栈
Status isEmpty(LinkStack *stack)
{
	return stack->count == 0 ? TRUE : FALSE;
}

// 获得栈顶元素
Status getTop(LinkStack *stack, ElemType *e)
{
	if (stack->top == NULL)
		return FALSE;
	else
		*e = stack->top->data;

	return TRUE;
}

// 获得栈的长度
int getLength(LinkStack *stack)
{
	return stack->count;
}

int main()
{
	// 初始化栈
	LinkStack *stack;
	if (initStack(&stack) == TRUE)
		printf("初始化链栈成功！nn");

	// 入栈操作 
	for (int j = 1; j <= 10; j++)
		push(stack, j);
	printf("入栈操作（0-10）!nn");

	// 出栈操作 
	int e;
	pop(stack, &e);
	printf("弹出的栈顶元素e=%dnn", e);

	// 遍历栈
	printf("遍历栈，栈中元素依次为：");
	traverseStack(stack);
	printf("n");

	// 获得栈顶元素
	getTop(stack, &e);
	printf("栈顶元素 e=%d 栈的长度为%dnn", e, getLength(stack));

	// 判断是否为空栈
	printf("栈空否：%d(1:空 0:否)nn", isEmpty(stack));

	// 清空栈
	clearStack(stack);
	printf("清空栈后，栈空否：%d(1:空 0:否)nn", isEmpty(stack));

	return 0;
}

运行结果
初始化链栈成功！
入栈操作（0-10）!
弹出的栈顶元素e=10
遍历栈，栈中元素依次为：9 8 7 6 5 4 3 2 1
栈顶元素 e=9 栈的长度为9
栈空否：0(1:空 0:否)
清空栈后，栈空否：1(1:空 0:否)
请按任意键继续. . .

3.3顺序栈与链栈的区别

1、两者在时间复杂度上是一样的，均为 O(1)。
2、对于空间性能，顺序栈需要事先确定一个固定的长度，可能会存在内存空间浪费的问题，但它的优势是存取时定位很方便，而链栈则要求每个元素都有指针域，这同时也增加了一些内存开销，但对于栈的长度无限制。所以它们的区别和线性表中讨论的一样，如果栈的使用过程中元素变化不可预料，有时很小，有时非常大，那么最好是用链栈，反之，如果它的变化在可控范围内，建议使用顺序栈会更好一些。

四、多栈共享技术 4.1什么是多栈共享技术

栈的应用非常广泛，经常会出现一个程序中需要同时使用多个栈的情况。若使用顺序栈，会因为对栈空间大小难以准确估计，从而产生有的栈溢出、有的栈空间还很空闲的情况。为了解决这个问题，可以让多个栈共享一个足够大的数组空间，通过利用栈的动态特性来使其存储空间互相补充，这就是多栈的共享技术。
在顺序栈的共享技术中，最常用的是两个栈的共享技术，即双端栈。它主要利用了栈的栈底位置不变，而栈顶位置动态变化的特性。

4.2两个顺序栈共享空间

定义共享栈结构

typedef struct {  
    ElemType    data[MaxSize];  
    int         top1;                    
    int         top2;					
}Stack,  *pStack;

初始化

Status init_Stack(pStack S)
{
	S->top1 = -1;
	S->top2 = MaxSize;
	return OK; 
}

进栈

Status push_Stack(pStack S, ElemType e, int stackNumber)
{
	if (S->top1+1 == S->top2)
		return ERROR;
	switch(stackNumber)
	{
		case 1:		
				S->data[++S->top1] = e;		
				break;
		case 2:		
				S->data[--S->top2] = e;		
				break;
	}
	return OK;
}

出栈

Status pop_Stack(pStack S, ElemType *e, int stackNumber)
{
	if (1 == stackNumber)
	{	
		if (-1 == S->top1)		
			return ERROR;
		*e = S->data[S->top1--];
	}
	else if (2 == stackNumber)
	{
		if (MaxSize == S->top2)
			return ERROR;
		*e = S->data[S->top2++];
	}
	return OK;
}

输出

Status dis_pStack(pStack S, int stackNumber)
{
	int i;
	if (1 == stackNumber)
	{
		if (-1 == S->top1)
			return ERROR;

		printf("栈1中的元素为：n");
		for (i=0; i<=S->top1; ++i)
			printf("%d ", S->data[i]);
		printf("n==================================n");
	}
	else if (2 == stackNumber)
	{
		if (MaxSize == S->top2)
			return ERROR;
		printf("栈2中的元素为：n");
		for (i=MaxSize-1; i>=S->top2; --i)	
			printf("%d ", S->data[i]);
		printf("n==================================n");
	}
}

此时，我们定义这个共享栈的总长度为10，也就是说，栈1和栈2总数据为10个

	push_Stack(&S, 1, 1);
	push_Stack(&S, 2, 1);
	push_Stack(&S, 3, 1);
	push_Stack(&S, 4, 1);
	push_Stack(&S, 5, 1);
	push_Stack(&S, 6, 1);
    push_Stack(&S, 7, 1);
    push_Stack(&S, 8, 1);
	pop_Stack(&S, &e, 1);
	push_Stack(&S, 10, 2);
	push_Stack(&S, 9, 2);
	push_Stack(&S, 8, 2);
	dis_pStack(&S, 1);
	dis_pStack(&S, 2);

我们先在第一个栈插入八个数据，运行没问题：

现在，栈2只能插入2个元素，验证：

	push_Stack(&S, 10, 2);
	push_Stack(&S, 9, 2);
	push_Stack(&S, 8, 2);

结果肯定是只能插入10和9：

但如果，我们在插入栈2前先进行栈1出栈：

	pop_Stack(&S, &e, 1);

完整代码

#include 
#include 
#define MaxSize 10 
#define OK      1      
#define ERROR   0      
#define TRUE    1      
#define FALSE   0    
typedef int ElemType;  
typedef int Status;  
typedef struct {  
    ElemType    data[MaxSize];  
    int         top1;                    
    int         top2;					
}Stack,  *pStack;  

Status init_Stack(pStack S)
{
	S->top1 = -1;
	S->top2 = MaxSize;
	return OK; 
}

Status push_Stack(pStack S, ElemType e, int stackNumber)
{
	if (S->top1+1 == S->top2)
		return ERROR;
	switch(stackNumber)
	{
		case 1:		
				S->data[++S->top1] = e;		
				break;
		case 2:		
				S->data[--S->top2] = e;		
				break;
	}
	return OK;
}


Status pop_Stack(pStack S, ElemType *e, int stackNumber)
{
	if (1 == stackNumber)
	{	
		if (-1 == S->top1)		
			return ERROR;
		*e = S->data[S->top1--];
	}
	else if (2 == stackNumber)
	{
		if (MaxSize == S->top2)
			return ERROR;
		*e = S->data[S->top2++];
	}
	return OK;
}


Status dis_pStack(pStack S, int stackNumber)
{
	int i;
	if (1 == stackNumber)
	{
		if (-1 == S->top1)
			return ERROR;

		printf("栈1中的元素为：n");
		for (i=0; i<=S->top1; ++i)
			printf("%d ", S->data[i]);
		printf("n==================================n");
	}
	else if (2 == stackNumber)
	{
		if (MaxSize == S->top2)
			return ERROR;
		printf("栈2中的元素为：n");
		for (i=MaxSize-1; i>=S->top2; --i)	
			printf("%d ", S->data[i]);
		printf("n==================================n");
	}
}

int main()
{
	printf("======共享栈===========nn");
	Stack S;
	ElemType e;
	init_Stack(&S);
	push_Stack(&S, 1, 1);
	push_Stack(&S, 2, 1);
	push_Stack(&S, 3, 1);
	push_Stack(&S, 4, 1);
	push_Stack(&S, 5, 1);
	push_Stack(&S, 6, 1);
    push_Stack(&S, 7, 1);
    push_Stack(&S, 8, 1);
	pop_Stack(&S, &e, 1);
	push_Stack(&S, 10, 2);
	push_Stack(&S, 9, 2);
	push_Stack(&S, 8, 2);
	dis_pStack(&S, 1);
	dis_pStack(&S, 2);
	return 0;
}

C语言：指针四（栈）

C/C++/C#相关栏目本月热门文章