目录

1.栈

1.1栈的概念及结构

1.2栈的实现

 1.2.1、数组实现栈结构

1.2.2、初始化栈void StackInit(Stack* ps);

1.2.3、栈的销毁void StackDestroy(Stack* ps)

1.2.4、入栈void StackPush(Stack* ps, STDataType x)

1.2.5、出栈void StackPop(Stack* ps)

1.2.6、获取栈顶元素STDataType StackTop(Stack* ps)

1.2.7、检测栈是否为空，如果为空返回true，如果不为空返回false bool StackEmpty(Stack* ps)

2.队列

2.1队列的概念及结构

2.2队列queue的实现

3.栈和队列面试题

1. 括号匹配问题。

2. 用队列实现栈。

3. 用栈实现队列。

4. 设计循环队列。

4.概念选择题

1.栈

1.1栈的概念及结构

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端 称为栈顶，另一端称为栈底。

栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

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

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

1.2栈的实现

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。

 1.2.1、数组实现栈结构

//下面是定长的静态栈的结构，实际中一般不实用，
//所以我们主要实现下面的支持动态增长的栈
//#define N 10
//typedef int STDataType;
//typedef struct Stack
//{
//	STDataType data[N];
//	int top;
//	int capacity;
//}Stack;// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{STDataType* data;int top;			//栈顶int capacity;		//容量
}Stack;

1.2.2、初始化栈
void StackInit(Stack* ps);

//初始化栈
void StackInit(Stack* ps)
{assert(ps);ps->data = NULL;ps->top = 0;ps->capacity = 0;
}

1.2.3、栈的销毁
void StackDestroy(Stack* ps)

//栈的销毁
void StackDestroy(Stack* ps)
{assert(ps);free(ps->data);ps->data = NULL;ps->top = ps->capacity = 0;
}

1.2.4、入栈
void StackPush(Stack* ps, STDataType x)

void StackPush(Stack* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;STDataType* tmp = (STDataType*)realloc(ps->data, sizeof(STDataType) * newcapacity);if (tmp == NULL){printf("realloc fail\n");exit(-1);}ps->data = tmp;ps->capacity = newcapacity;}ps->data[ps->top] = x;++ps->top;
}

1.2.5、出栈
void StackPop(Stack* ps)

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

1.2.6、获取栈顶元素
STDataType StackTop(Stack* ps)

//获取栈顶元素
STDataType StackTop(Stack* ps)
{assert(ps);assert(!StackEmpty(ps));return ps->data[ps->top - 1];
}

1.2.7、检测栈是否为空，如果为空返回true，如果不为空返回false 
bool StackEmpty(Stack* ps)

// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
bool StackEmpty(Stack* ps)
{assert(ps);if (ps->top == 0){return true;}return false;
}

2.队列

2.1队列的概念及结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头

2.2队列queue的实现

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数 组头上出数据，效率会比较低。

#pragma once
#include
#include
#include
#include
// 链式结构：表示队列
typedef int QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType data;}QNode;
//队列结构
typedef struct Queue
{QNode* head;QNode* tail;//int size;
}Queue;// 初始化队列
void QueueInit(Queue* pq);
// 销毁队列
void QueueDestroy(Queue* pq);// 队尾入队列
void QueuePush(Queue* pq, QDataType data);
// 队头出队列
void QueuePop(Queue* pq);// 获取队列头部元素
QDataType QueueFront(Queue* pq);
// 获取队列队尾元素
QDataType QueueBack(Queue* pq);// 获取队列中有效元素个数
int QueueSize(Queue* pq);
// 检测队列是否为空，如果为空true，如果非空false 
bool QueueEmpty(Queue* pq);

#include"Queue.h"// 初始化队列
void QueueInit(Queue* pq)
{assert(pq);pq->head = pq->tail = NULL;
}
// 销毁队列
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->head;while (cur){pq->head = pq->head->next;free(cur);cur = pq->head;}pq->head = pq->tail = NULL;
}// 队尾入队列
void QueuePush(Queue* pq, QDataType data)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){printf("malloc fail\n");exit(-1);}newnode->data = data;newnode->next = NULL;if (pq->tail == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}
}
// 队头出队列
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq->head->next == NULL){pq->tail = NULL;}QNode* del = pq->head;pq->head = pq->head->next;free(del);del = NULL;
}// 获取队列头部元素
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;}
// 获取队列队尾元素
QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}// 获取队列中有效元素个数
int QueueSize(Queue* pq)
{assert(pq);QNode* cur = pq->head;int size = 0;while (cur){size++;cur = cur->next;}return size;
}// 检测队列是否为空，如果为空true，如果非空false 
bool QueueEmpty(Queue* pq)
{assert(pq);if (pq->head == NULL){return true;}return false;
}

另外扩展了解一下，实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型 时可以就会使用循环队列。环形队列可以使用数组实现，也可以使用循环链表实现。

3.栈和队列面试题

1. 括号匹配问题。

Loading Question... - 力扣（LeetCode）https://leetcode.cn/problems/valid-parentheses/

 左括号入栈，右括号出栈

// 支持动态增长的栈
typedef char STDataType;
typedef struct Stack
{STDataType* data;int top;			//栈顶int capacity;		//容量
}Stack;//初始化栈
void StackInit(Stack* ps);//栈的销毁
void StackDestroy(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 StackInit(Stack* ps)
{assert(ps);ps->data = NULL;ps->top = 0;ps->capacity = 0;
}//栈的销毁
void StackDestroy(Stack* ps)
{assert(ps);free(ps->data);ps->data = NULL;ps->top = ps->capacity = 0;
}//入栈
void StackPush(Stack* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;STDataType* tmp = (STDataType*)realloc(ps->data, sizeof(STDataType) * newcapacity);if (tmp == NULL){printf("realloc fail\n");exit(-1);}ps->data = tmp;ps->capacity = newcapacity;}ps->data[ps->top] = x;++ps->top;
}
//出栈
void StackPop(Stack* ps)
{assert(ps);assert(!StackEmpty(ps));ps->top--;
}//获取栈顶元素
STDataType StackTop(Stack* ps)
{assert(ps);assert(!StackEmpty(ps));return ps->data[ps->top - 1];
}// 获取栈中有效元素个数
int StackSize(Stack* ps)
{assert(ps);return ps->top;
}// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
bool StackEmpty(Stack* ps)
{assert(ps);if (ps->top == 0){return true;}return false;
}bool isValid(char * s){Stack sk;StackInit(&sk);while(*s){if(*s == '(' || *s == '{' || *s == '['){StackPush(&sk,*s);++s;}else{if(StackEmpty(&sk)){StackDestroy(&sk);return false;}STDataType top1 = StackTop(&sk);StackPop(&sk);if(top1 == '{' && *s == '}'||top1 == '[' && *s == ']'||top1 == '(' && *s == ')'){++s;}else{StackDestroy(&sk);return false;}}}bool ret = StackEmpty(&sk);StackDestroy(&sk);return ret;
}

2. 用队列实现栈。

利用两个队列，实现栈：

1. 由于队列先进先出，栈先进后出，
2. 因此当入栈时，使其入一个队列
3. 出栈时，将不为空的队列前 n -1 个元素入到空队列，此时不为空的队列变为栈顶元素，进行出队，即出栈 
4. 获取栈顶元素，只需要返回不为空队列的队尾
5. 判断栈是否为空只需要判断两队列是否为空
6. 栈的销毁，首先销毁两个队列，其次销毁栈区

225. 用队列实现栈 - 力扣（LeetCode）https://leetcode.cn/problems/implement-stack-using-queues/

#include
#include
#include
#include
// 链式结构：表示队列
typedef int QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType data;}QNode;
//队列结构
typedef struct Queue
{QNode* head;QNode* tail;//int size;
}Queue;// 初始化队列
void QueueInit(Queue* pq);
// 销毁队列
void QueueDestroy(Queue* pq);// 队尾入队列
void QueuePush(Queue* pq, QDataType data);
// 队头出队列
void QueuePop(Queue* pq);// 获取队列头部元素
QDataType QueueFront(Queue* pq);
// 获取队列队尾元素
QDataType QueueBack(Queue* pq);// 获取队列中有效元素个数
int QueueSize(Queue* pq);
// 检测队列是否为空，如果为空true，如果非空false 
bool QueueEmpty(Queue* pq);// 初始化队列
void QueueInit(Queue* pq)
{assert(pq);pq->head = pq->tail = NULL;
}
// 销毁队列
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->head;while (cur){pq->head = pq->head->next;free(cur);cur = pq->head;}pq->head = pq->tail = NULL;
}// 队尾入队列
void QueuePush(Queue* pq, QDataType data)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){printf("malloc fail\n");exit(-1);}newnode->data = data;newnode->next = NULL;if (pq->tail == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}
}
// 队头出队列
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq->head->next == NULL){pq->tail = NULL;}QNode* del = pq->head;pq->head = pq->head->next;free(del);del = NULL;
}// 获取队列头部元素
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;}
// 获取队列队尾元素
QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}// 获取队列中有效元素个数
int QueueSize(Queue* pq)
{assert(pq);QNode* cur = pq->head;int size = 0;while (cur){size++;cur = cur->next;}return size;
}// 检测队列是否为空，如果为空true，如果非空false 
bool QueueEmpty(Queue* pq)
{assert(pq);if (pq->head == NULL){return true;}return false;
}typedef struct {Queue q1;Queue q2;} MyStack;MyStack* myStackCreate() {MyStack* obj =(MyStack*) malloc(sizeof(MyStack));QueueInit(&obj->q1);QueueInit(&obj->q2);return obj;
}void myStackPush(MyStack* obj, int x) {if(!QueueEmpty(&obj->q1)){QueuePush(&obj->q1,x);}else{QueuePush(&obj->q2,x);}
}int myStackPop(MyStack* obj) {Queue* emptQ = &obj->q1;Queue* nonEmptyQ = &obj->q2;if(!QueueEmpty(&obj->q1)){emptQ = &obj->q2;nonEmptyQ = &obj->q1;}while(QueueSize(nonEmptyQ) > 1 ){QueuePush(emptQ,QueueFront(nonEmptyQ));QueuePop(nonEmptyQ);}int top = QueueFront(nonEmptyQ);QueuePop(nonEmptyQ);return top;
}int myStackTop(MyStack* obj) {if(!QueueEmpty(&obj->q1)){return QueueBack(&obj->q1);}return QueueBack(&obj->q2);
}bool myStackEmpty(MyStack* obj) {if(QueueEmpty(&obj->q1) == true && QueueEmpty(&obj->q2) == true){return true;}return false;
}void myStackFree(MyStack* obj) {QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);free(obj);obj = NULL;
}/*** 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);
*/

3. 用栈实现队列。

232. 用栈实现队列 - 力扣（LeetCode）https://leetcode.cn/problems/implement-queue-using-stacks/

// 支持动态增长的栈
typedef char STDataType;
typedef struct Stack
{STDataType* data;int top;			//栈顶int capacity;		//容量
}Stack;//初始化栈
void StackInit(Stack* ps);//栈的销毁
void StackDestroy(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 StackInit(Stack* ps)
{assert(ps);ps->data = NULL;ps->top = 0;ps->capacity = 0;
}//栈的销毁
void StackDestroy(Stack* ps)
{assert(ps);free(ps->data);ps->data = NULL;ps->top = ps->capacity = 0;
}//入栈
void StackPush(Stack* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;STDataType* tmp = (STDataType*)realloc(ps->data, sizeof(STDataType) * newcapacity);if (tmp == NULL){printf("realloc fail\n");exit(-1);}ps->data = tmp;ps->capacity = newcapacity;}ps->data[ps->top] = x;++ps->top;
}
//出栈
void StackPop(Stack* ps)
{assert(ps);assert(!StackEmpty(ps));ps->top--;
}//获取栈顶元素
STDataType StackTop(Stack* ps)
{assert(ps);assert(!StackEmpty(ps));return ps->data[ps->top - 1];
}// 获取栈中有效元素个数
int StackSize(Stack* ps)
{assert(ps);return ps->top;
}// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
bool StackEmpty(Stack* ps)
{assert(ps);if (ps->top == 0){return true;}return false;
}typedef struct {Stack pushst;Stack popst;
} MyQueue;MyQueue* myQueueCreate() {MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));StackInit(&obj->pushst);StackInit(&obj->popst);return obj;
}void myQueuePush(MyQueue* obj, int x) {StackPush(&obj->pushst,x);
}int myQueuePop(MyQueue* obj) {if(StackEmpty(&obj->popst)){while(!StackEmpty(&obj->pushst)){StackPush(&obj->popst,StackTop(&obj->pushst));StackPop(&obj->pushst);}}int tmp = StackTop(&obj->popst);StackPop(&obj->popst);return tmp;
}int myQueuePeek(MyQueue* 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) {return StackEmpty(&obj->pushst) && StackEmpty(&obj->popst);}void myQueueFree(MyQueue* obj) {StackDestroy(&obj->pushst);StackDestroy(&obj->popst);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);
*/

4. 设计循环队列。

622. 设计循环队列 - 力扣（LeetCode）https://leetcode.cn/problems/design-circular-queue/

typedef struct {int front;int rear;int * data;int size;int maxsize;
} MyCircularQueue;// 构造
MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* Q = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));Q->data = (int*)malloc(sizeof(int) * k);Q->front = 0;Q->rear = 0;Q->size = 0;Q->maxsize = k;return Q;
}// 入队
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {// 队满if( obj->size == obj->maxsize ){ return 0; }obj->data[obj->rear++] = value;obj->size++;if(obj->rear >= obj->maxsize){obj->rear %= obj->maxsize;}return 1;
}// 出队
bool myCircularQueueDeQueue(MyCircularQueue* obj) {// 队空if( obj->size == 0 ){ return 0; }obj->front = (obj->front + 1) % obj->maxsize;obj->size--;return 1;
}// 取队头
int myCircularQueueFront(MyCircularQueue* obj) {if(obj->size == 0){ return -1; }return obj->data[obj->front];
}int myCircularQueueRear(MyCircularQueue* obj) {if(obj->size == 0){ return -1; }if(obj->rear == 0){return obj->data[obj->maxsize-1];}return obj->data[obj->rear-1];
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return !obj->size;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return obj->size == obj->maxsize;
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj->data);free(obj);
}

4.概念选择题

1.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出
栈的顺序是（ ）。
A 12345ABCDE
B EDCBA54321
C ABCDE12345
D 54321EDCBA2.若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（）
A 1,4,3,2
B 2,3,4,1
C 3,1,4,2
D 3,4,2,13.循环队列的存储空间为 Q(1:100) ，初始状态为 front=rear=100 。经过一系列正常的入队与退队操作
后， front=rear=99 ，则循环队列中的元素个数为（ ）
A 1
B 2
C 99
D 0或者1004.以下( )不是队列的基本运算？
A 从队尾插入一个新元素
B 从队列中删除第i个元素
C 判断一个队列是否为空
D 读取队头元素的值5.现有一循环队列，其队头指针为front，队尾指针为rear；循环队列长度为N。其队内有效长度为？(假设
队头不存放数据)
A (rear - front + N) % N + 1
B (rear - front + N) % N
C ear - front) % (N + 1)
D (rear - front + N) % (N - 1)
1.B
2.C
3.D
4.B
5.B