栈的定义和基本操作的实现

写代码：定义顺序存储的栈（数组实现），数据元素是 int 型
写代码：基于上述定义，实现“出栈、入栈、判空、判满”四个基本操作
写代码：定义链式存储的栈（单链表实现）
写代码：基于上述定义，栈顶在链头，实现“出栈、入栈、判空、判满”四个基本操作
写代码：定义链式存储的栈（双向链表实现）
写代码：基于上述定义，栈顶在链尾，实现“出栈、入栈、判空、判满”四个基本操作
给自己出题：自己动手创造，写一个具有多层小括号、中括号的算数表达式
画图：针对2.1.7的算数表达式，使用栈进行“括号匹配”，画出栈内元素最多的状态
简答：请描述使用栈进行括号匹配的过程

1.定义顺序存储的栈（数组实现），数据元素是 int 型

#include <stdio.h>#define Maxsize 50typedef struct{int data[Maxsize];int top;
}sqStack;

2.实现“出栈、入栈、判空、判满”四个基本操作

#include <stdio.h>#define Maxsize 50typedef struct{int data[Maxsize];int top;
}sqStack;//初始化
void InitStack(sqStack *s){s->top=-1;
} 
//判空
bool  StackEmpty(sqStack &s)
{if(s.top==-1)return true;elsereturn false;}
//判满
bool StackFull(sqStack s)
{if(s.top==Maxsize-1){//TODOreturn true;}else{return false;}
}
//入栈
bool Push (sqStack &s,int e){if(s.top==Maxsize-1){//TODOreturn false;}s.data[++s.top]=e;return true;
} 
//出栈
bool Pop(sqStack &s,int e){if(s.top==-1){//TODOreturn false;}e=s.data[s.top--];return true;
} 
// 打印栈内元素
void printStack(sqStack &s) {if (StackEmpty(s)) {printf("栈为空\n");return;}for (int i = s.top; i >= 0; i--) {printf("%d ", s.data[i]);}printf("\n");
}int main() {sqStack s;InitStack(&s);// 示例操作Push(s, 1);Push(s, 2);Push(s, 3);printStack(s);int value = Pop( s,3);printf("出栈元素: %d\n", value);printStack(s);return 0;
}

3.定义链式存储的栈（单链表实现）

#include <stdio.h>typedef struct Linknode
{int data;struct Linknode *next;
}Linknode;
typedef struct Stack
{Linknode *top;}Stack;

4.栈顶在链头，实现“出栈、入栈、判空、判满”四个基本操作

#include <stdio.h>
#include <stdlib.h>
typedef struct Linknode
{int data;struct Linknode *next;
}Linknode;
typedef struct Stack
{Linknode *top;int size;int maxSize;}Stack;//初始化
void initStack(Stack *stack,int maxSize)
{stack->top=NULL;stack->maxSize=maxSize;stack->size=0;}//判空
bool stackEmpty(Stack stack)
{if(stack.top==NULL){//TODOreturn true;}else{return false;}
} //判满
bool stackFull(Stack *stack)
{if(stack->size =stack->maxSize){return true;} else{return false;}}
//入栈
void push(Stack *stack ,int data)
{Linknode *newNode=(Linknode*)malloc(sizeof(Linknode));newNode->data=data;newNode->next=stack->top;//新节点指向旧的栈顶stack->top=	newNode;//更新栈顶指针} 
//出栈
bool pop(Stack *stack)
{if(stackEmpty(*stack)){//TODOprintf("栈已空，无法进行出栈操作。\n");return false;}Linknode*temp=stack->top;int data=stack->top->data;stack->top=stack->top->next;//更新栈顶指针free(temp) ;return true ;} void printStack(Stack stack) {Linknode* current = stack.top;while (current != NULL) {printf("%d ", current->data);current = current->next;}printf("\n");
}int main() {Stack stack;initStack(&stack,50);push(&stack, 1);push(&stack, 2);push(&stack, 3);printStack(stack); // 输出: 3 2 1int popped = pop(&stack);printf("出栈元素: %d\n", popped);printStack(stack); // 输出: 2 1return 0;
}

5.定义链式存储的栈（双向链表实现）

#include <stdio.h>
#include <stdlib.h>struct Node {int data;struct Node* next;struct Node* prev;
};// 定义栈结构
struct Stack {struct Node* top; // 栈顶指针，链尾
};

6.基于上述定义，栈顶在链尾，实现“出栈、入栈、判空、判满”四个基本操作

#include <stdio.h>
#include <stdlib.h>struct Node {int data;struct Node* next;struct Node* prev;
};// 定义栈结构
struct Stack {struct Node* top; // 栈顶指针，链尾
};// 初始化
void initStack(struct Stack* stack) {stack->top = NULL;
}// 入栈
void push(struct Stack* stack, int value) {struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));if (newNode == NULL) {printf("内存分配失败，无法执行入栈操作\n");return;}newNode->data = value;newNode->next = NULL;if (stack->top == NULL) {newNode->prev = NULL;stack->top = newNode;} else {newNode->prev = stack->top;stack->top->next = newNode;stack->top = newNode;}
}// 出栈
int pop(struct Stack* stack) {if (stack->top == NULL) {printf("栈为空，无法执行出栈操作\n");return -1; // 返回一个错误值}struct Node* temp = stack->top;int poppedValue = temp->data;if (stack->top->prev != NULL) {stack->top = stack->top->prev;stack->top->next = NULL;} else {stack->top = NULL;}free(temp);return poppedValue;
}// 判空
int isEmpty(struct Stack* stack) {return (stack->top == NULL);
}// 判满
//对于链式存储的栈，通常不会满，所以返回0表示不满
int isFull(struct Stack* stack) {return 0;
}void freeStack(struct Stack* stack) {while (stack->top != NULL) {struct Node* temp = stack->top;stack->top = temp->prev;free(temp);}
}int main() {struct Stack stack;initStack(&stack);push(&stack, 1);push(&stack, 2);push(&stack, 3);printf("出栈操作: %d\n", pop(&stack));printf("栈是否为空: %s\n", isEmpty(&stack) ? "是" : "否");printf("栈是否满: %s\n", isFull(&stack) ? "是" : "否");freeStack(&stack);return 0;
}