Using bidirectional linked list to realize stack (c)

Catalog

One . Structure definition ：

Two . Structure operation

3、 ... and . Test code

Four . Application

---

One . Structure definition ：

1. Define the node , Including a precursor pointer , A successor pointer , A data field

2. Define stack , Including a stack top pointer , Point to the top element of the stack ; The number of elements in a stack size

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
typedef int STDataType;
// Define each node 
typedef struct StackNode {
    struct Stack* next;
    struct Stack* prev;
    STDataType data;
}STNode;
// Define a stack 
typedef struct Stack {
    STNode* top;
    int size;
}Stack;

Two . Structure operation

Contains initialization , Push , Out of the stack , Look at the top of the stack elements , Destroy the stack , Air judgment and other operations .

void StackInit(Stack* ps);

void StackDestroy(Stack* ps);

void StackPush(Stack* ps, STDataType x);

void StackPop(Stack* ps);

STDataType StackTop(Stack* ps);

bool StackEmpty(Stack* ps);

int StackSize(Stack* ps);

The specific implementation is as follows ：

void StackInit(Stack* ps) {
	assert(ps);
	ps->size = 0;
	ps->top = NULL;
}
void StackPush(Stack* ps, STDataType x) {
	assert(ps);
	STNode*newnode= (STNode*)malloc(sizeof(STNode));
	assert(newnode);
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	if (ps->top == NULL)ps->top = newnode;
	else {
		ps->top->next = newnode;
		newnode->prev = ps->top;
		ps->top = newnode;
	}
	ps->size++;
}
void StackPop(Stack* ps) {
	assert(ps&&ps->top);
	if (ps->top->prev== NULL) {
		free(ps->top);
		ps->top = NULL;
	}
	else {
		STNode* prev = ps->top->prev;
		free(ps->top); 
		ps->top = prev;
	}
	ps->size--;
}
STDataType StackTop(Stack* ps) {
	assert(ps && ps->top);
	return ps->top->data;
}
bool StackEmpty(Stack* ps){
	assert(ps);
	return ps->top == NULL;
}
int StackSize(Stack* ps) {
	return ps->size;
}
void StackDestroy(Stack* ps) {
	assert(ps);
	while (ps->top) {
		StackPop(ps);
	}
}

3、 ... and . Test code

The test code is as follows ：

  The test results are as follows ：

Four . Application

Explain LeetCode20. Valid parenthesis ：

  Create a stack , Encountered left parenthesis in stack , Encounter the same right parenthesis out of the stack .

  Code implementation ：

typedef char STDataType;
typedef struct StackNode {
    struct Stack* next;
    struct Stack* prev;
    STDataType data;
}STNode;
typedef struct Stack {
    STNode* top;
    int size;
}Stack;
void StackInit(Stack* ps) {
	assert(ps);
	ps->size = 0;
	ps->top = NULL;
}
void StackPush(Stack* ps, STDataType x) {
	assert(ps);
	STNode*newnode= (STNode*)malloc(sizeof(STNode));
	assert(newnode);
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	if (ps->top == NULL)ps->top = newnode;
	else {
		ps->top->next = newnode;
		newnode->prev = ps->top;
		ps->top = newnode;
	}
	ps->size++;
}
void StackPop(Stack* ps) {
	assert(ps&&ps->top);
	if (ps->top->prev== NULL) {
		free(ps->top);
		ps->top = NULL;
	}
	else {
		STNode* prev = ps->top->prev;
		free(ps->top); 
		ps->top = prev;
	}
	ps->size--;
}
STDataType StackTop(Stack* ps) {
	assert(ps && ps->top);
	return ps->top->data;
}
bool StackEmpty(Stack* ps){
	assert(ps);
	return ps->top == NULL;
}
int StackSize(Stack* ps) {
	return ps->size;
}
void StackDestroy(Stack* ps) {
	assert(ps);
	while (ps->top) {
		StackPop(ps);
	}
}
// The above is the stack structure and operation definition .
bool isValid(char * s){
    if(s==NULL)return false;
    Stack st;
    StackInit(&st);
   while(*s!='\0'){
      if(*s=='('||*s=='{'||*s=='['){
          StackPush(&st,*s);
      }else{
          if(StackEmpty(&st)){// If first element is a right parenthesis 
            StackDestroy(&st);
            return false;     
          }
          if((StackTop(&st)=='('&&*s==')')||(StackTop(&st)=='['&&*s==']')||(StackTop(&st)=='{'&&*s=='}')){
              StackPop(&st);// Out of the stack 
          }else{
              StackDestroy(&st);
              return false;
          }
      }
      s++;
   }
   if((&st)->top!=NULL){// If there are elements at the top of the stack 
        StackDestroy(&st);
        return false;
   }
   StackDestroy(&st);
   return true;
}