[数据结构与算法]栈和队列题目

有效的括号（简单）

题目链接： LeetCode20.有效的括号

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

解题思路：
1.左括号，进栈。
2.右括号，栈里面出一个与这个左括号进行匹配，匹配失败就false。

题解：
这一个题目用C语言实现的话，就必须自己写一个栈，然后去调用写的栈的函数接口，特别的麻烦。以后如果学了C++，那么我们可以直接用STL库里面的函数，相对而言就简化了很多。
但目前我们依旧用C语言来实现。

typedef char STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;       //栈顶的位置
	int capacity;  //容量
}ST;

void StackInit(ST* ps);
void StackDestroy(ST* ps);
void StackPush(ST* ps, STDataType x);
void StackPop(ST* ps);
bool StackEmpty(ST* ps);
int StackSize(ST* ps);
STDataType StackTop(ST* ps);

void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}

void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	//空间满了扩容
	if (ps->capacity == ps->top)
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		ps->a = (STDataType*)realloc(ps->a, newCapacity * sizeof(STDataType));
		if (ps->a == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		ps->capacity = newCapacity;
	}
	ps->a[ps->top] = x;
	ps->top++;
}

void StackPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	--ps->top;
}

bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	return ps->a[ps->top - 1];
}

bool isValid(char * s)
{
    ST st;//我们先创建一个栈
    StackInit(&st);//对栈进行初始化

    while(*s)//字符串如果没有遍历完则继续进入循环，字符串结束的标志为'\0'
    {
        if(*s=='('||*s=='{'||*s=='[')//*s是左括号的情况
        {
            StackPush(&st,*s);//进行入栈
            ++s;//继续向后遍历
        }
        else//*s不是左括号的情况
        {
            if(StackEmpty(&st))//如果字符串的第一个括号就是右括号，那么就可能匹配上了
                return false;

            char top=StackTop(&st);//取栈顶的元素
            StackPop(&st);//删除栈顶的元素

            if((*s=='}'&&top!='{')||(*s==']'&&top!='[')||(*s==')'&&top!='('))
            {
                return false;//如果匹配不成功，直接false
            }

            ++s;//匹配，继续向后遍历字符串
        }
    }

    //栈为空，则说明所有的左括号都匹配了
    bool ret=StackEmpty(&st);
    StackDestroy(&st);
    
    return ret;
}

用队列实现栈（简单）

题目链接： LeetCode225.用队列实现栈

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

实现 MyStack 类：

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

注意：

• 你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
• 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

示例：

输入：
[“MyStack”, “push”, “push”, “top”, “pop”, “empty”]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]
解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

提示：
提示：

• 1 <= x <= 9
• 最多调用100 次 push、pop、top 和 empty
• 每次调用 pop 和 top 都保证栈不为空

题目分析：
首先先定义两个队列。
1.入栈，push数据到不为空的队列
2.出栈，把不为空的队列的数据的前N-1个数据导入另一个空队列，最后剩下的一个删掉。
3.保持一个队列存储数据，另外一个队列空着。要出栈是，空队列用来导数据。

和上一个题目一样，如果需要用C语言来写，那么就要自己实现队列的基本接口。

题解：

typedef int QDataType;

//链式结构：表示队列
typedef struct QueueNode
{
	QDataType data;           //存储数据
	struct QueueNode* next;   //指针域
}QNode;

//队列的结构
typedef struct Queue
{
	QNode* head;//标识队头的位置
	QNode* tail;//标识队尾的位置
}Queue;

//初始化队列
void QueueInit(Queue* pq);
//队尾入队列
void QueuePush(Queue* pq, QDataType x);
//队头出队列
void QueuePop(Queue* pq);
//获取队列头部元素
QDataType QueueFront(Queue* pq);
//获取队列队尾元素
QDataType QueueBack(Queue* pq);
//获取队列中有效元素个数
int QueueSize(Queue* pq);
//检测队列是否为空，如果为空返回非零结果，如果非空返回0
bool QueueEmpty(Queue* pq);
//销毁队列
void QueueDestroy(Queue* pq);

//初始化队列
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;//将两个指针置为空
}

//队尾入队列
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));//申请一个新的结点
	assert(newnode);//检测结点是否申请成功
	newnode->data = x;//
	newnode->next = NULL;
	if (pq->tail == NULL)//如果队列为空的情况
	{
		assert(pq->head==NULL);
		pq->tail = pq->head = newnode;
	}
	else//队列不为空的情况
	{
		pq->tail->next = newnode;//尾插一个新结点
		pq->tail = newnode;//更新尾的位置
	}
}

//队头出队列
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head && pq->tail);//保证队列中有数据在往下走
	if (pq->head->next == NULL)//如果队列里面只有一个数据的情况
	{
		free(pq->head);//释放队头数据
		pq->head = pq->tail = NULL;//将队列的头指针和尾指针均置为空
	}
	else
	{
		QNode* next = pq->head->next;//让next指向队头结点的下一个结点
		free(pq->head);//释放队头结点
		pq->head = next;//让head指向next结点
	}
}

//获取队列头部元素
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);//检测队列是否为空
	return pq->head->data;//返回队列头部元素
}

//获取队列队尾元素
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->tail);//检测队列是否为空
	return pq->tail->data;//返回队列尾部元素
}

//获取队列中有效元素个数
int QueueSize(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;//让cur指向队头的元素
	size_t size = 0;//定义一个无符号的size变量用来计数
	while (cur)//cur不为空则进入循环继续执行
	{
		size++;//size=size+1
		cur = cur->next;//继续向后遍历
	}
	return size;//返回有效元素个数
}

//检测队列是否为空，如果为空返回非零结果，如果非空返回0
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	//return (pq->head == NULL) && (pq->tail == NULL);
    return pq->head == NULL;
}

//销毁队列
void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;//定义一个next指向cur的下一个结点
		free(cur);//释放cur
		cur = next;
	}
	pq->head = pq->tail = NULL;//将头尾指针均置为空
}

typedef struct
{
	Queue q1;//定义队列1
	Queue q2;//定义队列2
} MyStack;


MyStack* myStackCreate() {
	MyStack* pst = (MyStack*)malloc(sizeof(MyStack));//为MyStack结构动态申请一块空间
	assert(pst);//检测空间申请是否成功

	QueueInit(&pst->q1);//对队列1进行初始化
	QueueInit(&pst->q2);//对队列2进行初始化
	return pst;//返回申请的空间
}

void myStackPush(MyStack* obj, int x) {
	assert(obj);

	//向不为空的队列里面插入数据
	if (!QueueEmpty(&obj->q1))
	{
		QueuePush(&obj->q1, x);
	}
	else
	{
		QueuePush(&obj->q2, x);
	}
}

int myStackPop(MyStack* obj) {
	assert(obj);

	Queue* emptyQ = &obj->q1;//默认队列1为空
	Queue* nonEmptyQ = &obj->q2;//默认队列2不为空

	//若队列1不为空
	if (!QueueEmpty(&obj->q1))
	{
		emptyQ = &obj->q2;//队列2为空
		nonEmptyQ = &obj->q1;//队列1不为空
	}

	//把非空队列的前N-1个数据，导入空队列，剩下的一个删掉
	//就可以实现后进先出
	while (QueueSize(nonEmptyQ) > 1)
	{
		QueuePush(emptyQ, QueueFront(nonEmptyQ));//将非空队列的数据导入空队列
		QueuePop(nonEmptyQ);
	}
	int top = QueueFront(nonEmptyQ);//取非空队列队头的数据
	QueuePop(nonEmptyQ);
	return top;
}

int myStackTop(MyStack* obj) {
	assert(obj);
	//返回非空队列的队尾数据
	if (!QueueEmpty(&obj->q1))
	{
		return QueueBack(&obj->q1);
	}
	else
	{
		return QueueBack(&obj->q2);
	}
}

bool myStackEmpty(MyStack* obj) {
	assert(obj);
	//连个队列都为空，则这个栈为空
	return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

void myStackFree(MyStack* obj)
{
	assert(obj);
	QueueDestroy(&obj->q1);
	QueueDestroy(&obj->q2);
	free(obj);
}

用栈实现队列（简单）

题目链接： LeetCode232.用栈实现队列

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

实现 MyQueue 类：

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

说明：

• 你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
• 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
  

题目解析：
开两个栈，一个栈用来入数据，另一个栈用来出数据。

题解：

typedef int STDataType;
typedef struct Stack
{
	STDataType* a;  
	int top;       //栈顶
	int capacity;  //容量
}Stack;


//初始化栈
void StackInit(Stack* ps);
//入栈
void StackPush(Stack* ps, STDataType x);
//出栈
void StackPop(Stack* ps);
//获取栈顶元素
STDataType StackTop(Stack* ps);
//获取栈中有效元素个数
int StackSize(Stack* ps);
//检测栈是否为空，如果为空返回非零结果，如果不为空返回0
bool StackEmpty(Stack* ps);
//栈的销毁
void StackDestroy(Stack* ps);


//初始化栈
void StackInit(Stack* ps)
{
	assert(ps);//检测传过来的ps是否为空
	ps->a = NULL;//把a标识的这块空间先置为空
	ps->top = ps->capacity = 0;
}

//入栈
void StackPush(Stack* ps, STDataType x)
{
	assert(ps);//检测ps是否为空

	//如果空间满了，我们需要扩容
	if (ps->capacity == ps->top)//判断空间是否满了的条件
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//指定新空间的大小
		ps->a = (STDataType*)realloc(ps->a, newCapacity*sizeof(STDataType));//进行扩容
		if (ps->a == NULL)//扩容失败
		{
			printf("realloc fail\n");
			exit(-1);//终止程序
		}
		ps->capacity = newCapacity;//让其标识新的空间的大小
	}
	ps->a[ps->top] = x;//将数据放入栈
	ps->top++;//top向后走一步
}

//出栈
void StackPop(Stack* ps)
{
	assert(ps);
	if (ps->top > 0)//避免栈里面数据已经删除完了，top依旧向下减为负数
	{
		--ps->top;
	}
}

//获取栈顶元素
STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(ps->top > 0);//保证下标为正
	return ps->a[ps->top - 1];//返回栈顶元素
}

//获取栈中有效元素个数
int StackSize(Stack* ps)
{
	assert(ps);
	return ps->top;
}

//检测栈是否为空，如果为空返回非零结果，如果不为空返回0
bool StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->top == 0;//如果条件成立就返回真，否则就为假（不为空）
}

//栈的销毁
void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->a);//释放开辟的这一块空间
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}


typedef struct {
    Stack pushST;//入数据的栈
    Stack popST;//出数据的栈
} MyQueue;

MyQueue* myQueueCreate() {
    MyQueue*obj=(MyQueue*)malloc(sizeof(MyQueue));
    assert(obj);

    //初始化开辟的栈空间
    StackInit(&obj->pushST);
    StackInit(&obj->popST);
    return obj;
}

void myQueuePush(MyQueue* obj, int x) {
    assert(obj);
    StackPush(&obj->pushST,x);//入数据
}

int myQueuePop(MyQueue* obj) {
    assert(obj);

    //如果popST为空，把pushST的数据导过来加，就符合先进先出的顺序了
    if(StackEmpty(&obj->popST))
    {
        while(!StackEmpty(&obj->pushST))//把pushST里面的全部数据导入popST中
        {
            StackPush(&obj->popST,StackTop(&obj->pushST));
            StackPop(&obj->pushST);
        }
    }
    int top=StackTop(&obj->popST);//取popST栈的栈顶数据
    StackPop(&obj->popST);
    return top;
}

int myQueuePeek(MyQueue* obj) {
    assert(obj);
    if(StackEmpty(&obj->popST))
    {
        while(!StackEmpty(&obj->pushST))
        {
            StackPush(&obj->popST,StackTop(&obj->pushST));
            StackPop(&obj->pushST);
        }
    }
    return StackTop(&obj->popST);
}

bool myQueueEmpty(MyQueue* obj) {
    assert(obj);
    return StackEmpty(&obj->pushST)&&StackEmpty(&obj->popST);
}

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

设计循环队列（中等）

题目链接： LeetCode622.设计循环队列

题目：
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

你的实现应该支持如下操作：

• MyCircularQueue(k): 构造器，设置队列长度为 k 。
• Front: 从队首获取元素。如果队列为空，返回 -1 。
• Rear: 获取队尾元素。如果队列为空，返回 -1 。
• enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
• deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
• isEmpty(): 检查循环队列是否为空。
• isFull(): 检查循环队列是否已满。
  
  题目解析：
  
  
  
  题解：

typedef struct {
    int* a;//定义一个int型的指针
    int head;//记录循环队列的头
    int tail;//记录循环队列的尾
    int k;//记录要存储多少元素
} MyCircularQueue;

//需要在这里提前声明一下，因为在这两个函数实现的前面有函数调用这两个函数
bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);


MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));//开辟一个结构体空间
    assert(obj);//检测空间开辟是否成功

    obj->a = (int*)malloc(sizeof(int) * (k + 1));//开辟能够存储k+1个整形元素的数组
    obj->head = obj->tail = 0;//将循环队列的头和尾的位置先置为0
    obj->k = k;

    return obj;//返回开辟的空间
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if (myCircularQueueIsFull(obj))//队列满了的情况
        return false;

    //向数组中下标尾tail的位置插入指定数据
    obj->a[obj->tail] = value;

    //将tail指向循环队列的最后一个位置的情况
    if (obj->tail == obj->k)
    {
        obj->tail = 0;
    }
    else
    {
        obj->tail++;
    }
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))//队列为空的情况
        return false;

    //head在循环队列的最后一个位置的特殊情况
    if (obj->head == obj->k)
    {
        obj->head = 0;
    }
    else
    {
        obj->head++;
    }
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))//队列为空的情况
        return -1;

    return obj->a[obj->head];//返回队列的首元素
}

int myCircularQueueRear(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))//队列为空的情况
        return -1;

    //因为tail的前一个位置为队列的最后一个元素的位置，所以特殊情况拿出来考虑
    if (obj->tail == 0)
    {
        return obj->a[obj->k];
    }
    else
    {
        return obj->a[obj->tail - 1];
    }
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->head == obj->tail;//head==tail时，队列为空
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {

    //这里需要分两种情况讨论
    if (obj->head == 0 && obj->tail == obj->k)
    {
        return true;
    }
    else
    {
        return obj->tail + 1 == obj->head;
    }
}

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);//首先是否后开辟的动态空间a，如果不释放则会造成内存泄漏
    free(obj);//释放开辟的obj指向的空间
}