栈1. 基本概念栈是一种逻辑结构，是特殊的线性表。特殊在：
只能在固定的一端操作只要满足上述条件，那么这种特殊的线性表就会呈现一种“后进先出”的逻辑，这种逻辑就被称为栈。栈在生活中到处可见，比如堆叠的盘子、电梯中的人们、嵌套函数的参数等等。
由于约定了只能在线性表固定的一端进行操作，于是给栈这种特殊的线性表的“插入”、“删除”，另起了下面这些特定的名称：
栈顶：可以进行插入删除的一端栈底：栈顶的对端入栈：将节点插入栈顶之上，也称为压栈，函数名通常为push()出栈：将节点从栈顶剔除，也称为弹栈，函数名通常为pop()取栈顶：取得栈顶元素，但不出栈，函数名通常为top()基于这种固定一端操作的简单约定，栈获得了“后进先出”的基本特性，如下图所示，最后一个放入的元素，最先被拿出来：
2. 存储形式栈只是一种数据逻辑，如何将数据存储于内存则是另一回事。一般而言，可以采用顺序存储形成顺序栈，或采用链式存储形成链式栈。
顺序栈
顺序存储意味着开辟一块连续的内存来存储数据节点，一般而言，管理栈数据除了需要一块连续的内存之外，还需要记录栈的总容量、当前栈的元素个数、当前栈顶元素位置，如果有多线程还需要配互斥锁和信号量等信息，为了便于管理，通常将这些信息统一于在一个管理结构体之中：
struct seqStack
{
datatype *data; // 顺序栈入口
int size; // 顺序栈总容量
int top; // 顺序栈栈顶元素下标
};
链式栈
链式栈的组织形式与链表无异，只不过插入删除被约束在固定的一端。为了便于操作，通常也会创建所谓管理结构体，用来存储栈顶指针、栈元素个数等信息：
// 链式栈节点
typedef struct node
{
datatype data;
struct node *next;
}node;
// 链式栈管理结构体
struct linkStack
{
node *top; // 链式栈栈顶指针
int size; // 链式栈当前元素个数
};
3. 基本操作不管是顺序栈，链式栈，栈的操作逻辑都是一样的，但由于存储形式不同，代码的实现是不同的。下面分别将顺序栈和链式栈的基本核心操作罗列出来：
顺序栈
// 顺序栈管理结构体
typedef struct
{
datatype *data; // 顺序栈入口
int size; // 顺序栈总容量
int top; // 顺序栈栈顶元素下标
}seqStack;
// 初始化空栈
seqStack *initStack(int size)
{
seqStack *s = (seqStack *)malloc(sizeof(seqStack))
if(s != NULL)
{
s->data = (datatype *)malloc(sizeof(datatype) * size));
if(s->data == NULL)
{
free(s);
return NULL;
}
s->size = size;
s->top = -1;
}
return s;
}
// 判断栈是否已满
bool isFull(seqStack *s)
{
return s->top == s->size-1;
}
// 判断栈是否为空
bool isEmpty(seqStack *s)
{
return s->top == -1;
}
// 入栈
bool push(seqStack *s, datatype data)
{
if(isFull(s))
return false;
s->data[++s->top] = data;
return true;
}
// 出栈
bool pop(seqStack *s, datatype *pm)
{
if(top(s, pm) == false)
return false;
s->top--;
return true;
}
// 取栈顶元素
bool top(seqStack *s, datatype *pm)
{
if(isEmpty(s))
return false;
*pm = s->data[s->top];
return true;
}
使用顺序栈，接收键盘的输入，实现如下功能：
输入数字时，依次入栈。输入字母时，依次出栈。每次入栈或者出栈，都将顺序栈中的各个元素输出出来。链式栈
// 链式栈节点
typedef struct node
{
datatype data;
struct node *next;
}node;
// 链式栈管理结构体
typedef struct linkStack
{
node *top; // 链式栈栈顶指针
int size; // 链式栈当前元素个数
}linkStack;
// 初始化空栈
linkStack * initStack(void)
{
linkStack * s = (linkStack *)malloc(sizeof(linkStack));
if(s != NULL)
{
s->top = NULL;
s->size = 0;
}
return s;
}
// 判断栈是否为空
bool isEmpty(linkStack *s)
{
return (s->size == 0);
}
// 入栈
bool push(linkStack *s, datatype data)
{
// 创建链表节点
node *new = (node *)malloc(sizeof(node));
if(new == NULL)
return false;
new->data = data;
// 将节点置入栈顶
new->next = s->top;
s->top = new;
// 更新栈元素个数
s->size++;
return true;
}
// 出栈
bool pop(linkStack *s, datatype *pm)
{
if(isEmpty(s))
return false;
linkStack *tmp = s->top;
// 将原栈顶元素剔除出栈
s->top = tmp->next;
tmp->next = NULL;
// 返回栈顶元素，并释放节点
*pm = tmp->data;
free(tmp);
return true;
}
// 取栈顶元素
bool top(linkStack *s, datatype *pm)
{
if(isEmpty(s))
return false;
// 返回栈顶元素
*pm = s->top->data;
return true;
}
队列1. 基本概念队列是最常见的概念，日常生活经常需要排队，仔细观察队列会发现，队列是一种逻辑结构，是一种特殊的线性表。特殊在：
只能在固定的两端操作线性表只要满足上述条件，那么这种特殊的线性表就会呈现一种“先进先出”的逻辑，这种逻辑就被称为队列。
由于约定了只能在线性表固定的两端进行操作，于是给队列这种特殊的线性表的插入删除，起个特殊的名称：
队头：可以删除节点的一端队尾：可以插入节点的一端入队：将节点插入到队尾之后，函数名通常为enQueue()出队：将队头节点从队列中剔除，函数名通常为outQueue()取队头：取得队头元素，但不出队，函数名通常为front()由于这种固定两端操作的简单约定，队列获得了“先进先出”的基本特性，如下图所示：
2. 顺序存储的队列：循环队列与其他的逻辑结构类似，队列可以采用顺序存储形成循环队列，也可以采用链式存储形成链式队列。顺序存储的队列之所以被称为循环队列，是因为可以利用更新队头队尾的下标信息，来循环地利用整个数组，出队入队时也不必移动当中的数据。循环队列示意图如下所示：
从上述动图中可以观察到，需要牺牲至少数组中的一个存储位置，来区分循环队列中的满队和空队。满队和空队的约定如下：
当front与rear相等时，队列为空当rear循环加一与front相等时，队列为满与其他数据结构一样，管理循环队列除了需要一块连续的内存之外，还需要记录队列的总容量、当前队列的元素个数、当前队头、队尾元素位置，如果有多线程还需要配互斥锁和信号量等信息，为了便于管理，通常将这些信息统一于在一个管理结构体之中：
struct seqQueue
{
datatype *data; // 循环队列入口
int capacity; // 循环队列总容量
int front; // 循环队列队头元素下标
int rear; // 循环队列队头元素下标
};
循环队列的基本操作
// 初始化空队列
seqQueue * initQueue(int cap)
{
*pq = (sequeue *)malloc(sizeof(sequeue));
(*pq)->front = (*pq)->rear = MAXSIZE - 1;
}
// 判断队列是否为空
bool isEmpty(seqQueue *q)
{
return q->front == q->rear;
}
// 判断队列是否已满
bool isFull(seqQueue *q)
{
return (q->rear+1)%q->capacity == q->front;
}
// 出队
bool outQueue(seqQueue *q, datatype *pm)
{
if(isEmpty(q))
return false;
*pm = q->data[q->front];
q->front = (q->front + 1) % q->capacity;
return true;
}
// 入队
bool enQueue(seqQueue *q, datatype data)
{
if(isFull(q))
return false;
q->data[q->rear] = data;
q->rear = (q->rear + 1) % q->capacity;
return true;
}
注意：
循环队列中，需要牺牲一个存储位置来区分空队和满队
3. 链式存储的队列：链式队列链式队列的组织形式与链表无异，只不过插入删除被约束在固定的两端。为了便于操作，通常也会创建所谓管理结构体，用来存储队头指针、队尾指针、队列元素个数等信息：
从上图可以看到，链式队列主要控制队头和队尾，由于管理结构体中保存了当前队列元素个数size，因此可以不必设计链表的头节点，初始化空队列时只需要让队头队尾指针同时指向空即可。
以下是队列链表节点设计和管理结构体设计的示例代码：
// 链式队列节点
typedef struct node
{
datatype data;
struct node *next;
}node;
// 链式队列管理结构体
typedef struct
{
node *front; // 队头指针
node *rear; // 队尾指针
int size; // 队列当前元素个数
}linkQueue;
链式队列的基本操作
// 初始化空队列
linkQueue *initQueue()
{
linkQueue *q = (linkQueue *)malloc(sizeof(linkQueue))
if(q != NULL)
{
q->front = NULL;
q->rear = NULL;
q->size = 0;
}
return q;
}
// 判断队列是否为空
bool isEmpty(linkQueue *q)
{
return q->size == 0;
}
// 入队
bool enQueue(linkQueue *q, datatype data)
{
// 创建新节点
node *new = malloc(sizeof(node));
if(new == NULL)
return false;
new->data = data;
new->next = NULL;
// 入队分两种情况：
// 1. 当前队列为空，则新节点是队列的唯一节点
if(isEmpty(q))
q->front = q->rear = new;
// 2. 否则队列不为空，将新节点拼接到队尾之后
else
{
q->rear->next = new;
q->rear = new;
}
q->size++;
return true;
}
// 出队
bool outQueue(linkQueue *q, datatype *pm)
{
if(isEmpty(q))
return false;
// 返回用户数据
*pm = q->front->data;
// 更新队头队尾指针，分两种情况：
// 1. 当前队列只有一个元素，出队后队列为空，此时队头队尾指针都必须更新
if(q->size == 1)
{
free(q->front);
q->front = NULL;
q->rear = NULL;
}
// 2. 否则，只需更新队头指针即可
else
{
node *tmp = q->front;
q->front = q->front->next;
tmp->next = NULL;
free(tmp);
}
q->size--;
return true;
}
// 取队头元素
bool front(linkQueue *q, datatype *pm)
{
if(isEmpty(q))
return false;
*pm = q->front->data;
return true;
}
**
栈的操作**
编程实现功能将键盘输入的十进制数，转换为十六进制输出。
解析
十进制转十六进制跟十进制转八进制思路一样，但需要注意，由于十六进制中包含字母，因此栈中的数据类型应该是char型。示例代码
int main(void)
{
linkStack *s = initStack();
int n;
scanf("%d", &n);
int m = abs(n);
while(m > 0)
{
push(s, m%16);
m /= 16;
}
printf("%c0x", n<0?'-':'\r');
int tmp;
while(!isSmpty(s))
{
pop(s, &tmp);
printf("%c", tmp);
}
printf("\n");
return 0;
}
解析
十进制转十六进制跟十进制转八进制思路一样，但需要注意，由于十六进制中包含字母，因此栈中的数据类型应该是char型。
示例代码``
int main(void)
{
linkStack *s = initStack();
int n;
scanf("%d", &n);
int m = abs(n);
while(m > 0)
{
push(s, m%16);
m /= 16;
}
printf("%c0x", n<0?'-':'\r');
int tmp;
while(!isSmpty(s))
{
pop(s, &tmp);
printf("%c", tmp);
}
printf("\n");
return 0;
}