1. 栈1.1 栈的概念及结构栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈，出数据也在栈顶。
栈的结构1.2 栈的实现栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些，因为数组在尾上插入数据的代价比较小。（如果要用单链表，就是在头上插入删除，因为在尾上删除要找尾的前一个节点，很麻烦）
代码语言：javascript复制//Stack.h
#include
#include
#include
#include
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top;
int capacity;
}ST;
void STInit(ST* ps);
void STDestroy(ST* ps);
//栈顶
void STPush(ST* ps, STDataType x);
void STPop(ST* ps);
STDataType STTop(ST* ps);
int STSize(ST* ps);
bool STEmpty(ST* ps);代码语言：javascript复制//Stack.c
#include "Stack.h"
void STInit(ST* ps)
{
assert(ps);
ps->a = NULL;
ps->top = 0;//top指向栈顶元素的下一个
//ps->top = -1;//top指向栈顶元素
ps->capacity = 0;
}
void STDestroy(ST* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->top = ps->capacity = 0;
}
//栈顶
void STPush(ST* ps, STDataType x)
{
assert(ps);
//满了，扩容
if (ps->top == ps->capacity)
{
int newcapacity = 0 == ps->capacity ? 4 : 2 * ps->capacity;
STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
if (NULL == tmp)
{
perror("realloc fail");
return;
}
ps->a = tmp;
ps->capacity = newcapacity;
}
ps->a[ps->top] = x;
ps->top++;
}
void STPop(ST* ps)
{
assert(ps);
assert(!STEmpty(ps));
ps->top--;
}
STDataType STTop(ST* ps)
{
assert(ps);
assert(!STEmpty(ps));
return ps->a[ps->top - 1];
}
int STSize(ST* ps)
{
assert(ps);
return ps->top;
}
bool STEmpty(ST* ps)
{
assert(ps);
return 0 == ps->top;
}代码语言：javascript复制//test.c
#include "Stack.h"
int main()
{
ST s;
STInit(&s);
STPush(&s, 1);
STPush(&s, 2);
STPush(&s, 3);
STPush(&s, 4);
STPush(&s, 5);
while (!STEmpty(&s))
{
int top = STTop(&s);
printf("%d ", top);
STPop(&s);
}
STDestroy(&s);
return 0;
}注：
栈的用途有很多，只要满足后进先出原则的基本都要用到栈在递归改成非递归时，也可以用到栈深度优先遍历（dfs）可以用递归，也可以用栈这里的栈和之前讲过的内存区域划分里的栈区是两个东西，几乎没有什么关联2. 队列2.1 队列的概念及结构队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头
队列队列的功能：保障公平性的排队（比如抽号机）；广度优先遍历（bfs）
2.2 队列的实现队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。
首先定义一下队列节点的结构体：
代码语言：javascript复制typedef int QDataType;
typedef struct QueueNode
{
QDataType val;
struct QueueNode* next;
}QNode;接着是入队列和出队列：
代码语言：javascript复制//入队列
void QueuePush(QNode** pphead, QDataType x);
//出队列
void QueuePop(QNode** pphaed);如果这样写你会发现每次入队列都要找尾，很麻烦，所以我们可以再定义一个尾结点指针：
代码语言：javascript复制//入队列
void QueuePush(QNode** pphead, QNode** pptail, QDataType x);
//出队列
void QueuePop(QNode** pphaed, QNode** pptail);当我们传多个参数时，我们可以把它们定义成一个结构体再进行传参：
代码语言：javascript复制typedef struct Queue
{
QNode* phead;
QNode* ptail;
int size;
}Queue;
//入队列
void QueuePush(Queue* pq, QDataType x);
//出队列
void QueuePop(Queue* pq);这样写同时还把二级指针变成了一级指针。
这时有小伙伴就会问了：当时学习单链表的时候为什么就传一个头节点指针，而不传尾节点指针呢？
这是因为单链表不仅要实现尾插，还要实现尾删，有了尾节点依然找不到尾节点的前一个节点来实现尾删的操作，所以就没必要传尾节点的指针了。
而队列只需要实现尾插和头删，有了尾节点指针就可以很好的避免遍历链表找尾的操作，时间复杂度变低了，因此我们要传尾节点指针。
解决了这个问题之后，我们完整的把队列需要实现的功能列出来：
代码语言：javascript复制#include
#include
#include
#include
typedef int QDataType;
typedef struct QueueNode
{
QDataType val;
struct QueueNode* next;
}QNode;
typedef struct Queue
{
QNode* phead;
QNode* ptail;
int size;
}Queue;
void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
//入队列
void QueuePush(Queue* pq, QDataType x);
//出队列
void QueuePop(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);代码语言：javascript复制#include "Queue.h"
void QueueInit(Queue* pq)
{
assert(pq);
pq->phead = NULL;
pq->ptail = NULL;
pq->size = 0;
}
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->phead;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->phead = pq->ptail = NULL;
pq->size = 0;
}
//入队列
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (NULL == newnode)
{
perror("malloc fail");
return;
}
newnode->val = x;
newnode->next = NULL;
if (pq->ptail)
{
pq->ptail->next = newnode;
pq->ptail = newnode;
}
else
{
pq->phead = pq->ptail = newnode;
}
pq->size++;
}
//出队列
void QueuePop(Queue* pq)
{
assert(pq);
//0个节点
//温柔检查
//if (NULL == pq->phead)
//{
// return;
//}
//暴力检查
assert(pq->phead != NULL);
//一个节点
//多个节点
if (NULL == pq->phead->next)
{
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 != NULL);
return pq->phead->val;
}
QDataType QueueBack(Queue* pq)
{
assert(pq);
//暴力检查
assert(pq->ptail != NULL);
return pq->ptail->val;
}
bool QueueEmpty(Queue* pq)
{
assert(pq);
return 0 == pq->size;
}
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}代码语言：javascript复制#include "Queue.h"
int main()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
while (!QueueEmpty(&q))
{
printf("%d ", QueueFront(&q));
QueuePop(&q);
}
QueueDestroy(&q);
return 0;
}3. 栈和队列面试题括号匹配问题
括号匹配问题代码语言：javascript复制#include
#include
#include
#include
typedef char STDataType;
typedef struct Stack
{
STDataType* a;
int top;
int capacity;
}ST;
void STInit(ST* ps)
{
assert(ps);
ps->a = NULL;
ps->top = 0;
ps->capacity = 0;
}
void STDestroy(ST* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->top = ps->capacity = 0;
}
void STPush(ST* ps, STDataType x)
{
assert(ps);
if (ps->top == ps->capacity)
{
int newcapacity = 0 == ps->capacity ? 4 : 2 * ps->capacity;
STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
if (NULL == tmp)
{
perror("realloc fail");
return;
}
ps->a = tmp;
ps->capacity = newcapacity;
}
ps->a[ps->top] = x;
ps->top++;
}
bool STEmpty(ST* ps)
{
assert(ps);
return 0 == ps->top;
}
void STPop(ST* ps)
{
assert(ps);
assert(!STEmpty(ps));
ps->top--;
}
STDataType STTop(ST* ps)
{
assert(ps);
assert(!STEmpty(ps));
return ps->a[ps->top - 1];
}
int STSize(ST* ps)
{
assert(ps);
return ps->top;
}
bool isValid(char* s)
{
ST st;
STInit(&st);
while (*s)
{
if ('[' == *s || '(' == *s || '{' == *s)
{
STPush(&st, *s);
}
else
{
//右括号比左括号多
if (STEmpty(&st))
{
STDestroy(&st);//在返回前释放动态申请的空间，防止内存泄漏
return false;
}
char top = STTop(&st);
STPop(&st);
//符号不匹配
if (('[' == top && *s != ']')
|| ('(' == top && *s != ')')
|| ('{' == top && *s != '}'))
{
STDestroy(&st);//在返回前释放动态申请的空间，防止内存泄漏
return false;
}
}
++s;
}
//左括号比右括号多，栈不为空
bool ret = STEmpty(&st);
STDestroy(&st);
return ret;
}用队列实现栈
用队列实现栈代码语言：javascript复制#include
#include
#include
#include
typedef int QDataType;
typedef struct QueueNode
{
QDataType val;
struct QueueNode* next;
}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* cur = pq->phead;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->phead = pq->ptail = NULL;
pq->size = 0;
}
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (NULL == newnode)
{
perror("malloc fail");
return;
}
newnode->val = x;
newnode->next = NULL;
if (pq->phead)
{
pq->ptail->next = newnode;
pq->ptail = newnode;
}
else
{
pq->phead = pq->ptail = newnode;
}
pq->size++;
}
void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->phead != NULL);
if (NULL == pq->phead->next)
{
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 != NULL);
return pq->phead->val;
}
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(pq->ptail != NULL);
return pq->ptail->val;
}
bool QueueEmpty(Queue* pq)
{
assert(pq);
return 0 == pq->size;
}
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}
typedef struct
{
Queue q1;
Queue q2;
} MyStack;
MyStack* myStackCreate()
{
MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
QueueInit(&pst->q1);
QueueInit(&pst->q2);
return pst;
}
void myStackPush(MyStack* obj, int x)
{
if (!QueueEmpty(&obj->q1))
{
QueuePush(&obj->q1, x);
}
else
{
QueuePush(&obj->q2, x);
}
}
int myStackPop(MyStack* obj)
{
//不为空前n-1导入另一个队列，删掉最后一个
Queue* pEmptyQ = &obj->q1;
Queue* pNonEmptyQ = &obj->q2;
if (!QueueEmpty(&obj->q1))
{
pEmptyQ = &obj->q2;
pNonEmptyQ = &obj->q1;
}
//不为空前n-1导入另一个空队列
while (QueueSize(pNonEmptyQ) > 1)
{
int front = QueueFront(pNonEmptyQ);
QueuePush(pEmptyQ, front);
QueuePop(pNonEmptyQ);
}
int front = QueueFront(pNonEmptyQ);
QueuePop(pNonEmptyQ);
return front;
}
int myStackTop(MyStack* obj)
{
if (!QueueEmpty(&obj->q1))
{
return QueueBack(&obj->q1);
}
else
{
return QueueBack(&obj->q2);
}
}
bool myStackEmpty(MyStack* obj)
{
return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}
void myStackFree(MyStack* obj)
{
QueueDestroy(&obj->q1);
QueueDestroy(&obj->q2);
free(obj);
}用栈实现队列
用栈实现队列代码语言：javascript复制#include
#include
#include
#include
typedef char STDataType;
typedef struct Stack
{
STDataType* a;
int top;
int capacity;
}ST;
void STInit(ST* ps)
{
assert(ps);
ps->a = NULL;
ps->top = 0;
ps->capacity = 0;
}
void STDestroy(ST* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->top = ps->capacity = 0;
}
void STPush(ST* ps, STDataType x)
{
assert(ps);
if (ps->top == ps->capacity)
{
int newcapacity = 0 == ps->capacity ? 4 : 2 * ps->capacity;
STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
if (NULL == tmp)
{
perror("realloc fail");
return;
}
ps->a = tmp;
ps->capacity = newcapacity;
}
ps->a[ps->top] = x;
ps->top++;
}
bool STEmpty(ST* ps)
{
assert(ps);
return 0 == ps->top;
}
void STPop(ST* ps)
{
assert(ps);
assert(!STEmpty(ps));
ps->top--;
}
STDataType STTop(ST* ps)
{
assert(ps);
assert(!STEmpty(ps));
return ps->a[ps->top - 1];
}
int STSize(ST* ps)
{
assert(ps);
return ps->top;
}
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)
{
STPush(&obj->pushst, x);
}
int myQueuePeek(MyQueue* obj)
{
if (STEmpty(&obj->popst))
{
//pushst的数据导入到popst
while (!STEmpty(&obj->pushst))
{
int top = STTop(&obj->pushst);
STPop(&obj->pushst);
STPush(&obj->popst, top);
}
}
return STTop(&obj->popst);
}
int myQueuePop(MyQueue* obj)
{
int front = myQueuePeek(obj);
STPop(&obj->popst);
return front;
}
bool myQueueEmpty(MyQueue* obj)
{
return STEmpty(&obj->pushst) && STEmpty(&obj->popst);
}
void myQueueFree(MyQueue* obj)
{
STDestroy(&obj->popst);
STDestroy(&obj->pushst);
free(obj);
}注： 在定义队列结构体时，如果里面定义成ST* pushst ，那么下面的初始化就会出现问题，因为malloc队列结构体的时候只开辟了两个指针的空间，这两个指针是野指针；而如果定义的是ST pushst，那么开辟的就是栈结构体的空间，取它的地址进行初始化是没有问题的。如果要用ST* pushst定义，可以先malloc一块空间给pushst，然后再调用STInit函数。（同理，上面的第二题也是这个道理）
设计循环队列
设计循环队列（1）设计循环队列（2）设计循环队列（3）代码语言：javascript复制#include
#include
#include
typedef struct
{
int* a;
int front;//指向头
int rear;//指向尾下一个
int k;
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k)
{
MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
//多开一个解决假溢出问题
obj->a = (int*)malloc(sizeof(int) * (k + 1));
obj->front = 0;
obj->rear = 0;
obj->k = k;
return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{
return obj->front == obj->rear;
}
bool myCircularQueueIsFull(MyCircularQueue* obj)
{
//int rearNext = obj->rear + 1;
//if (rearNext == obj->k + 1)
//{
// rearNext = 0;
//}
//return rearNext == obj->front;
return (obj->rear + 1) % (obj->k + 1) == obj->front;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{
if (myCircularQueueIsFull(obj))
{
return false;
}
obj->a[obj->rear] = value;
obj->rear++;
obj->rear %= (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;
}
else
{
return obj->a[obj->front];
}
}
int myCircularQueueRear(MyCircularQueue* obj)
{
if (myCircularQueueIsEmpty(obj))
{
return -1;
}
else
{
return obj->a[(obj->rear - 1 + obj->k + 1) % (obj->k + 1)];
}
}
void myCircularQueueFree(MyCircularQueue* obj)
{
free(obj->a);
obj->a = NULL;
free(obj);
}4. 概念选择题 一个栈的初始状态为空，现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是（ ）
A. 12345ABCDE
B. EDCBA54321
C. ABCDE12345
D. 54321EDCBA
答案：B
若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（ ）
A. 1,4,3,2
B. 2,3,4,1
C. 3,1,4,2
D. 3,4,2,1
答案：C