数据结构复习1.1, 链表栈

实现

栈的定义以不用多说。链表栈的实现主要是依靠头插法将元素插入链表。尾插法也可以就是有点麻烦。

头插法实现栈

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

//written by 真的木有鱼丸啊


//定义一个链表
typedef struct node
{
	int data;
	struct node* next;
}List;

//定义一个栈
typedef struct
{
	int Top;
	List* list;
}Stack;


void __Stack_init(Stack *S)//头节点初始化
{
	if (S == NULL)
	{
		printf("head is NULL\n");
		assert(0);
	}
	else
	{
		Stack* temp = S;
		temp->Top = -1;
		temp->list->next = NULL;
		temp->list->data = -1;
	}
}

//因为头插法是逆序插入的刚好和栈的定义和相同
void __Stack_push(Stack* S, int num)
{
	if (S == NULL)
	{
		printf("Stack pointer is NULL\n");
		assert(0);
	}
	else
	{
		Stack* temp = S;
		temp->Top++;
		List* p = temp->list;
		List* new_node = (List*)malloc(sizeof(List));
		new_node->data = num;
		new_node->next = p->next;
		p->next = new_node;
	}
}

//删除头节点后方的节点就可以了
int __Stack_pop(Stack* S)
{
	if (S == NULL)
	{
		printf("Stack pointer is NULL\n");
		assert(0);
	}
	else if (S->Top == -1)
	{
		printf("Stack is empty");
		assert(0);
	}
	else
	{
		int data;
		Stack* temp = S;
		List* p = temp->list;//将p指向头节点
		List* q = p->next;//将q指向头节点后方节点
		data = q->data;
		p->next = q->next;//将头节点连至下一个节点
		free(q);
		return data;
	}
}

void __Print_stack(Stack* S)
{
	if (S == NULL)
	{
		printf("Stack pointer is NULL\n");
		assert(0);
	}
	else if (S->Top == -1)
	{
		printf("Stack is empty");
		assert(0);
	}
	else
	{
		List* temp = S->list->next;
		while (temp != NULL)
		{
			printf("%d ", temp->data);
			temp = temp->next;
		}
		printf("\n");
	}
}

void __Stack_destory(Stack* S)
{
	free(S->list);
	free(S);
}
int main()
{
	Stack* stack = (Stack*)malloc(sizeof(Stack));
	stack->list = (List*)malloc(sizeof(Stack));

	__Stack_init(stack);

	for (int i = 0; i < 10; i++)
	{
		__Stack_push(stack, i);
	}

	printf("print stack: ");
	__Print_stack(stack);

	printf("stack pop: ");
	List* temp = stack->list->next;
	for (int i = 0; i < 10; i++)
	{
		printf("%d ", __Stack_pop(stack));
	}

	__Stack_destory(stack);

}

尾插法实现

这个代码比较有历史，所以比较乱。

#include <stdio.h>
#include <time.h>

//单链表实现stack
//written by 真的木有米线啊


typedef struct node
{
	int top;
	int data;
	struct ndoe* next;
}stack;


void Stack_init(stack *Stack)
{
	Stack->top = -1;
	Stack->next = NULL;
}

void stack_destory(stack *Stack)
{
	free(Stack);
}

int Stack_empty(stack *Stack)
{
	stack* S = Stack;
	if (S != NULL)
	{
		while (S->next != NULL)
		{
			S = S->next;
		}

		if (S->top == -1)
			return 1;
		else
			return 0;
	}
}

void Stack_push(stack *Stack,int element)
{

	if(Stack == NULL)
	{
		return;
	}

	stack *S = Stack;


	while (S->next != NULL)
	{
		S = S->next;
	}

	stack* new_node = (stack*)malloc(sizeof(stack));
	new_node->top= S->top+1;
	new_node->data = element;
	new_node->next = NULL;

	S->next = new_node;
}

int Stack_pop(stack* Stack)
{
	if (Stack_empty(Stack))
	{
		printf("Stack empty\n");
		return -1;//can not pop
	}
	else
	{
		stack* S = Stack->next;
		stack* slow = Stack;
		while (S->next != NULL)
		{
			S = S->next;
			slow = slow -> next;
		}

		int element = S->data;
		slow->next = NULL;
		free(S);
		return element;
	}
}


int main()
{
	stack* Stack = (stack*)malloc(sizeof(stack));
	Stack_init(Stack);

	for (int i = 0; i < 10; i++)
	{
		Stack_push(Stack,i);
	}

	int ind = 0;
	stack* index = Stack;
	while (index->next != NULL)
	{
		index = index->next;
		ind++;
	}
	
	for (int i = 0; i < ind; i++)
	{
		printf("%d ", Stack_pop(Stack));
	}

	printf("\n");
}