目录

1.栈

1.1栈的概念及结构

1.2栈的实现：

2.队列

2.1队列的概念及结构

2.2队列的实现

3.经典OJ题

3.1有效括号

3.2 用队列实现栈   

3.3 用栈实现队列

3.4设计循环队列

1.栈

1.1栈的概念及结构

栈：一种特殊的线性表。其只允许在固定的的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端成为栈底。栈中的数据元素遵守后进先出或先进后出LIFO（Last In First Out）的原则。

压栈：栈大的插入操作叫做进栈压栈入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据也在栈顶。

栈实现的两种方式： 两种都可以，非要选一种数组栈结构稍微好一点。

数组栈：尾插尾删效率高，缓存率还高。

链式栈：如果使用尾做栈顶，尾插尾删，要设计成双向链表，否则删除数据效率低。如果用头做栈顶，头插头删，就可以设计成单链表。

1.2栈的实现：

1.声明栈的所有函数Stack.h：

#include 
#include 
#include 

typedef int STDataType;

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

void StackInit(Stack*ps);//栈初始化
void StackPush(Stack* ps, STDataType data);//入栈
void StackPop(Stack* ps);//出栈
STDataType StackTop(Stack* ps);//获取栈顶的数据
int StackSize(Stack* ps);//获取栈的有效元素个数
int StackEmpty(Stack* ps);//检测栈是否为空。空为1，不空为0
void StackDestory(Stack* ps);//栈销毁

2.栈的初始化：

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

初始化理解图： 

ps是一个结构体指针变量，存的是ST变量的地址，ST是一个结构体变量，含有一个指针和两个整数。

3.栈入数据：

void StackPush(Stack* ps, STDataType data)
{
    assert(ps);

    //当capacity==top时，就会扩容
	if (ps->capacity == ps->top)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		int* temp = (int* )realloc(ps->a,sizeof(Stack)* newcapacity);
		if (temp == NULL)
		{
			//开辟失败
			printf("动态申请失败n");
			exit(-1);
		}
		ps->a = temp;
		ps->capacity = newcapacity;
	}

    //数据入栈
	ps->a[ps->top] = data;
	ps->top++;

}

注意：1.realloc 在pa->a(第一个参数)为空时，可以当作malloc来使用。

           2.当capacity==0时，会先开辟4个空间的大小，capacity不为0时，扩大原来空间的2倍，即8个空间

           3.入数据就是在数组的top位置上插入数据。

4.取栈顶数据与出栈是一起使用的，才符合栈的性质。也就是出栈。

1.取栈顶数据

STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->a[ps->top - 1];
}

2.出栈

出栈不需要将数据复位为0，下次再插入数据时，就直接覆盖了原来的数据。

void StackPop(Stack* ps)
{
    assert(ps);
    assert(!StackEmpty(ps));
	ps->top--;
}

5.获取栈的有效元素个数 

top保存是最后一个有效数据的后面的数字。

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

6.检测栈是否为空

为空返回1，不为空返回0

int StackEmpty(Stack* ps)
{
    assert(ps);
	return ps->top == 0;
}

7.栈的销毁

void StackDestory(Stack* ps)
{
    assert(ps);
	free(ps->a);
	ps->capacity = ps->top = 0;
}

8.测试

#include "Stack.h"

int main()
{

	Stack ST;
	StackInit(&ST);
	StackPush(&ST,1);
	StackPush(&ST,2);
	StackPush(&ST,3);
	StackPush(&ST,4);
	StackPush(&ST, 5);
	while (!StackEmpty(&ST))
	{
		printf("%d ", StackTop(&ST));
		StackPop(&ST);
	}
	
	StackEmpty(&ST);

	return 0;
}

结果：符合栈的先进后出原则。

入栈从栈顶入，过程： 

 出栈从栈顶出， 过程：

2.队列

2.1队列的概念及结构

队列：只允许在一端进行插入数据操作，在另一端及逆行删除数据操作的特殊线性表，队列具有先进先出。入队列：进行插入操作的一端称为队尾，出队列:进行删除操作的一端称为队头。

2.2队列的实现

队列使用链表更加适合

1.队列的头文件Queue.h

#include
#include
#include 

typedef int QDataType;
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QNode;


typedef struct Queue
{
	QNode* front;
	QNode* tail;
}Queue;

void QueueInit(Queue* q);//队列初始化
void QueuePush(Queue* q, QDataType x);//入队列
void QueuePrint(Queue* q);//打印队列
void QueuePop(Queue* q);//出队列
QDataType QueueFront(Queue* q);//获取队列头数据
QDataType QueueBack(Queue* q);//获取队尾元素
void QueueDestory(Queue* q);//销毁队列
int QueueEmpty(Queue* q);//队列是否为空
int QueueSize(Queue* q);//队列元素个数

2.队列的初始化

void QueueInit(Queue* q)
{
	assert(q);
	q->front =q->tail = NULL;
}

3.入队列

void QueuePush(Queue* q, QDataType x)
{
	assert(q);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		printf("动态申请失败n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;

	if (q->front == NULL)
	{
		q->tail=q->front = newnode;
	}
	else
	{
		q->tail->next = newnode;
		q->tail = newnode;
	}

}

4.出队列

void QueuePop(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	QNode* next = q->front->next;
	free(q->front);
	q->front = next;
	if (q->front == NULL)
	{
		q->tail = NULL;//防止野指针。
	}
}

5.获取队列头数据

QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->front->data;
}

6.获取队尾数据

QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->tail->data;
}

7.获取有效数据个数

int QueueSize(Queue* q)
{
	assert(q);
	QNode* temp = q->front;
	int count = 0;
	while (temp!=NULL)
	{
		count++;
		temp = temp->next;
	}
	return count;
}

8.检测队列是否为空

int QueueEmpty(Queue* q)
{
	assert(q);
	return q->front == NULL;
}

9. 队列销毁

void QueueDestory(Queue* q)
{
	assert(q);
	QNode* temp = q->front;
	while (temp != NULL)
	{
		QNode* next = temp->next;
		free(temp);
		temp = next;
	}
	q->front = q->tail = NULL;
}

代码测试：

#include "Queue.h"


int main()
{
	Queue queue;
	QueueInit(&queue);
	QueuePush(&queue,1);
	QueuePush(&queue,2);
	QueuePush(&queue,3);
	QueuePush(&queue,4);
	QueuePush(&queue,5);
	//获取队头数据
	printf("队头数据为：%dn", QueueFront(&queue));
	QueuePop(&queue);//队列出一次数据

	QueuePush(&queue, 6);

	QueuePrint(&queue);
	return 0;
}

结果：

过程：

1.入数据就是在队尾插入数据：

2.获取队头数据并出队列

 3.插入6数据入队列

3.经典OJ题

3.1有效括号

力扣https://leetcode-cn.com/problems/valid-parentheses/本题思路：把栈的程序复制到上边，当字符是左括号，就入栈，当是右括号时，就出栈。当匹配时，就返回true,不匹配时，就返回false。

OJ代码实现： 

bool isValid(char * s){
    Stack st;
    StackInit(&st);

    while(*s!='')
    {
        if(*s=='('||*s=='['||*s=='{')
        {
           StackPush(&st,*s);
           
        }
        else 
        {
            //防止只有一个右括号
          if(StackEmpty(&st))
            {
                StackDestory(&st);
                return false;
            }
          STDataType temp=StackTop(&st);
          StackPop(&st);
          if((temp=='(' && *s!=')' )|| (temp=='['&& *s!=']')|| (temp=='{' && *s!='}'))
          {
              StackDestory(&st);
              return false;
          }

        }
        s++;
    }
//若栈不为空，则就不匹配
    if(!StackEmpty(&st))
    {
        StackDestory(&st);
        return false;
    }


    StackDestory(&st);
    return true;

3.2 用队列实现栈   

力扣https://leetcode-cn.com/problems/implement-stack-using-queues/submissions/主要思想是：利用两个队列来实现栈的先进后出，比如我在队列1里入了五个数据1，2，3，4，5此时我想实现栈，也就是需要先取数据5，此时需要将1，2，3，4入到队列2中去，使得队列1只剩下5，然后取队列1的头数据，并出队列，此时便完成了栈的后进先出，下一次就是反过来也就是队列2的数据入队列1，只剩下最后一个数据，直到两个队列都为空。若是入数据就向非空的队列中入数据，也就是入队列。

初始化后的结构：

 入数据后的结构：

OJ代码实现： 

typedef struct {
    Queue q1;
    Queue q2;
} MyStack;


MyStack* myStackCreate() {
    MyStack*st=(MyStack*)malloc(sizeof(MyStack));
    QueueInit(&st->q1);
    QueueInit(&st->q2);
    return st;
}

void myStackPush(MyStack* obj, int x) {
   if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }
    else
    {
        QueuePush(&obj->q2,x);
    }

}

int myStackPop(MyStack* obj) {
    Queue* empty=&obj->q1;
    Queue* nonempty=&obj->q2;
    if(QueueEmpty(nonempty))
    {
        Queue* temp=empty;
        empty=nonempty;
        nonempty=temp;
    }
    while(QueueSize(nonempty)>1)
    {
     QueuePush(empty,QueueFront(nonempty));
     QueuePop(nonempty);
    }
    int temp=QueueFront(nonempty);
    QueuePop(nonempty);
    return temp;
}

int myStackTop(MyStack* obj) {

    Queue* empty=&obj->q1;
    Queue* nonempty=&obj->q2;
    if(QueueEmpty(nonempty))
    {
        Queue* temp=empty;
        empty=nonempty;
        nonempty=temp;
    }
   return  QueueBack(nonempty);

}

bool myStackEmpty(MyStack* obj) {
 
    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

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

3.3 用栈实现队列

力扣https://leetcode-cn.com/problems/implement-queue-using-stacks/

 主要思想：利用两个栈，完成队列的先进先出的性质。

代码实现： 

typedef struct {
    Stack st1;//存数据的栈
    Stack st2;//出数据的栈

} MyQueue;


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

void myQueuePush(MyQueue* obj, int x) {
    StackPush(&obj->st1,x);//入数据就向栈1入数据
}

int myQueuePop(MyQueue* obj) {
     if(StackEmpty(&obj->st2))//只有栈2 为空时才能将栈1的数据入栈2
    {
        while(!StackEmpty(&obj->st1))
        {
            StackPush(&obj->st2,StackTop(&obj->st1)); //栈2为空将栈1的所有数据依次出栈
            StackPop(&obj->st1);
        }
    }
        int top=StackTop(&obj->st2);
        StackPop(&obj->st2);
        return top;
}

int myQueuePeek(MyQueue* obj) {
      if(StackEmpty(&obj->st2))//只有栈2 为空时才能将栈1的数据入栈2
    {
        while(!StackEmpty(&obj->st1))
        {
            StackPush(&obj->st2,StackTop(&obj->st1)); //栈2为空将栈1的所有数据依次出栈
            StackPop(&obj->st1);
        }
    }
     int top=StackTop(&obj->st2);
     return top;

}

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

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

3.4设计循环队列

力扣https://leetcode-cn.com/problems/design-circular-queue/

重点：循环队列，无论使用数组实现还是链表实现，都要多开一个空间，也就意味着，要是一个存k个数据的循环队列，要开k+1个空间否则无法实现判空和判满。链表和数组都可以实现。

多开一个空间的原因：

1.无法判满还是判空：

2.解决判空和判满 

本代码使用数组实现循环队列：

typedef struct {
    int *a;
    int front;
    int tail;
    int k;

} MyCircularQueue;

bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);

MyCircularQueue* myCircularQueueCreate(int k) {
     MyCircularQueue*cq=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
     cq->a=(int* )malloc(sizeof(int)*(k+1));
     cq->front=0;
     cq->tail=0;
     cq->k=k;
     return cq;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))
    {
        return false;
    }
    obj->a[obj->tail++]=value;

    (obj->tail)%=(obj->k+1);
    
    return true;
}

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

int myCircularQueueFront(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
   {
       return -1;
   } 
   return obj->a[obj->front];
}

int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
       return -1;
    } 
    
    return obj->a[(obj->tail+obj->k)%(obj->k+1)];
          
}

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

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return  (obj->tail+1)%(obj->k+1) ==obj->front;
}

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(obj);
}