526互联

数据结构与算法---------2

发布时间 2023-12-08 19:19:02作者: lwj1239

栈

栈是一个具有一定操作约束的线性表，只能在一端(栈顶，top)做插入和删除。

栈的顺序实现

//栈的顺序实现 
#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <stdbool.h>
#define u unsigned
#define ll long long
#define sc scanf
#define pr printf 
#define fr(i, j, n) for (int i = j; i < n; i++)
#define ERROR -1//返回-1代表出错 

typedef int ELEMENT;//元素类型为int类型，抽象的艺术 

typedef struct SNode {//定义栈的数据类型 
	ELEMENT *data;//使用数组实现，当然也可以用指针来开辟 
	int size;//栈中元素的个数 
	int MaxSize;
}SNode,*Stack;


Stack CreateStack(int MaxSize);//创建一个最大大小为MaxSize的栈 
bool isFull(Stack ptrS);//判断栈是不是满了不能再存放了 
void push(Stack ptrS, ELEMENT item);//把元素ITEM压入栈中 
ELEMENT pop(Stack ptrS);//把栈顶的元素弹出 
bool empty(Stack ptrS);//判断栈是不是空栈 
int size(Stack ptrS);//返回栈中元素的个数 
ELEMENT peek(Stack ptrS);//返回栈顶元素，但不弹出栈顶元素 
void FreeStack(Stack ptrS);//释放ptrS所指向的空间 

int main(int argc, char* argv[])
{
	Stack a;
	
	a = CreateStack(3);
	
	push(a, 1);
	push(a, 2);
	
	pr("%d\n", pop(a));
	pr("%d\n", peek(a));
	pr("size = %d\n", size(a));
	
	FreeStack(a);
	
	return 0;
}

Stack CreateStack(int MaxSize)
{
	Stack s = (Stack)malloc(sizeof(SNode));//开辟一个栈空间 
	
	s -> MaxSize = MaxSize; 
	s -> size = 0;//让栈的大小为0 
	s -> data = (ELEMENT*)malloc(sizeof(ELEMENT) * MaxSize);//开辟空间用来存放元素 
	
	return s;
}
bool isFull(Stack ptrS) { 
	return ptrS -> size == ptrS -> MaxSize;//如果栈中的元素等于栈能容纳的最大元素代表栈满了 
}

void push(Stack ptrS, ELEMENT item) {//用指针可以改变ptrS所指向的栈,因为要改变所对应的栈顶位置 
	if (isFull(ptrS)) {//如果栈满了就不能进行压栈了 
		pr("栈已经满了\n");
		return ; 
	}
	else {
		ptrS -> data[ptrS -> size++] = item;//就是先把item压入到栈里面去，size的大小再加一 
	}
}

ELEMENT pop(Stack ptrS) {//用指针可以改变ptrS所指向的栈,因为要改变所对应的栈顶位置 
	if (empty(ptrS)) {//如果栈为空，那么没有元素可以弹出，所以是犯法操作，返回一个特定的值 
		pr("栈已经空了\n");
		return ERROR; 
	}
	
	return ptrS -> data[--ptrS -> size];//是先减一，再弹出栈顶元素 
}

bool empty(Stack ptrS) {
	return ptrS -> size == 0;//如果栈里面没有元素，那么栈就是空的
}

int size(Stack ptrS) {
	return ptrS -> size;//直接返回size
}
ELEMENT peek(Stack ptrS)
{
	if (empty(ptrS)) {// 
		pr("栈已经空了\n");
		return ERROR; 
	}
	
	ELEMENT ans = pop(ptrS);//使用pop函数 
	
	push(ptrS, ans);//因为已经弹出ans元素，所以在压入栈中 
	
	return ans;
}
void FreeStack(Stack ptrS)
{
	free(ptrS -> data);//先释放数据域的内存空间 
	free(ptrS);//再释放ptrS所指向的空间 
}

栈的链式实现

//栈的链式实现 
#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <stdbool.h>
#define u unsigned
#define ll long long
#define sc scanf
#define pr printf 
#define fr(i, j, n) for (int i = j; i < n; i++)
#define ERROR -1

typedef int ELEMENT; 

typedef struct SNode{//元素结构 
	ELEMENT data;
	struct SNode* next; 
}SNode;

typedef struct stack {//栈的结构 
	SNode* head;//元素的链表 
	int size;//栈中元素个数 
}stack;

typedef struct stack* Stack;

Stack creatStack(void);//创建一个栈 
bool empty(Stack s);//判断栈是不是一个空栈 
void push(Stack s, ELEMENT item);//把元素item压入到栈里面 
ELEMENT pop(Stack s);//弹出栈顶元素 
ELEMENT peek(Stack s);//返回栈顶元素但不弹出 
int size(Stack s);//返回栈中元素个数 
void FreeStack(Stack s);//释放掉栈的空间 

int main(int argc, char* argv[])
{
	Stack s = creatStack();
	
	push(s, 1);
	push(s, 2);
	push(s, 3);
	
	pr("size = %d\n", size(s));
	pr("%d\n", peek(s));
	pr("%d\n", pop(s));
	pr("%d\n", pop(s));
	pr("%d\n", empty(s));
	pr("%d\n", pop(s));

	return 0;
}
Stack creatStack()
{
	Stack head = (Stack)malloc(sizeof(stack));//创建一个栈 
	
	head -> head = (SNode*)malloc(sizeof(SNode));//创建一个虚拟头节点 
	head -> size = 0;//让栈的元素大小为0 
	head -> head -> next = NULL;//让虚拟头节点的next指向NULL 
	
	return head; 
}

bool empty(Stack s) {
	return size == 0;
}
void push(Stack s, ELEMENT item)
{
	SNode* t = (SNode*)malloc(sizeof(SNode));//创建一个元素节点 
	
	if (t == NULL) {
		pr("内存空间不足\n");
		return ;
	}
	
	t -> data = item;//把item赋值给元素节点t 
	t -> next = s -> head -> next;//让新的元素的next指向虚拟头节点的next 
	s -> head -> next = t;//再让虚拟头节点的next指向t，就完成了压栈 
	s -> size++;//有元素压栈，所以size加1 
}
ELEMENT pop(Stack s)
{
	if (empty(s)) {
		pr("栈已经空了\n");
		return ERROR;
	}
	
	ELEMENT ans = s -> head -> next -> data;//取出虚拟头节点netx的元素指赋值给ans 
	
	SNode* t = s -> head -> next;//让t指向虚拟头节点的next 

	s -> head -> next = t -> next;//让虚拟头节点的next指向虚拟头节点的netx的next，也就是删除虚拟头节点的next 
	
	free(t);//因为从链表中已经断了，所以直接free 
	
	return ans;
}
ELEMENT peek(Stack s)
{
	if (empty(s)) {
		pr("栈已经空了\n");
		return ERROR;
	}
	
	ELEMENT ans = pop(s);//复用pop函数 

	push(s, ans);//因为已经弹出元素ans，所以在压入栈中 

	return ans;
}
int size(Stack s)
{
	return s -> size;//返回栈中元素的个数 
}
void FreeStack(Stack s)
{
	SNode* p = NULL;
	SNode* q = s -> head;
	
	while(q) {//删除链表 
		p = q;
		q = q -> next;
		free(p);
	}
	
	free(s);//释放整个栈 
}

用栈实现队列

力控题目链接

解题思路

  1. 栈是一种先进后出的结构，而队列是一种先进先出的结构，因此想要用栈来实现，就必须要再把顺序反过来。所以还需要另一个栈，先出栈再压栈，再出栈，就能让顺序颠倒了。
  2. 进队的操作用一个叫inStack的栈来模拟，出队操作用一个叫outStack的栈来模拟。
  3. 进队只需要把元素压入inStack栈就可以了
  4. 而出队操作，需要先把inStack的所有元素压入outStack栈中，因为只有这样才能保证出队的顺序是符合正确队列出队的顺序，如果不压入全部元素必定会导致，后出队的先出队了，栈底元素一定是要先出队的，而不压入outStack的话，就会导致后进队的元素先出队了，就不符合队列的要求了。
  5. 如果outStack为NULL的话，就把inStack的元素全部压入到outStack栈中，再弹出outStack的栈顶元素
  6. 如果不为NULL，就直接弹出outStack的栈顶元素
  7. 注意只有当两个栈都为空时，队列才为空
#define pr printf
#define ERROR -1

typedef int ELEMENT;//元素类型为int类型，抽象的艺术 

typedef struct SNode {//定义栈的数据类型 
	ELEMENT *data;//使用数组实现，当然也可以用指针来开辟 
	int size;//栈中元素的个数 
	int MaxSize;
}SNode,*Stack;

Stack CreateStack(int MaxSize);//创建一个最大大小为MaxSize的栈 
bool isFull(Stack ptrS);//判断栈是不是满了不能再存放了 
void push(Stack ptrS, ELEMENT item);//把元素ITEM压入栈中 
ELEMENT pop(Stack ptrS);//把栈顶的元素弹出 
bool empty(Stack ptrS);//判断栈是不是空栈 
int size(Stack ptrS);//返回栈中元素的个数 
ELEMENT peek(Stack ptrS);//返回栈顶元素，但不弹出栈顶元素 
void FreeStack(Stack ptrS);//释放ptrS所指向的空间 

Stack CreateStack(int MaxSize)
{
	Stack s = (Stack)malloc(sizeof(SNode));//开辟一个栈空间 
	
	s -> MaxSize = MaxSize; 
	s -> size = 0;//让栈的大小为0 
	s -> data = (ELEMENT*)malloc(sizeof(ELEMENT) * MaxSize);//开辟空间用来存放元素 
	
	return s;
}
bool isFull(Stack ptrS) { 
	return ptrS -> size == ptrS -> MaxSize;//如果栈中的元素等于栈能容纳的最大元素代表栈满了 
}

void push(Stack ptrS, ELEMENT item) {//用指针可以改变ptrS所指向的栈,因为要改变所对应的栈顶位置 
	if (isFull(ptrS)) {//如果栈满了就不能进行压栈了 
		pr("栈已经满了\n");
		return ; 
	}
	else {
		ptrS -> data[ptrS -> size++] = item;//就是先把item压入到栈里面去，size的大小再加一 
	}
}

ELEMENT pop(Stack ptrS) {//用指针可以改变ptrS所指向的栈,因为要改变所对应的栈顶位置 
	if (empty(ptrS)) {//如果栈为空，那么没有元素可以弹出，所以是犯法操作，返回一个特定的值 
		pr("栈已经空了\n");
		return ERROR; 
	}
	
	return ptrS -> data[--ptrS -> size];//是先减一，再弹出栈顶元素 
}

bool empty(Stack ptrS) {
	return ptrS -> size == 0;//如果栈里面没有元素，那么栈就是空的
}

int size(Stack ptrS) {
	return ptrS -> size;//直接返回size
}
ELEMENT peek(Stack ptrS)
{
	if (empty(ptrS)) {// 
		pr("栈已经空了\n");
		return ERROR; 
	}
	
	ELEMENT ans = pop(ptrS);//使用pop函数 
	
	push(ptrS, ans);//因为已经弹出ans元素，所以在压入栈中 
	
	return ans;
}
void FreeStack(Stack ptrS)
{
	free(ptrS -> data);//先释放数据域的内存空间 
	free(ptrS);//再释放ptrS所指向的空间 
}

typedef struct {//两个栈模拟队列
    Stack in;//模拟进队的栈
    Stack out;//模拟出队的栈
} MyQueue;


MyQueue* myQueueCreate() {//创建一个队列
    MyQueue* t = (MyQueue*)malloc(sizeof(MyQueue));//开辟一个队列

    t -> in = CreateStack(100);//创建一个栈
    t -> out = CreateStack(100);//创建一个栈

    return t;//返回队列
}

void myQueuePush(MyQueue* obj, int x) {
    push(obj -> in, x);//直接把x压入到in栈中
}

int myQueuePop(MyQueue* obj) {
    if (!empty(obj -> out)) {//如果out栈是不是空的，直接弹出out的栈顶元素
        return pop(obj -> out);
    }

    while(!empty(obj -> in)) {//只要in栈还有元素，就把inStack的元素压到outStack中
        push(obj -> out, pop(obj -> in));
    }

    return pop(obj -> out);//返回outStack栈顶元素
}

int myQueuePeek(MyQueue* obj) {
    if (empty(obj -> out)) {//如果outStack是空栈
        while(!empty(obj -> in)) {//把inStack的元素压入到outStack中
            push(obj -> out, pop(obj -> in));
        }
    }

    return peek(obj -> out);//返回outStack的栈顶元素但不弹出
}

bool myQueueEmpty(MyQueue* obj) {
    if (empty(obj -> in) && empty(obj -> out)) {//inStack和outStack都为空队列才为空
        return true;
    }

    return false;//否则不是空
}

void myQueueFree(MyQueue* obj) {//释放掉队列
    FreeStack(obj -> in);//释放inStack
    FreeStack(obj -> out);//释放outStack
    free(obj);//释放队列空间
}

/**
 * Your MyQueue struct will be instantiated and called as such:
 * MyQueue* obj = myQueueCreate();
 * myQueuePush(obj, x);
 
 * int param_2 = myQueuePop(obj);
 
 * int param_3 = myQueuePeek(obj);
 
 * bool param_4 = myQueueEmpty(obj);
 
 * myQueueFree(obj);
*/

有效的括号

力扣题目链接

由于栈结构的特殊性，非常适合做对称匹配类的题目，例如像回文问题。

先来分析一下 这里有三种不匹配的情况，

  1. 第一种情况，字符串里左方向的括号多余了 ，所以不匹配。

  2. 第二种情况，括号没有多余但括号的类型不匹配
  3. 第三种情况，字符串里右方向的括号多余了，所以不匹配。

解题思路

  1. 为了简化代码，我们遇到了左括号，我们就把对应得右括号压入到栈里面，那么在比较的时候就可以简化我们的代码了
  2. 根据上面分的情况，我们就很容易写出整个代码

代码实现

#define pr printf
#define ERROR -1//返回-1代表出错 

typedef char ELEMENT;//元素类型为int类型，抽象的艺术 

typedef struct SNode {//定义栈的数据类型 
	ELEMENT *data;//使用数组实现，当然也可以用指针来开辟 
	int size;//栈中元素的个数 
	int MaxSize;
}SNode,*Stack;

Stack CreateStack(int MaxSize);//创建一个最大大小为MaxSize的栈 
bool isFull(Stack ptrS);//判断栈是不是满了不能再存放了 
void push(Stack ptrS, ELEMENT item);//把元素ITEM压入栈中 
ELEMENT pop(Stack ptrS);//把栈顶的元素弹出 
bool empty(Stack ptrS);//判断栈是不是空栈 
int size(Stack ptrS);//返回栈中元素的个数 
ELEMENT peek(Stack ptrS);//返回栈顶元素，但不弹出栈顶元素 
void FreeStack(Stack ptrS);//释放ptrS所指向的空间

Stack CreateStack(int MaxSize)
{
	Stack s = (Stack)malloc(sizeof(SNode));//开辟一个栈空间 
	
	s -> MaxSize = MaxSize; 
	s -> size = 0;//让栈的大小为0 
	s -> data = (ELEMENT*)malloc(sizeof(ELEMENT) * MaxSize);//开辟空间用来存放元素 
	
	return s;
}
bool isFull(Stack ptrS) { 
	return ptrS -> size == ptrS -> MaxSize;//如果栈中的元素等于栈能容纳的最大元素代表栈满了 
}

void push(Stack ptrS, ELEMENT item) {//用指针可以改变ptrS所指向的栈,因为要改变所对应的栈顶位置 
	if (isFull(ptrS)) {//如果栈满了就不能进行压栈了 
		pr("栈已经满了\n");
		return ; 
	}
	else {
		ptrS -> data[ptrS -> size++] = item;//就是先把item压入到栈里面去，size的大小再加一 
	}
}

ELEMENT pop(Stack ptrS) {//用指针可以改变ptrS所指向的栈,因为要改变所对应的栈顶位置 
	if (empty(ptrS)) {//如果栈为空，那么没有元素可以弹出，所以是犯法操作，返回一个特定的值 
		pr("栈已经空了\n");
		return ERROR; 
	}
	
	return ptrS -> data[--ptrS -> size];//是先减一，再弹出栈顶元素 
}

bool empty(Stack ptrS) {
	return ptrS -> size == 0;//如果栈里面没有元素，那么栈就是空的
}

int size(Stack ptrS) {
	return ptrS -> size;//直接返回size
}
ELEMENT peek(Stack ptrS)
{
	if (empty(ptrS)) {// 
		pr("栈已经空了\n");
		return ERROR; 
	}
	
	ELEMENT ans = pop(ptrS);//使用pop函数 
	
	push(ptrS, ans);//因为已经弹出ans元素，所以在压入栈中 
	
	return ans;
}
void FreeStack(Stack ptrS)
{
	free(ptrS -> data);//先释放数据域的内存空间 
	free(ptrS);//再释放ptrS所指向的空间 
}

bool isValid(char* s) {
    if (strlen(s) & 1) {//如果字符串是奇数那么必然不可能是合法的
        return false;
    }

   Stack c;//准备一个栈，用来放对应的右括号，但实际上是左括号

   c = CreateStack(10000);//最大为10000大小，题目的要求

   while(*s) {//遍历完字符串才结束
       if (*s == '(') {//如果是左括号就压入对应的右括号
           push(c, ')');
       }
       else if (*s == '[') {//如果是左括号就压入对应的右括号
           push(c, ']');
       }
       else if (*s == '{') {//如果是左括号就压入对应的右括号
           push(c, '}');
       }
       else if (empty(c)) {//如果栈为空，那么代表做左括号少了，因为栈里面实际存放的是左括号对应的右括号，因为是左括号才压栈，所以其实存放的是左括号，只是为了方便之后的比较才存放对应的右括号。
           return false;
       }
       else if (pop(c) != *s) {//如果栈顶元素跟字符串不匹配，代表有括号的类型对不上
           return false;
       }
       s++;
   }

   bool ans = empty(c);//如果栈不为空，代表左括号多了，返回false，栈为空代表括号都对的上，那么就返回true

   FreeStack(c);//释放栈的空间

   return ans;
}

删除字符串中所有相邻的重复项

力扣题目链接

解题思路

  1. 本题要删除相邻相同元素，相对于有效的括号来说其实也是匹配问题，有效的括号 是匹配左右括号，本题是匹配相邻元素，最后都是做消除的操作。
  2. 本题也是用栈来解决的经典题目。
  3. 那么栈里应该放的是什么元素呢？
  4. 我们在删除相邻重复项的时候，其实就是要知道当前遍历的这个元素，我们在前一位是不是遍历过一样数值的元素，那么如何记录前面遍历过的元素呢？
  5. 所以就是用栈来存放，那么栈的目的，就是存放遍历过的元素，当遍历当前的这个元素的时候，去栈里看一下我们是不是遍历过相同数值的相邻元素。

代码实现

#define ERROR -1//返回-1代表出错 
#define pr printf

typedef char ELEMENT;//元素类型为int类型，抽象的艺术 

typedef struct SNode {//定义栈的数据类型 
	ELEMENT *data;//使用数组实现，当然也可以用指针来开辟 
	int size;//栈中元素的个数 
	int MaxSize;
}SNode,*Stack;

Stack CreateStack(int MaxSize);//创建一个最大大小为MaxSize的栈 
bool isFull(Stack ptrS);//判断栈是不是满了不能再存放了 
bool push(Stack ptrS, ELEMENT item);//把元素ITEM压入栈中 
ELEMENT pop(Stack ptrS);//把栈顶的元素弹出 
bool empty(Stack ptrS);//判断栈是不是空栈 
int size(Stack ptrS);//返回栈中元素的个数 
ELEMENT peek(Stack ptrS);//返回栈顶元素，但不弹出栈顶元素 
void FreeStack(Stack ptrS);//释放ptrS所指向的空间

char* removeDuplicates(char* s) {
    char *p = s;
    Stack a = CreateStack(20000);//题目说最大为20000

    while(*p)//遍历字符串
    {
        if (empty(a)) {//如果栈为空,直接压栈
            push(a, *p);
        }
        else if (peek(a) == *p) {//如果栈顶元素跟当前的元素相等,代表相邻元素相等，因为栈顶的元素是后进来的
            pop(a);//弹出栈顶元素
        }
        else {
            push(a, *p);//相邻元素不相等直接压栈
        }
        p++;
    }

    char *q = (char*)malloc(sizeof(char) * (size(a) + 1));//返回栈里面的元素个数，也就是删除重复项之后的字符串的长度，还要存放一个结束标志符，所有加一
    q[size(a)] = 0;//给字符串添加结束标志符
    
    for (int i = size(a); i > 0; i--) {//栈底的是先出来的，所有要倒序输出栈
        q[i - 1] = pop(a);
    }

    FreeStack(a);//释放栈空间

    return q;//返回字符串
}
Stack CreateStack(int MaxSize)
{
	Stack s = (Stack)malloc(sizeof(SNode));//开辟一个栈空间 
	
	s -> MaxSize = MaxSize; 
	s -> size = 0;//让栈的大小为0 
	s -> data = (ELEMENT*)malloc(sizeof(ELEMENT) * MaxSize);//开辟空间用来存放元素 
	
	return s;
}
bool isFull(Stack ptrS) { 
	return ptrS -> size == ptrS -> MaxSize;//如果栈中的元素等于栈能容纳的最大元素代表栈满了 
}

bool push(Stack ptrS, ELEMENT item) {//用指针可以改变ptrS所指向的栈,因为要改变所对应的栈顶位置 
	if (isFull(ptrS)) {//如果栈满了就不能进行压栈了 
		return false; 
	}
	else {
		ptrS -> data[ptrS -> size++] = item;//就是先把item压入到栈里面去，size的大小再加一 
		return true;
	}
}

ELEMENT pop(Stack ptrS) {//用指针可以改变ptrS所指向的栈,因为要改变所对应的栈顶位置 
	if (empty(ptrS)) {//如果栈为空，那么没有元素可以弹出，所以是犯法操作，返回一个特定的值 
		pr("栈已经空了\n");
		return ERROR; 
	}
	
	return ptrS -> data[--ptrS -> size];//是先减一，再弹出栈顶元素 
}

bool empty(Stack ptrS) {
	return ptrS -> size == 0;//如果栈里面没有元素，那么栈就是空的
}

int size(Stack ptrS) {
	return ptrS -> size;//直接返回size
}
ELEMENT peek(Stack ptrS)
{
	if (empty(ptrS)) {// 
		pr("栈已经空了\n");
		return ERROR; 
	}
	
	ELEMENT ans = pop(ptrS);//使用pop函数 
	
	push(ptrS, ans);//因为已经弹出ans元素，所以在压入栈中 
	
	return ans;
}
void FreeStack(Stack ptrS)
{
	free(ptrS -> data);//先释放数据域的内存空间 
	free(ptrS);//再释放ptrS所指向的空间 
}

逆波兰表达式求值

波兰表达式就是后缀表达式，而我们生活中用的多的大多是中缀表达式，也是最常见到的，例如(4 + (13 / 5)）它所对应的后缀表达式是"4" "13" "5" "/" "+"。

解题思路

  1. 只要是数字就压到栈里面去。
  2. 碰到运算符，就弹出栈顶的两个元素，在进行对应的运算。但要注意栈顶元素是被运算的数。比如除法，栈顶元素就是除数，即a / b里面的b，其他运算同理。
  3. 最后栈顶元素就是我们表达式的结果

代码实现

#define ERROR -1//返回-1代表出错 
#define pr printf

typedef int ELEMENT;//元素类型为int类型，抽象的艺术 

typedef struct SNode {//定义栈的数据类型 
	ELEMENT *data;//使用数组实现，当然也可以用指针来开辟 
	int size;//栈中元素的个数 
	int MaxSize;
}SNode,*Stack;

Stack CreateStack(int MaxSize);//创建一个最大大小为MaxSize的栈 
bool isFull(Stack ptrS);//判断栈是不是满了不能再存放了 
bool push(Stack ptrS, ELEMENT item);//把元素ITEM压入栈中 
ELEMENT pop(Stack ptrS);//把栈顶的元素弹出 
bool empty(Stack ptrS);//判断栈是不是空栈 
int size(Stack ptrS);//返回栈中元素的个数 
ELEMENT peek(Stack ptrS);//返回栈顶元素，但不弹出栈顶元素 
void FreeStack(Stack ptrS);//释放ptrS所指向的空间

int evalRPN(char** tokens, int tokensSize) {
    Stack data = CreateStack(10000);//开辟一个最大能放10000个元素的栈
    int i = 0;

    for (int i = 0; i < tokensSize; i++) {//遍历数组
        if (!strcmp(tokens[i], "+")) {//如果是加法运算
            int a = pop(data);//弹出栈顶的两个元素，作为运算数
            int b = pop(data);

            push(data, b + a);
        }
        else if (!strcmp(tokens[i], "-")) {//如果是减法运算
            int a = pop(data);//弹出栈顶的两个元素，作为运算数
            int b = pop(data);

            push(data, b - a);//注意顺序
        }
        else if (!strcmp(tokens[i], "*")) {//如果是乘法运算
            int a = pop(data);
            int b = pop(data);

            push(data, b * a);
        }
        else if (!strcmp(tokens[i], "/")) {//如果是除法运算
            int a = pop(data);
            int b = pop(data);

            push(data, b / a);//注意顺序
        }
        else {
            push(data, atoi(tokens[i]));//atoi的功能是把字符串转换成数字
        }
    }

    int ans = pop(data);//表达式结果就是栈顶元素
    
    FreeStack(data);//释放栈空间

    return ans;//返回答案
}
Stack CreateStack(int MaxSize)
{
	Stack s = (Stack)malloc(sizeof(SNode));//开辟一个栈空间 
	
	s -> MaxSize = MaxSize; 
	s -> size = 0;//让栈的大小为0 
	s -> data = (ELEMENT*)malloc(sizeof(ELEMENT) * MaxSize);//开辟空间用来存放元素 
	
	return s;
}
bool isFull(Stack ptrS) { 
	return ptrS -> size == ptrS -> MaxSize;//如果栈中的元素等于栈能容纳的最大元素代表栈满了 
}

bool push(Stack ptrS, ELEMENT item) {//用指针可以改变ptrS所指向的栈,因为要改变所对应的栈顶位置 
	if (isFull(ptrS)) {//如果栈满了就不能进行压栈了 
		return false; 
	}
	else {
		ptrS -> data[ptrS -> size++] = item;//就是先把item压入到栈里面去，size的大小再加一 
		return true;
	}
}

ELEMENT pop(Stack ptrS) {//用指针可以改变ptrS所指向的栈,因为要改变所对应的栈顶位置 
	if (empty(ptrS)) {//如果栈为空，那么没有元素可以弹出，所以是犯法操作，返回一个特定的值 
		pr("栈已经空了\n");
		return ERROR; 
	}
	
	return ptrS -> data[--ptrS -> size];//是先减一，再弹出栈顶元素 
}

bool empty(Stack ptrS) {
	return ptrS -> size == 0;//如果栈里面没有元素，那么栈就是空的
}

int size(Stack ptrS) {
	return ptrS -> size;//直接返回size
}
ELEMENT peek(Stack ptrS)
{
	if (empty(ptrS)) {// 
		pr("栈已经空了\n");
		return ERROR; 
	}
	
	ELEMENT ans = pop(ptrS);//使用pop函数 
	
	push(ptrS, ans);//因为已经弹出ans元素，所以在压入栈中 
	
	return ans;
}
void FreeStack(Stack ptrS)
{
	free(ptrS -> data);//先释放数据域的内存空间 
	free(ptrS);//再释放ptrS所指向的空间 
}

用队列实现栈

  其实跟用栈实现队列是一样的，都是模拟

解题思路

  1. 每次push的时候，就先记录队列元素的个数，然后让push的元素入队
  2. 然后进行之前元素个数的出队和入队的操作
  3. pop就直接弹出队列头就行了

代码实现

#define ERROR -1 

typedef int ELEMENT;

typedef struct queue {
	ELEMENT *data;//存放元素 
	int head;//指向队头，也就是队列的第一个元素
	int tail;//指向下一个入队的位置，所以区间为[head, tail) 
	int size;//记录队列元素的个数 
	int MaxSize;//记录队列最大能同时存在的元素个数 
}QNode, *Queue;

Queue CreateQueue(int n);//创建一个大小为n的队列 
bool isFull(Queue q);//判断队列是不是满了 
bool addQ(Queue q, ELEMENT item);//把元素item入队 
bool empty(Queue q);//判断队列是不是空 
ELEMENT deleteQ(Queue q);//出队 
ELEMENT head(Queue q);//取出队头的元素但不出队 
ELEMENT tail(Queue q);//取出队尾的元素 
int size(Queue q);//返回队列的元素个数 
void FreeQueue(Queue q);//释放队列

typedef struct {
    Queue q;//队列
} MyStack;

MyStack* myStackCreate() {
    MyStack* stack = (MyStack*)malloc(sizeof(MyStack));//开辟一个栈

    stack -> q = CreateQueue(100);//初始化队列

    return stack;
}

void myStackPush(MyStack* obj, int x) {
    int n = size(obj -> q);//记录队列元素的个数

    addQ(obj -> q, x);//把x入队
    for (int i = 0; i < n; i++) {
        addQ(obj -> q, deleteQ(obj -> q));//进行n次出队和入队的操作
    }
}

int myStackPop(MyStack* obj) {
    return deleteQ(obj -> q);//删除队列头
}

int myStackTop(MyStack* obj) {
    return head(obj -> q);//返回队列头就行了
}

bool myStackEmpty(MyStack* obj) {
    return empty(obj -> q);//判断队列是不是空就行了
}

void myStackFree(MyStack* obj) {
    FreeQueue(obj -> q);//先释放队列空间
    free(obj);//再释放栈空间
}

/**
 * Your MyStack struct will be instantiated and called as such:
 * MyStack* obj = myStackCreate();
 * myStackPush(obj, x);
 
 * int param_2 = myStackPop(obj);
 
 * int param_3 = myStackTop(obj);
 
 * bool param_4 = myStackEmpty(obj);
 
 * myStackFree(obj);
*/
Queue CreateQueue(int n)
{
	Queue t = (Queue)malloc(sizeof(QNode));//开辟一个队列 
	
	t -> data = (ELEMENT*)malloc(sizeof(ELEMENT) * n);//开辟空间来存放元素 
	t -> head = 0;//初始化队头 
	t -> tail = 0;//初始化队尾 
	t -> MaxSize = n;//初始化最大的大小
	t -> size = 0; 
	
	return t;//返回队列 
}
bool empty(Queue q)
{
	return q -> size == 0;//队列中没有元素，那么队列就是空的 
}
bool isFull(Queue q)
{
	return q -> size == q -> MaxSize;//如果队列中元素个数等于最大能容纳的元素，那么就满了 
}
bool addQ(Queue q, ELEMENT item)
{
	if (isFull(q)) {//如果队列是满的，不能入队返回false 
		return false;
	}
	
	q -> data[q -> tail++] = item;//把元素item入队，因为是[head, tail)，所以自增在后面 
	q -> tail %= q -> MaxSize;//如果到了数组尾，回到下标0位置 
	q -> size++;//队列元素个数加一 
	
	return true;//能入队返回true 
}
ELEMENT deleteQ(Queue q)
{
	if (empty(q)) {//如果队列为空，那么就不能出队，返回一个错误信息 
		return ERROR;
	}
	
	ELEMENT ans = q -> data[q -> head++];
	
	q -> head %= q -> MaxSize;
	q -> size--;
	
	return ans;//不为空，返回队头，因为是[head, tail)的区间，所以自增在后面 
}
ELEMENT head(Queue q)
{
	if (empty(q)) {//如果队列为空，没有队头，是非法的 ，返回一个错误信息 
		return ERROR;
	}
	
	return q -> data[q -> head];//队列不为空，返回队列头的元素，返回队头元素不用特判，因为是[head, tail)，那么head必定是有效的下标，所以直接返回 
}
ELEMENT tail(Queue q)
{
	if (empty(q)) {//如果队列为空，没有队尾，是非法的 ，返回一个错误信息 
		return ERROR;
	}
	
	return q -> tail - 1 < 0? q -> data[q -> MaxSize - 1]: q -> data[q -> tail - 1];//如果q -> tail - 1 < 0，代表是从MaxSize - 1下标过来的
	//然后tial变成0了，所以队尾元素实际在MaxSize - 1位置，其他位置不用特判 
	//因为是[head, tail)所以队尾元素在tail - 1位置，但因为是环形数组，可能是从MaxSize下标过来的
	//所以tail == 0是减一，数组越界了，因此要特判 
}
int size(Queue q)
{
	return q -> size;//因为是[head, tail)的区间所以，直接相减就是队列的元素个数 
}
void FreeQueue(Queue q)
{
	free(q -> data);//先释放掉元素的内存空间 
	free(q);//再释放掉队列的内存空间 
}

 最小栈

力扣题目链接

想要每次在常数时间取出栈中的最小值，我们需要另一个栈，来辅助。

解题思路

  1. push的时候数据栈直接放入，最小栈判断是不是空，是空就把元素也push到最小栈里面
  2. 最小栈不是空，那么就比较最小栈的栈顶和压入的元素谁最小,把最小的压入最小栈
  3. pop的时候同时pop数据栈和min栈就行了

代码实现

#define ERROR -1//返回-1代表出错 
#define pr printf

typedef int ELEMENT;//元素类型为int类型，抽象的艺术 

typedef struct SNode {//定义栈的数据类型 
	ELEMENT *data;//使用数组实现，当然也可以用指针来开辟 
	int size;//栈中元素的个数 
	int MaxSize;
}SNode,*Stack;

Stack CreateStack(int MaxSize);//创建一个最大大小为MaxSize的栈 
bool isFull(Stack ptrS);//判断栈是不是满了不能再存放了 
bool push(Stack ptrS, ELEMENT item);//把元素ITEM压入栈中 
ELEMENT pop(Stack ptrS);//把栈顶的元素弹出 
bool empty(Stack ptrS);//判断栈是不是空栈 
int size(Stack ptrS);//返回栈中元素的个数 
ELEMENT peek(Stack ptrS);//返回栈顶元素，但不弹出栈顶元素 
void FreeStack(Stack ptrS);//释放ptrS所指向的空间

Stack CreateStack(int MaxSize);//´´½¨Ò»¸ö×î´ó´óСΪMaxSizeµÄÕ» 
bool isFull(Stack ptrS);//ÅжÏÕ»ÊDz»ÊÇÂúÁ˲»ÄÜÔÙ´æ·ÅÁË 
bool push(Stack ptrS, ELEMENT item);//°ÑÔªËØITEMѹÈëÕ»ÖÐ 
ELEMENT pop(Stack ptrS);//°ÑÕ»¶¥µÄÔªËص¯³ö 
bool empty(Stack ptrS);//ÅжÏÕ»ÊDz»ÊÇ¿ÕÕ» 
int size(Stack ptrS);//·µ»ØÕ»ÖÐÔªËصĸöÊý 
ELEMENT peek(Stack ptrS);//·µ»ØÕ»¶¥ÔªËØ£¬µ«²»µ¯³öÕ»¶¥ÔªËØ 
void FreeStack(Stack ptrS);//ÊÍ·ÅptrSËùÖ¸ÏòµÄ¿Õ¼ä

typedef struct {
    Stack min;//最小栈，用来存放数据栈中的最小值
    Stack data;//数据栈
} MinStack;


MinStack* minStackCreate() {
    MinStack* s = (MinStack*)malloc(sizeof(MinStack));//开辟一个栈

    s -> min = CreateStack(30000);//根据题目要求最大30000
    s -> data = CreateStack(30000);

    return s;//返回栈
}

void minStackPush(MinStack* obj, int val) {
    push(obj -> data, val);/直接把数据压入数据栈
    if (empty(obj -> min)) {//如果最小栈是空的，直接压入最小栈
        push(obj -> min, val);
    }
    else {//最小栈不是空的
        if (peek(obj -> min) < val) {//如果数据栈中的最小值是最小的，那么继续压入数据栈中的最小值
            push(obj -> min, peek(obj -> min));
        }
        else {//如果数据栈中的最小值不是最小的，那么压入数据,即val作为新的最小值
            push(obj -> min, val);
        }
    }
}

void minStackPop(MinStack* obj) {
    pop(obj -> data);
    pop(obj -> min);//还要同时弹出最小栈的元素，不然就更新不了最小值
}

int minStackTop(MinStack* obj) {
    return peek(obj -> data);//返回数据栈的栈顶元素
}

int minStackGetMin(MinStack* obj) {
    return peek(obj -> min);//返回最小栈的栈顶元素
}

void minStackFree(MinStack* obj) {
    FreeStack(obj -> min);//释放最小栈
    FreeStack(obj -> data);//释放数据栈
    free(obj);//释放栈
}

/**
 * Your MinStack struct will be instantiated and called as such:
 * MinStack* obj = minStackCreate();
 * minStackPush(obj, val);
 
 * minStackPop(obj);
 
 * int param_3 = minStackTop(obj);
 
 * int param_4 = minStackGetMin(obj);
 
 * minStackFree(obj);
*/
Stack CreateStack(int MaxSize)
{
	Stack s = (Stack)malloc(sizeof(SNode));//开辟一个栈空间 
	
	s -> MaxSize = MaxSize; 
	s -> size = 0;//让栈的大小为0 
	s -> data = (ELEMENT*)malloc(sizeof(ELEMENT) * MaxSize);//开辟空间用来存放元素 
	
	return s;
}
bool isFull(Stack ptrS) { 
	return ptrS -> size == ptrS -> MaxSize;//如果栈中的元素等于栈能容纳的最大元素代表栈满了 
}

bool push(Stack ptrS, ELEMENT item) {//用指针可以改变ptrS所指向的栈,因为要改变所对应的栈顶位置 
	if (isFull(ptrS)) {//如果栈满了就不能进行压栈了 
		return false; 
	}
	else {
		ptrS -> data[ptrS -> size++] = item;//就是先把item压入到栈里面去，size的大小再加一 
		return true;
	}
}

ELEMENT pop(Stack ptrS) {//用指针可以改变ptrS所指向的栈,因为要改变所对应的栈顶位置 
	if (empty(ptrS)) {//如果栈为空，那么没有元素可以弹出，所以是犯法操作，返回一个特定的值 
		pr("栈已经空了\n");
		return ERROR; 
	}
	
	return ptrS -> data[--ptrS -> size];//是先减一，再弹出栈顶元素 
}

bool empty(Stack ptrS) {
	return ptrS -> size == 0;//如果栈里面没有元素，那么栈就是空的
}

int size(Stack ptrS) {
	return ptrS -> size;//直接返回size
}
ELEMENT peek(Stack ptrS)
{
	if (empty(ptrS)) { 
		pr("栈已经空了\n");
		return ERROR; 
	}
	
	ELEMENT ans = pop(ptrS);//使用pop函数 
	
	push(ptrS, ans);//因为已经弹出ans元素，所以在压入栈中 
	
	return ans;
}
void FreeStack(Stack ptrS)
{
	free(ptrS -> data);//先释放数据域的内存空间 
	free(ptrS);//再释放ptrS所指向的空间 
}

总结

  1. 栈这种数据结构在处理匹配问题的时候，往往有很大的用处。
  2. 函数的嵌套用的也是栈，不然怎么知道返回到那一个函数呢
  3. 浏览器访问网站用的也是栈，例如回退一个网页的时候，怎么知道上一个网页是什么呢