【数据结构】栈与队列的简单应用

【数据结构】栈与队列的简单应用

目录

1.括号匹配问题

题解：栈 2.用队列实现栈结构

题解：两个队列实现 3.用栈实现队列结构

题解：两个栈实现

1.括号匹配问题

给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

题目链接: 力扣20. 有效的括号.

题解：栈

借助栈的数据结构特性，我们可以遍历给定的括号数组：当遇到左括号时数组元素入栈，当遇到一个右括号时，栈内的栈顶元素出栈，并进行比较，若不能与之相互匹配为左右括号，则该括号数组不成立；反之再进一步判断，直至括号数组遍历完毕，这时若栈内仍有元素（左括号）尚未匹配出栈，说明括号数组左右括号数量不匹配，仍不满足要求。

//用栈结构实现括号判断问题

//动态开辟顺序表结构作为栈的结构
typedef struct stack
{
    char* array;
    int capacity;  //空间总大小
    int top;  //栈顶（存放结点个数）
}Stack;

//检测空间是否已满
void CheckCapacity(Stack* ps)
{
	assert(ps);
	int newCapacity = 2 * ps->capacity;
	if (ps->top == ps->capacity)
	{
		//1.申请新空间
		char* newArray = (char*)malloc(sizeof(char) * newCapacity);
		if (NULL == newArray)
		{
            printf("空间扩容失败!n");
			return;
		}
		//2.拷贝原空间至新空间
		memcpy(newArray, ps->array, ps->top * sizeof(char));
		//3.释放原空间
		free(ps->array);

		ps->array = newArray;
		ps->capacity = newCapacity;
	}
}
//初始化栈
void StackInit(Stack* ps)
{
    assert(ps);
    ps->array = (char*)malloc(sizeof(char)*3);  //默认开辟3个结点
    if(NULL == ps->array)  //检测堆上是否成功开辟空间
    {
        assert(0);
        return;
    }
    ps->capacity = 3;
    ps->top = 0;
}
//销毁栈
void StackDestroy(Stack* ps)
{
    assert(ps);
    if(ps->array)
    {
        free(ps->array);  //顺序结构连续空间 一次性释放
        ps->array++;
        ps->capacity = 0;
        ps->top = 0;
    }
}
//入栈（尾插）
void StackPush(Stack* ps,char a)
{
    assert(ps);
    //先判断栈空间是否满了
    CheckCapacity(ps);

    ps->array[ps->top] = a;
    ps->top++;
}
//出栈（头删）
void StackPop(Stack* ps)
{
    assert(ps);
    if(ps->top == 0)
    {
        printf("栈为空！n");
    }
    ps->top--;
}
//返回栈顶元素
char StackTop(Stack* ps)
{
	assert(ps);
	//1.检测栈是否为空
	if (ps->top == 0)
	{
		printf("获取错误！栈为空n");
		return -1;
	}
	//2.返回数组最后一位元素
	return ps->array[ps->top - 1];
}

bool isValid(char * s)
{
    bool flag = true;
    Stack st;
    StackInit(&st);
    while(*s)
    {

        if(*s == '[' || *s == '(' || *s == '{')
        {
            StackPush(&st,*s);
            s++;
        }
        else
        {
            if(st.top == 0)  //栈为空
            {
                flag = false;
                break;
            }
            char ch = StackTop(&st);
            StackPop(&st);
            if((*s == ']' && ch != '[')
            || (*s == '}' && ch != '{')
            || (*s == ')' && ch != '('))
            {
                flag = false;
                break;
            }
            else
            {
                s++;
            }
        }
    }
    
    if(flag == true)
    {
        if(st.top != 0)
        {
            flag = false;
        } 
    }

    StackDestroy(&st);
    return flag;
}

2.用队列实现栈结构

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种 *** 作（push、top、pop 和 empty）。

实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false

题目链接: 力扣225. 用队列实现栈.

题解：两个队列实现

//两队列实现栈结构

//用队列模拟栈结构，那么结点应该用队列的结点结构
//队列是前出后进 也就是头删尾插
//头删更适合链表结构

// 定义单链表结点
typedef struct QNode
{
	int data;
	struct QNode* next;
}QNode;

// 定义队列结构体
typedef struct Queue
{
	QNode* front;  //指向队头结点 队头：出队
	QNode* rear;   //指向队尾结点 队尾：入队
	int size;      //队列元素个数
}Queue;

// 初始化队列
void QueueInit(Queue* q)
{
	assert(q);
	q->front = NULL;
	q->rear = NULL;
	q->size = 0;
}

// 检测队列是否为空
int QueueEmpty(Queue* q)
{
	assert(q);
	return 0 == q->size;
}

// 创建队列结点
QNode* buyQNode(int data)
{
	QNode* newQNode = (QNode*)malloc(sizeof(QNode));
	if (NULL == newQNode)
	{
		assert(0);
		return NULL;
	}
	newQNode->data = data;
	newQNode->next = NULL;

	return newQNode;
}

// 入队列 尾插
void QueuePush(Queue* q, int data)
{
	assert(q);
	QNode* newQNode = buyQNode(data);
	//1.队列为空
	if (QueueEmpty(q))
	{
		q->front = newQNode;
	}
	else
	{
		//2.队列已有元素
		q->rear->next = newQNode;
	}
	//3.调整队列其余元素
	q->rear = newQNode;
	q->size++;

	return;
}

// 出队列 头删
int QueuePop(Queue* q)
{
	assert(q);
	//1.队列为空
	if (QueueEmpty(q))
	{
		assert(0);
		return -1;
	}
	else
	{
		//2.队列已有元素
		QNode* delNode = q->front;
		int delData = delNode->data;
		q->front = q->front->next;
		q->size--;
		free(delNode);
		if (NULL == q->front)
		{
			q->rear = NULL;
		}
		return delData;
	}
}

// 获取队尾元素
int QueueBack(Queue* q)
{
	//队列为空情况设为违法
	assert(!QueueEmpty(q));
	return q->rear->data;
}

// 销毁队列
void QueueDestroy(Queue* q)
{
	assert(q);
	QNode* cur = q->front;
	while (cur)
	{
		q->front = cur->next;
		free(cur);
		cur = q->front;
	}
	q->front = NULL;
	q->rear = NULL;
	q->size = 0;
}

//------------------------------------------------------------------------------

//定义栈结构--由两个队列构成
typedef struct
{
	Queue Q1;
	Queue Q2;
} MyStack;


//创建栈
MyStack* myStackCreate()
{
	MyStack* obj = (MyStack*)malloc(sizeof(MyStack));  //在堆上开辟栈结构
	if (NULL == obj)
	{
		assert(0);
		return NULL;
	}
	QueueInit(&(obj->Q1));  //初始化队列1
	QueueInit(&(obj->Q2));  //初始化队列2
	return obj;
}

//入栈
//哪个队列不为空，存进那个队
void myStackPush(MyStack* obj, int x)
{
	if (QueueEmpty(&(obj->Q1)))
	{
		QueuePush(&(obj->Q2),x);
	}
	else
	{
		QueuePush(&(obj->Q1), x);
	}
}

//出栈
//将不为空队列的前n-1个结点转到另一个队列
//在将该队列最后一个结点出队即可
int myStackPop(MyStack* obj)
{
	if (QueueEmpty(&(obj->Q1)))
	{
		while (obj->Q2.size > 1)
		{
			QueuePush(&(obj->Q1), QueuePop(&(obj->Q2)));
		}
		return QueuePop(&(obj->Q2));
	}
	while (obj->Q1.size > 1)
	{
		QueuePush(&(obj->Q2), QueuePop(&(obj->Q1)));
	}
	return QueuePop(&(obj->Q1));
}

//返回栈顶元素
//将不为空的队列的队尾元素返回即可
int myStackTop(MyStack* obj) 
{
	if (QueueEmpty(&(obj->Q1)))
	{
		return QueueBack(&(obj->Q2));
	}
	else
	{
		return QueueBack(&(obj->Q1));
	}
}

//判断是否空栈
//判断两个队列是否为空
bool myStackEmpty(MyStack* obj) 
{
	if (QueueEmpty(&(obj->Q1)) && QueueEmpty(&(obj->Q2)))
	{
		return true;
	}
	return false;
}

//释放栈
//先销毁栈的两个队列，再销毁栈结构
void myStackFree(MyStack* obj) 
{
	assert(obj);
	QueueDestroy(&(obj->Q1));
	QueueDestroy(&(obj->Q2));

	free(obj);
}

3.用栈实现队列结构

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有 *** 作（push、pop、peek、empty）：

实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false

题目链接: 力扣232. 用栈实现队列.

题解：两个栈实现

//用两栈实现队列结构

//栈结构只从尾部出入 因此采用顺序表结构
//采用动态开辟顺序表结构
typedef struct Stack
{
	int* array;
	int capacity;  //空间总大小
	int size;  //储存实际大小
}Stack;

// 初始化栈
void StackInit(Stack* ps)
{
	assert(ps);
	ps->array = (int*)malloc(sizeof(int) * 3); //初始化默认开辟三个单位
	if (NULL == ps->array)
	{
		assert(0);
		return;
	}

	ps->capacity = 3;
	ps->size = 0;
}

// 检测空间是否已满
static void CheckCapacity(Stack* ps)
{
	assert(ps);
	int newCapacity = 2 * ps->capacity;
	if (ps->size == ps->capacity)
	{
		//1.申请新空间
		int* newArray = (int*)malloc(sizeof(int) * newCapacity);
		if (NULL == newArray)
		{
			assert(0);
			return;
		}
		//2.拷贝原空间至新空间
		memcpy(newArray, ps->array, ps->size * sizeof(int));
		//3.释放原空间
		free(ps->array);

		ps->array = newArray;
		ps->capacity = newCapacity;
	}
}

// 入栈 （尾插）
void StackPush(Stack* ps, int data)
{
	assert(ps);
	//1.判断栈空间
	CheckCapacity(ps);
	//2.直接插入
	ps->array[ps->size] = data;
	ps->size++;
}

// 检测栈是否为空
int StackEmpty(Stack* ps)
{
	assert(ps);
	return 0 == ps->size;
}

// 出栈 （尾删）
int StackPop(Stack* ps)
{
	assert(ps);
	//1.检测栈是否为空
	if (StackEmpty(ps))
	{
		printf("删除错误！栈为空n");
		return -1;
	}
	//2.保存删除的值
	int delData = ps->array[ps->size - 1];
	//3.直接减值
	ps->size--;

	return delData;
}

// 获取栈顶元素
int StackTop(Stack* ps)
{
	assert(ps);
	//1.检测栈是否为空
	if (StackEmpty(ps))
	{
		printf("获取错误！栈为空n");
		return -1;
	}
	//2.返回数组最后一位元素
	return ps->array[ps->size - 1];
}

//销毁链表
void StackDestroy(Stack* ps)
{
	assert(ps);
	if (ps->array)
	{
		free(ps->array);
		ps->array = NULL;
		ps->capacity = 0;
		ps->size = 0;
	}
}

//-------------------------------------------------------------------------------

//定义队列结构--两个栈构成
typedef struct
{
	Stack S1;  //令S1为入队栈
	Stack S2;  //令S2为出队栈
} MyQueue;

//初始化队列
MyQueue* myQueueCreate()
{
	//先在堆上开辟队列空间
	MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
	if (NULL == obj)
	{
		assert(0);
		return NULL;
	}
	//初始化队列里的栈空间
	StackInit(&(obj->S1));
	StackInit(&(obj->S2));

	return obj;
}

//入队
//直接将数据存入栈S1中
void myQueuePush(MyQueue* obj, int x)
{
	assert(obj);
	StackPush((&(obj->S1)), x);
}

//出队
//将栈S2的栈顶出栈
//若S2没有数据，则先将栈S1的所有数据转入栈S2中
int myQueuePop(MyQueue* obj) 
{
	if (StackEmpty(&(obj->S2)))  //栈S2为空
	{
		while (obj->S1.size)
		{
			StackPush(&(obj->S2), StackPop(&(obj->S1)));
		}
	}
	return StackPop(&(obj->S2));
}

//返回队列开头的元素
//返回栈S2的栈顶元素
//若S2没有数据，则先将栈S1的所有数据转入栈S2中
int myQueuePeek(MyQueue* obj) 
{
	assert(obj);
	if (StackEmpty(&(obj->S2)))  //栈S2为空
	{
		while (obj->S1.size)
		{
			StackPush(&(obj->S2), StackPop(&(obj->S1)));
		}
	}
	return StackTop(&(obj->S2));
}

//判断队列是否为空
//直接判断两个栈是否为空即可
bool myQueueEmpty(MyQueue* obj) 
{
	assert(obj);
	if (StackEmpty(&(obj->S1)) && StackEmpty(&(obj->S2)))
	{
		return true;
	}
	return false;
}

void myQueueFree(MyQueue* obj) 
{
	assert(obj);
	StackDestroy(&(obj->S1));
	StackDestroy(&(obj->S2));
	free(obj);
}