用双向链表实现栈（C）

目录

一.结构定义：

二.结构操作

三.测试代码

四.运用

---

一.结构定义：

1.定义节点，包括一个前驱指针，一个后继指针，一个数据域

2.定义栈，包括一个栈顶指针，指向栈顶元素；一个栈所含元素个数size

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
typedef int 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);

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);

具体实现如下：

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);
	}
}

三.测试代码

测试代码如下：

 测试结果如下：

四.运用

解LeetCode20.有效的括号：

 创建一个栈，遇到左括号入栈，遇到相同右括号出栈。

 代码实现：

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);
	}
}
//以上是栈结构和操作定义。
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)){//若第一个元素是右括号
            StackDestroy(&st);
            return false;     
          }
          if((StackTop(&st)=='('&&*s==')')||(StackTop(&st)=='['&&*s==']')||(StackTop(&st)=='{'&&*s=='}')){
              StackPop(&st);//出栈
          }else{
              StackDestroy(&st);
              return false;
          }
      }
      s++;
   }
   if((&st)->top!=NULL){//若栈顶还有元素
        StackDestroy(&st);
        return false;
   }
   StackDestroy(&st);
   return true;
}