[Data structure] chain stack

definition

Chained stack is a data storage structure, which can be implemented in the form of a singly linked list. The advantage of using a chained stack is that it can overcome the low space utilization of sequential stacks implemented with arrays, but it needs to be used for each stack element. Allocate additional pointer space for storing pointer fields.

Action to be implemented

Push, pop, get the top of the stack, clear, get size, is it empty

implementation code

define stack
First define a singly linked list, and then define the stack. The stack only stores the address of a node in the linked list, which is a bit like the function of the head node in the singly linked list.

struct Node{
	T elem;
	struct Node* next;
}
typedef struct Stack{
	struct Node* first;
}stack;

Initialize the chain stack, that is, set the top node of the stack to NULL

void initStack(Stack *s){
	assert(s!=NULL);
	s->first=NULL;
}

To push into the stack, you need to pass in the elements pushed into the stack, apply for the memory of a new node, put the elements into this node, and then connect the new node. Note that the next node of the new node should point to the top of the stack, and then go to the new node. Set to the top of the stack.

int pushStack(Stack *s,T elem){
	assert(s!=NULL);
	struct Node* node=malloc(sizeof(Node));
	if(node==NULL){
		return FAILURE;
	}
	node->elem=elem;
	node->next=s->first;
	s->first=node;
	return SUCCESS;
}

Pop out the stack, where a pointer to an element is passed in to accept the popped element, and of course a null pointer can also be passed. Record the top of the stack with a node, then set the next node on the top of the stack as the top of the stack, and finally release the recorded original top of the stack.

int popStack(Stack *s,T *pelem){
	assert(s!=NULL);
	if(s->first==NULL){
		return FAILURE;
	}
	if(pelem!=NULL){
		*pelem=s->first->elem;
	}
	struct Node* node=s->first;
	s->first=node->next;
	free(node);
	return SUCCESS;
}

Get the top element of the stack and pass in an element address to accept the top element of the stack.

int peekStack(Stack *s, T *pelem){
	assert(s!=NULL);
	if(pelem!=NULL){
		*pelem=s->first->elem;
	}

	return SUCCESS;
}

To empty the stack, two nodes need to be defined here, one is used to record the current node to be deleted, and the other is used to record the next node to be deleted. Note that in each loop, you must first specify the next (next) and then delete the current node. The loop starts at the top of the stack, replacing each time with the next node that was recorded.

void clearStack(Stack *s){
	assert(s!=NULL);
	struct  Node* node,*next;
	for(node=s->first; node!=NULL; node=next){
		next=node->next;
		free(node);
	}
	s->first=NULL;
}

Get the size of the stack (number of elements), define a size to record the size, traverse from the head node, size+1 each time

size_t sizeStack(Stack *s){
	assert(s!=NULL);
	struct  Node* node=s->first;
	size_t size=0;
	while(node!=NULL){
		size++;
		node=node->next;
	}
	return size;
}

Simple testing framework

#include "list_stack.h"
#include<stdio.h>
#include<stdlib.h>
void push(Stack *s){
	printf("input a elem \n");
	int elem = 0;
	scanf("%d", &elem);
	if(pushStack(s, elem)==SUCCESS){
		printf("input SUCCESS!\n");

	}
	else{
		printf("input FAILED!\n");
	}

}

void pop(Stack *s){
	int elem =0;
	if(popStack(s, &elem)==SUCCESS){
		printf("pop SUCCESS! ,elem is %d\n", elem);

	}
	else{
		printf("pop FAILED!\n");
	}
}

void peek(Stack *s){
	int elem =0;
	if(peekStack(s, &elem)==SUCCESS){
		printf("peek SUCCESS! elem is %d\n",elem);
	}
	else{
		printf("peek FAILED!\n");
	}
}
void empty(Stack *s){
	if(emptyStack(s)){
		printf("Stack is empty!\n");
	}
	else{
		printf("stack is not empty!\n");

	}

}
void size(Stack *s){
	printf("size of stack is %u \n",sizeStack(s));
}
void back(Stack *s){
	clearStack(s);
	exit(0);
}
typedef void(*FUNC)(Stack *s);
struct {
	char *text;
	FUNC func;
}ntfs[]={
	{"push ",push},
	{"pop",pop},
	{"peek ",peek},
	{"empty",empty},
	{"size ",size},
	{"back",back}
};
void menu(void){
	int i=0;
	printf("list_stack test\n");
	
	for( i=0; i<(sizeof(ntfs)/sizeof(ntfs[0])); i++){
		printf("%d. %s\n",i,ntfs[i].text);
	}
	printf(">>>>");
	

}
void run(void){
	Stack s;
	initStack(&s);
	while(1){
		menu();
		 int opt =0;
	scanf("%d",&opt);
	if(opt>=0&&opt<sizeof(ntfs)/sizeof(ntfs[0])){
		ntfs[opt].func(&s);
	}else{
		printf("input FAILED!\n");
	}
	}

}
 int main()
{
	run();

	return 0;
}

Tags: data structure linked list

Posted by roughie on Sun, 22 May 2022 02:28:20 +0300