【数据结构】11 堆栈（顺序存储和链式存储）-堆栈的实现

时间：2024-02-17 13:54:34

顺序栈的实现

由一个一维数组和一个记录栈顶元素位置的变量组成，另外还有一个记录堆栈最大容量的变量MaxSize。
习惯将栈底放在数组下标小的那端，栈顶位置用一个整型变量Top记录当前栈顶元素的下标值。当Top指向-1时，表示空栈；当Top指向MaxSize-1时表示栈满。
顺序栈类型Stack表示如下：

typedef int ElementType;
typedef int Position;
typedef struct SNode* PtrToSNode;

struct SNode {
	ElementType* Data;
	Position Top;
	int MaxSize;

};

typedef PtrToSNode Stack;

顺序栈的创建

Stack CreateStack(int MaxSize) {
	Stack S = (Stack)malloc(sizeof(SNode) * 1);
	S->Data = (ElementType * )malloc(sizeof(ElementType) * MaxSize);
	S->Top = -1;
	S->MaxSize = MaxSize;
	return S;
}

进栈


bool IsFull(Stack S) {
	if (S->Top == S->MaxSize - 1) {
		return true;
	}
	return false;
}

bool Push(Stack S, ElementType X) {
	if (IsFull(S)) {
		printf("The Stack is full!\n");
		return false;
	}
	(S->Top)++;

	S->Data[S->Top] = X;
	return true;

}

出栈

bool IsEmpty(Stack S) {
	if (S->Top == -1) {
		return true;
	}
	return false;
}

ElementType Pop(Stack S) {
	if (IsEmpty(S)) {
		printf("The Stack is empty!\n");
		return -1;
	}
	int temp = S->Data[S->Top];
	(S->Top)--;
	return temp;


}

完整代码

# include <stdio.h>
#include < stdlib.h>

typedef int ElementType;
typedef int Position;
typedef struct SNode* PtrToSNode;

struct SNode {
	ElementType* Data;
	Position Top;
	int MaxSize;

};

typedef PtrToSNode Stack;


Stack CreateStack(int MaxSize) {
	Stack S = (Stack)malloc(sizeof(SNode) * 1);
	S->Data = (ElementType * )malloc(sizeof(ElementType) * MaxSize);
	S->Top = -1;
	S->MaxSize = MaxSize;
	return S;
}

bool IsFull(Stack S) {
	if (S->Top == S->MaxSize - 1) {
		return true;
	}
	return false;
}

bool Push(Stack S, ElementType X) {
	if (IsFull(S)) {
		printf("The Stack is full!\n");
		return false;
	}
	/*(S->Top)++;

	S->Data[S->Top] = X;*/
	S->Data[++(S->Top)] = X;
	return true;

}

bool IsEmpty(Stack S) {
	if (S->Top == -1) {
		return true;
	}
	return false;
}

ElementType Pop(Stack S) {
	if (IsEmpty(S)) {
		printf("The Stack is empty!\n");
		return -1;
	}
	/*int temp = S->Data[S->Top];
	(S->Top)--;
	return temp;*/
	return (S->Data[(S->Top)--]);


}

void print_s(Stack S) {
	int t = S->Top;
	while (t != -1) {
		printf("Node: %d\n", S->Data[t]);
		(t)--;
	}
}

int main() {
	Stack S = NULL;
	int MaxSize = 10;
	S = CreateStack(MaxSize);
	ElementType X;
	int N;
	scanf_s("%d", &N);
	while (N--) {
		scanf_s("%d", &X);
		if (Push(S, X) == false) {
			printf("Push error!\n");
		}

	}

	print_s(S);

	int out = Pop(S);
	printf("out : %d\n", out);
	print_s(S);
	

}

用一个数组实现两个堆栈

在这里插入图片描述

结构体
typedef struct DSNode* DStack;
struct DSNode
{
	ElementType* Data;
	Position Top1;
	Position Top2;
	int MaxSize;
};
创建
DStack CreateDStack(int MaxSize) {
	DStack S = (DStack)malloc(sizeof(DSNode) * 1);
	S->Data = (ElementType*)malloc(sizeof(ElementType) * MaxSize);
	S->Top2 = -1;
	S->Top1 = MaxSize;
	S->MaxSize = MaxSize;
	return S;
}
入栈

bool PushX(DStack S, ElementType X, int Tag) {
	if (S->Top1 - S->Top2 == 1) {
		printf("the stack is full!\n");
		return false;
	}
	if (Tag == 1) {
		(S->Top1)--;
		S->Data[S->Top1] = X;
	}
	else{
		(S->Top2)++;
		S->Data[S->Top2] = X;
	}
	return true;
}
出栈

ElementType PopX(DStack S, int Tag) {

	if (Tag == 1) {
		if (S->Top1 == S->MaxSize) {
			printf("the stack1 is empty!\n");
			return -1;
		}
		else {
			return S->Data[(S->Top1)++];
		}
		
	}
	else {
		if (S->Top2 == -1) {
			printf("the stack2 is empty!\n");
			return -1;
		}
		else {
			return S->Data[(S->Top2)--];
		}
	}


}
完整代码
# include <stdio.h>
#include < stdlib.h>

typedef int ElementType;
typedef int Position;

typedef struct DSNode* DStack;
struct DSNode
{
	ElementType* Data;
	Position Top1;
	Position Top2;
	int MaxSize;
};

DStack CreateDStack(int MaxSize) {
	DStack S = (DStack)malloc(sizeof(DSNode) * 1);
	S->Data = (ElementType*)malloc(sizeof(ElementType) * MaxSize);
	S->Top2 = -1;
	S->Top1 = MaxSize;
	S->MaxSize = MaxSize;
	return S;
}

bool PushX(DStack S, ElementType X, int Tag) {
	if (S->Top1 - S->Top2 == 1) {
		printf("the stack is full!\n");
		return false;
	}
	if (Tag == 1) {
		(S->Top1)--;
		S->Data[S->Top1] = X;
	}
	else{
		(S->Top2)++;
		S->Data[S->Top2] = X;
	}
	return true;
}

ElementType PopX(DStack S, int Tag) {

	if (Tag == 1) {
		if (S->Top1 == S->MaxSize) {
			printf("the stack1 is empty!\n");
			return -1;
		}
		else {
			return S->Data[(S->Top1)++];
		}
		
	}
	else {
		if (S->Top2 == -1) {
			printf("the stack2 is empty!\n");
			return -1;
		}
		else {
			return S->Data[(S->Top2)--];
		}
	}


}

void print_ds(DStack S) {
	printf("print S1:\n");
	int t = S->Top1;
	while (t != S->MaxSize) {
		printf("Node: %d\n", S->Data[t]);
		(t)++;
	}

	printf("print S2:\n");
	t = S->Top2;
	while (t != -1) {
		printf("Node: %d\n", S->Data[t]);
		(t)--;
	}
}

int main() {
	
	int MAXSIZE = 10;
	DStack S = CreateDStack(MAXSIZE);
	ElementType X;
	int N;
	scanf_s("%d", &N);
	while (N--) {
		scanf_s("%d", &X);
		if (PushX(S, X, 1) == false) {
			printf("Push error!\n");
		}
		if (PushX(S, X, 2) == false) {
			printf("Push error!\n");
		}

	}

	print_ds(S);
	int out = PopX(S,1);
	printf("out : %d\n", out);
	print_ds(S);


}

链式存储的实现

栈顶指针Top就是链表的栈顶结点，栈中的其他结点通过他们的指针Next链接起来，栈底结点的Next为NULL

数据结构

typedef int ElementType;
typedef struct SNode* PtrToSNode;


struct SNode {
	ElementType Data;
	PtrToSNode Next;
};

typedef PtrToSNode Stack;

创建


Stack CreateStack(Stack S) {
	S = (Stack)malloc(sizeof(SNode) * 1);
	S->Next = NULL;
	return S;
}

入栈


bool Push(Stack S, ElementType X) {
	Stack temp = (Stack)malloc(sizeof(SNode));
	temp->Data = X;
	temp->Next = S->Next;
	S->Next = temp;
	return true;

	
	
}

出栈

ElementType Pop(Stack S) {
	if (S->Next == NULL) {
		printf("the stack is empty!\n");
		return -1;
	}
	ElementType re = S->Next->Data;
	S->Next = S->Next->Next;
	return re;

}

完整代码

# include <stdio.h>
#include < stdlib.h>

typedef int ElementType;
typedef struct SNode* PtrToSNode;


struct SNode {
	ElementType Data;
	PtrToSNode Next;
};

typedef PtrToSNode Stack;

Stack CreateStack(Stack S) {
	S = (Stack)malloc(sizeof(SNode) * 1);
	S->Next = NULL;
	return S;
}


bool Push(Stack S, ElementType X) {
	Stack temp = (Stack)malloc(sizeof(SNode));
	temp->Data = X;
	temp->Next = S->Next;
	S->Next = temp;
	return true;

	
	
}


ElementType Pop(Stack S) {
	if (S->Next == NULL) {
		printf("the stack is empty!\n");
		return -1;
	}
	ElementType re = S->Next->Data;
	S->Next = S->Next->Next;
	return re;

}

void prints(Stack S) {
	Stack t = S->Next;
	while (t != NULL) {
		printf("Node: %d\n", t->Data);
		t = t->Next;
	}
}

int main() {
	Stack S = NULL;
	S = CreateStack(S);
	ElementType X;
	int N;
	scanf_s("%d", &N);
	while (N--) {
		scanf_s("%d", &X);
		if (Push(S, X) == false) {
			printf("Push error!\n");
		}


	}

	prints(S);

	ElementType out = Pop(S);
	printf("out : %d\n", out);
	prints(S);


}

相关文章