栈和队列的基础知识，C语言实现及经典OJ题

题目来源：力扣 

基础知识 

一.栈

1.栈的概念

定义：堆栈又名栈（stack），它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。

压栈：向一个栈插入新元素，又称作进栈、入栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；

出栈：从一个栈删除元素又称作退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

特点：先入后出，后入先出。

2.栈的实现

//利用动态数组实现栈
typedef int STDataType;
typedef struct Stack
{
	STDataType* arr;//用数组来实现栈
	int top;
	int capacity;
}ST;
// 初始化和销毁
void STInit(ST* pst)
{
	assert(pst);

	pst->arr = NULL;
	pst->capacity = 0;
	pst->top = 0;//top指向栈顶元素的下一位，数组下标从0开始
	//top实际指向的是下标，且top == 数据个数
}
void STDestroy(ST* pst)
{
	assert(pst);
	free(pst->arr);
	pst->arr = NULL;
	pst->capacity = 0;
	pst->top = 0;
}

// 入栈  出栈
void STPush(ST* pst, STDataType x)
{
	assert(pst);
	if (pst->capacity == pst->top)//扩容
	{
		int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;
		STDataType* tmp = (STDataType*)realloc(pst->arr, newcapacity*sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc");
			return;
		}
		pst->arr = tmp;
		pst->capacity = newcapacity;
	}
	pst->arr[pst->top++] = x;
}
void STPop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);//栈的数据个数大于0
	pst->top--;
}

// 取栈顶数据
STDataType STTop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);//栈的数据个数大于0
	return pst->arr[(pst->top - 1)];
}

// 判空
bool STEmpty(ST* pst)
{
	assert(pst);
	return (pst->top == 0);
}
// 获取数据个数
int STSize(ST* pst)
{
	assert(pst);
	return pst->top ;
}

二.队列 

1.队列的概念

定义：队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。

队尾：进行插入操作端称为队尾

队头：进行删除操作的端称为队头。

特点：先进先出（FIFO—first in first out）

分类：顺序队列和循环队列

顺序队列： 

2.顺序队列的实现

//队列的基本接口

//用单链表实现队列
typedef int QDataType;
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType val;
}QNode;

typedef struct Queue
{
	QNode* phead;//队列头节点指针
	QNode* ptail;//队列尾节点指针
	int size;//数据个数
}Queue;
//初始化  销毁
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}
void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* pcur = pq->phead;
	while (pcur)
	{
		QNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

// 队尾插入
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc");
		return;
	}
	newnode->next = NULL;
	newnode->val = x;
	//队列为空
	if (pq->ptail == NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	pq->size++;
}
// 队头删除
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->size > 0);

	//一个节点
	if (pq->phead == pq->ptail)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else//多个节点
	{
		QNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
	}

	pq->size--;
}

// 取队头和队尾的数据
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->phead);
	return pq->phead->val;
}
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->ptail);
	return pq->ptail->val;
}

//队列数据个数
int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}
//判空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return (pq->size == 0);
}

3.循环队列的概念：

 定义：在实际使用队列时，为了使队列空间能重复使用，往往对队列的使用方法稍加改进：无论插入或删除，一旦tail(尾）指针增1或head（头）指针增1 时超出了所分配的队列空间，就让它指向这片连续空间的起始位置。这实际上是把队列空间想象成一个环形空间，环形空间中的存储单元循环使用，用这种方法管理的队列也就称为循环队列。除了一些简单应用之外，真正实用的队列是循环队列。

空和满的判别条件：在循环队列中，当队列为空时，有head = tail，而当所有队列空间全占满时，也有head = tail。为了区别这两种情况，规定循环队列最多只能有MaxSize-1个队列元素，当循环队列中只剩下一个空存储单元时，队列就已经满了。因此，队列判空的条件是head = tail，而队列判满的条件是head=（tail+1）%MaxSize

题目一.有效的括号（括号匹配问题）

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

4. 示例 1：

   输入：s = "()"
   输出：true
   

   示例 2：

   输入：s = "()[]{}"
   输出：true
   

   示例 3：

   输入：s = "(]"
   输出：false

解题方法：

分析：

从字符串s的右边开始看，若左右括号不匹配或者左括号在前，则字符串无效，若匹配，则二者可以消掉，继续重复上述步骤。

左右括号数量一致

核心思想：

后进先出

工具：

栈

思路：（从s的左边开始依次，一个一个读取）

1. 左括号入栈

2.右括号与栈顶的左括号尝试匹配

代码（力扣中的部分代码）（由于栈和队列的接口代码在上文中已经写明，题目代码中就不再赘述）

（题目一至题目三都用到了前面实现的接口函数，题目四没有）

//题目主代码逻辑
bool isValid(char* s) 
{
    //左括号入栈，右括号出栈
    ST st;
    STInit(&st);
    while(*s)
    {
        //左括号入栈
        if(*s == '('||*s == '['||*s == '{')
        {
            STPush(&st,*s);
        }
        else//右括号与栈顶左括号尝试匹配
        {
            //如果栈为空，且s中的是右括号，则直接返回false
            if(STEmpty(&st))
            {
                STDestroy(&st);
                return false;
            }
            char top = STTop(&st);
            //不匹配
            if(top=='('&&(*s)!=')'||
               top=='['&&(*s)!=']'||
               top=='{'&&(*s)!='}')
            {
                STDestroy(&st);//销毁
                return false;
            }
            //匹配，栈顶的左括号出栈
            STPop(&st);
        }
        s++;
    }
    //如果栈为空，说明左括号和右括号数量匹配
    //反之，数量不匹配
    bool ret = STEmpty(&st);

    STDestroy(&st);
    return ret;

}

题目二.用队列实现栈 

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

实现 MyStack 类：

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

 分析：

压栈：将数据依次插入第一个队列

出栈：将尾数据之前的所有数据导入到第二个队列中（队列之间导入数据可以保证数据的顺序不变），留下的尾数据就是要出栈的栈顶元素

判空：如果两个队列都为空则栈为空

要点：

1.一个队列始终往不为空，用于进行压栈操作

2.另一个队列在每一次操作之后，一直保持为空，用于导入数据，实现出栈

 解题代码

//题目代码主逻辑

typedef struct 
{
    Queue que1;
    Queue que2;   
} MyStack;


MyStack* myStackCreate() {
    MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&pst->que1);
    QueueInit(&pst->que2);
    return pst;
}

void myStackPush(MyStack* obj, int x) 
{
    //往非空队列插入数据
   if(!QueueEmpty(&obj->que1))
    {
        QueuePush(&obj->que1,x);
    }
    else
    {
        QueuePush(&obj->que2,x);
    }

}

int myStackPop(MyStack* obj) 
{
    //判断哪个队列为空
    //假设法
    Queue* empty = &obj->que1;
    Queue* noempty = &obj->que2;
    if(!QueueEmpty(&obj->que1))
    {
        empty = &obj->que2;
        noempty = &obj->que1;
    }
    //非空队列的前size-1个数据导到空队列中
    while(QueueSize(noempty) > 1)
    {
        QueuePush(empty,QueueFront(noempty));
        QueuePop(noempty);
    }

    int top = QueueFront(noempty);
    QueuePop(noempty);
    return top;
}

int myStackTop(MyStack* obj) 
{
    if(!QueueEmpty(&obj->que1))
    {
        return QueueBack(&obj->que1);
    }
    else
    {
        return QueueBack(&obj->que2);
    }
}

bool myStackEmpty(MyStack* obj) 
{
    return (QueueEmpty(&obj->que1))&&(QueueEmpty(&obj->que2));    
}

void myStackFree(MyStack* obj) 
{
    //先释放每个队列，在释放栈
    QueueDestroy(&obj->que1);
    QueueDestroy(&obj->que2);
    free(obj);
    obj = NULL;
    
}

题目三.用栈实现队列

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

实现 MyQueue 类：

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

 分析：

方法一

和前面用队列实现栈大致相同，一个栈始终不为空，用于插入数据，另一个栈在每一次操作之后，一直保持为空，用于数据的转移，实现出队列的操作

不同的是，每一次Pop操作要进行两次数据的转移

方法二

设计两个栈，一个叫pushst，只用来插入数据，另一个叫popst，只用来删除数据，当popst为空时，将pushst中的所有数据导入到popst中。

方法一： 

typedef struct 
{
    ST st1;
    ST st2;
} MyQueue;


MyQueue* myQueueCreate() 
{
    MyQueue* pq = (MyQueue*)malloc(sizeof(MyQueue));
    STInit(&pq->st1);
    STInit(&pq->st2);
    return pq;
}

void myQueuePush(MyQueue* obj, int x) 
{
    //往非空栈中存数据
   if(!STEmpty(&obj->st1))
    {
        STPush(&obj->st1,x);
    }
    else
    {
        STPush(&obj->st2,x);
    }


}

int myQueuePop(MyQueue* obj) 
{
    //把非空栈中后size-1个数据挪到空栈中
    ST* empty = &obj->st1;
    ST* noempty = &obj->st2;
    if(STEmpty(&obj->st2))
    {
        ST* empty = &obj->st2;
        ST* noempty = &obj->st1;
    }
    while(noempty->top>1)
    {
        STPush(empty,STTop(noempty));
        STPop(noempty);
    }
    int top = STTop(noempty);    
    STPop(noempty);
    //再把数据导回去
    while(empty->top)
    {
        STPush(noempty,STTop(empty));
        STPop(empty);
    }
    return top;
}

int myQueuePeek(MyQueue* obj) 
{
    if(!STEmpty(&obj->st1))
    {
        return obj->st1.arr[0];
    }
    else
    {
        return obj->st2.arr[0];
    }   
}

bool myQueueEmpty(MyQueue* obj) 
{
    return (STEmpty(&obj->st1)&&STEmpty(&obj->st2));
}

void myQueueFree(MyQueue* obj) 
{
    STDestroy(&obj->st1);
    STDestroy(&obj->st2);
    free(obj);
    obj = NULL;    
}

方法二.

typedef struct 
{
    ST pushst;//插入数据
    ST popst; //删除数据   
} MyQueue;

MyQueue* myQueueCreate() 
{
    MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
    STInit(&obj->pushst);
    STInit(&obj->popst);
    return obj;    
}

void myQueuePush(MyQueue* obj, int x)
{
    //往pushst中插入数据
    STPush(&obj->pushst,x);    
}

int myQueuePop(MyQueue* obj) 
{
    //myQueuePop和 myQueuePeek的整体逻辑是大致相似的，只是多了一步删除，可以直接调用
    int top = myQueuePeek(obj);
    STPop(&obj->popst);
    return top;
}

int myQueuePeek(MyQueue* obj) 
{
    //如果popst为空
    if(STEmpty(&obj->popst))
    {
        //将pushst中的所有数据导入到popst中
        while(!STEmpty(&obj->pushst))
        {
            STPush(&obj->popst,STTop(&obj->pushst));
            STPop(&obj->pushst);
        }
    } 
    //popst为空和不为空，最终要返回的都是popst中的栈顶元素   
    return STTop(&obj->popst);
}

bool myQueueEmpty(MyQueue* obj) 
{
    return STEmpty(&obj->pushst)&&STEmpty(&obj->popst);
}

void myQueueFree(MyQueue* obj)
{
    STDestroy(&obj->pushst);
    STDestroy(&obj->popst);
    free(obj);
    obj = NULL;    
}

题目四.设计循环队列

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

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

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

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

代码： 

typedef struct 
{
    int* arr;//动态数据实现循环队列
    int head;//指向队头
    int tail;//指向队尾数据的下一个
    int k;//k表示最多可存数据的个数,即队列长度,等于 MaxSize - 1   
} MyCircularQueue;

MyCircularQueue* myCircularQueueCreate(int k) 
{
    MyCircularQueue* pq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));  
    //多开一个空间解决空和满冲突的问题
    pq->arr = (int*)malloc(sizeof(int)*(k+1));
    pq->head = pq->tail = 0;
    pq->k = k;
    return pq;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) 
{
    return obj->head == obj->tail;//head == tail    
}

bool myCircularQueueIsFull(MyCircularQueue* obj) 
{
    return (obj->tail+1)%(obj->k+1) == obj->head;//head=（tail+1）%MaxSize    
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) 
{
    if(myCircularQueueIsFull(obj))
    {
        return false;
    } 
    else
    {
        obj->arr[obj->tail++] = value; 
    }   
    //若tail超出了所分配的队列空间，即走到了数组下标为k+1的位置，则要回到起点
    //可以让tail%(k+1),若tail<k+1,则不变,若等于,则tail刚好为0
    obj->tail %= obj->k+1;
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) 
{
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    else
    {
        obj->head++;
        obj->head %= obj->k+1;
        return true;
    }
}

int myCircularQueueFront(MyCircularQueue* obj) 
{
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    else
    {
        return obj->arr[obj->head]; 
    }
   
}

int myCircularQueueRear(MyCircularQueue* obj) 
{
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    } 
    else
    {
        //情况一.tail位于起点，此时队尾在下标为k的地方
        //情况二.tail不在起点，队尾==tail-1
        //写法一.
        return obj->tail == 0?obj->arr[obj->k]:obj->arr[obj->tail-1];
        //写法二.
        //return obj->arr[(obj->tail - 1 + obj->k + 1)%(obj->k + 1)];
        //假设k == 4
        //若 tail == 0,则 (0-1+5)%5 == 4,恰好 == k
        //若 tail != 0,则 (k+1)%(k+1) == 0,二者相互抵消
    }   
    
}

void myCircularQueueFree(MyCircularQueue* obj) 
{
    free(obj->arr);
    obj->arr = NULL;
    obj->head = obj->tail = 0 ;  
    free(obj);
    obj = NULL;  
}