从数据结构的角度看，栈和队列也是线性表，其特殊性在于栈和队列的基本操作是线性表操作的子集
| 栈 | 队列 | |
|---|---|---|
| 逻辑结构 | 和线性表一样，数据元素之间存在一对一的关系 | 和线性表一样，数据元素之间存在一对一的关系 |
| 存储结构 |
顺序存储:
|
顺序存储（常设计成循环队列）：
|
链式存储：
|
链式存储：
|
|
| 运算规则 | 插入和删除在表的一端（栈顶）完成，后进先出 | 插入运算在表的一端（队尾）进行，删除在表的另一端（队头），先进先出 |
限定仅在表尾进行插入或者删除操作的线性表，栈的修改按照先进后出的原则
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100
typedef struct SqStack
{
int *data;
int top; // 栈顶指针
}SqStack;
// InitStack 初始化顺序栈
int InitStack(SqStack *s) {
s->top = -1;
s->data = (int *)malloc(sizeof(int)*MAXSIZE);;
return 0;
}
// Push 入栈
// 1. 判断栈是否满,若满则返回-1
// 2. 将新元素压入栈顶,栈顶指针加1
int Push(SqStack *s, int e) {
// 栈满
if (s->top == MAXSIZE-1) {
return -1;
}
s->data[++s->top] = e;
return 0;
}
// Pop 出栈
// 1. 判断栈是否为空,若空则返回-1
// 2. 栈顶指针减1,栈顶元素出栈
int Pop(SqStack *s, int *e) {
if (s->top == -1) {
return -1;
}
e = &s->data[s->top--];
return 0;
}
// GetTop 取栈顶元素
int GetTop(SqStack *s) {
if (s->top !=-1) {
return s->data[s->top];
}
return 0;
}
#include<stdio.h>
#include<stdlib.h>
typedef struct StackNode
{
int data;
struct StackNode* next;
}StackNode,*LinkStack;
// InitStack 初始化链栈
int InitStack(LinkStack s) {
s = NULL;
return 0;
}
// Push 入栈
// 1. 为入栈元素分配空间,用指针p指向
// 2. 将新节点数据域置为e
// 3. 将新节点插入栈顶
// 4. 修改栈顶指针为p
LinkStack Push(LinkStack s, int e) {
LinkStack p = (LinkStack)malloc(sizeof(StackNode));
p->data = e;
p->next = s;
s = p;
return s;
}
// Pop 出栈
// 1. 判断栈是否为空,若空则返回-1
// 2. 将栈顶元素赋给e
// 3. 临时保存栈顶元素的地址,以备释放
// 4. 修改栈顶指针,指向新的栈顶元素
// 5. 释放原栈顶元素的地址
LinkStack Pop(LinkStack s, int *e) {
if (s == NULL) {
return s;
}
*e = s->data;
LinkStack p = s;
s = s->next;
free(p);
return s;
}
// GetTop 取栈顶元素
int GetTop(LinkStack s) {
if (s != NULL) {
return s->data;
}
return 0;
}
一种先进先出的线性表。它只允许在表的一端进行插入，而在另一端删除元素
#include<stdio.h>
#include<stdlib.h>
#define MaxQSize 100
typedef struct {
int *base; // 存储空间基地址
int front; // 头结点
int rear; // 尾结点
}SqQueue;
// InitQueue 初始化循环队列
void InitQueue(SqQueue *q)
{
q->base = (int *)malloc(sizeof(int)*MaxQSize);
q->front = q->rear = 0;
}
// QueueLenth 队列长度
int QueueLenth(SqQueue q) {
return (q.rear - q.front + MaxQSize) % MaxQSize;
}
// Push 入队
// 1、判断队列是否满
// 2、将新元素插入队尾
// 3、队尾指针加1
int Push(SqQueue *q, int e)
{
// 队满
if ((q->rear+1)%MaxQSize == q->front) {
return -1;
}
q->base[q->rear] = e;
q->rear = (q->rear + 1) % MaxQSize;
return 0;
}
// Pop 出队
// 1、判断队列是否为空
// 2、保存队头元素
// 3、队头指针加1
int Pop(SqQueue *q, int *e)
{
// 队空
if (q->rear == q->front) {
return -1;
}
*e = q->base[q->front];
q->front = (q->front + 1) % MaxQSize;
return 0;
}
// GetTop 取队头元素
int GetTop(SqQueue *q, int *e)
{
if (q->front == q->rear) {
return -1;
}
*e = q->base[q->front];
return 0;
}
链队是指采用链式存储结构实现的队列。通常链队用单链表表示。一个链队显然需要两个分别指示队头和队尾的指针(分别称为头指针和尾指针)才能唯一确定。
#include<stdio.h>
#include<stdlib.h>
typedef struct QNode QNode;
typedef struct QNode* QPtr;
struct QNode
{
int data;
struct QNode* next;
};
typedef struct LinkQueue LinkQueue;
struct LinkQueue
{
QPtr front; // 队头指针
QPtr rear; // 队尾指针
};
// InitQueue 链队初始化
// 1、生成新结点，队头和队尾都指向此结点
// 2、头结点的指针域置为空
void InitQueue(LinkQueue *q)
{
QPtr node = (QPtr)malloc(sizeof(QNode));
node->next = NULL;
q->front = node;
q->rear = node;
}
// EnQueue 元素入队
// 1、为入队元素分配结点空间，用指针p指向
// 2、将新结点数据域置为e
// 3、将新结点插入到队尾
// 4、修改队尾指针为p
void EnQueue(LinkQueue *q, int e)
{
QPtr p = (QPtr)malloc(sizeof(QNode));
p->data = e;
p->next = NULL;
q->rear->next = p;
q->rear = p;
}
// DeQueue 元素出队
// 1、判断队列是否为空，若空则返回-1
// 2、临时保存队头元素的空间，以备释放
// 3、修改头结点的指针域，指向下一个结点
// 4、判断出队是否为最后一个元素，若是，则将队尾指针重新赋值，指向头结点
// 5、释放原队头元素的空间
void DeQueue(LinkQueue *q, int *e)
{
if (q->rear == q->front)
{
return;
}
QPtr p = q->front->next;
*e = p->data;
q->front->next = p->next;
if (q->rear == p)
{
q->rear = q->front;
}
free(p);
}
// GetTop 取队头元素
void GetTop(LinkQueue *q, int *e)
{
if (q->front != q->rear) {
*e = q->front->next->data;
}
}
#include<stdio.h>
void move(char A, char B) {
printf("%c ---> %c\n", A, B);
}
void hanoi(int n, char A, char B, char C) {
if (n == 1) {
move(A, C);
return;
}
// 将A上编号为1至n-1的圆盘移动到B,C做辅助塔
hanoi(n-1, A, C, B);
// 将编号为n的圆盘从A移动到C
move(A, C);
// 将B上编号为1至n-1的圆盘移动到C,A做辅助塔
hanoi(n-1, B, A, C);
}
// 表达式求值
// 1、初始化栈OPTR和OPND
// 2、扫描表达式，读入第一个字符ch，如果表达式没有扫描完成
// a、若ch不是运算符，则压入OPND栈，读入下一个字符ch;
// b、若ch是运算符，则根据OPTR的栈顶元素和ch的优先级比较结果，做不同的处理：
// 1、若是小于，则ch压入OPTR栈，读入下一个字符ch
// 2、若是大于，则弹出OPTR栈顶的运算符，从OPND栈弹出两个数，进行相应运算，结果压入OPND栈
// 3、若是等于，则OPTR的栈顶元素是"("且ch是")"，这是弹出OPTR栈顶的"("，相当于括号匹配成功，然后读入下一个字符ch
// 3、OPEN栈顶元素即为表达式求值结果，返回此元素
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXSIZE 100
// 运算符栈
typedef struct OPTRStack OPTRStack;
struct OPTRStack {
char data;
OPTRStack* next;
};
// 操作数栈
typedef struct OPNDStack OPNDStack;
struct OPNDStack
{
double data;
OPNDStack* next;
};
char getOptr(OPTRStack *optr)
{
char ch = '-';
if (optr == NULL)
{
return ch;
}
return optr->data;
}
OPTRStack* popOptr(OPTRStack *optr, char *ch)
{
if (optr == NULL)
{
return optr;
}
*ch = optr->data;
OPTRStack *p = optr;
optr = optr->next;
free(p);
return optr;
}
OPNDStack* popOpnd(OPNDStack *opnd, double *data)
{
if (opnd == NULL)
{
return opnd;
}
*data = opnd->data;
OPNDStack *p = opnd;
opnd = opnd->next;
free(p);
return opnd;
}
OPNDStack* pushOpnd(OPNDStack *opnd, double data)
{
OPNDStack *p = (OPNDStack*)malloc(sizeof(OPNDStack));
p->data = data;
p->next = opnd;
opnd = p;
return opnd;
}
int isOPTR(char ch)
{
if (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '(' || ch == ')' || ch == '#')
{
return 1;
}
return 0;
}
char precede(char a, char b)
{
if (a == '+')
{
if (b == '*' || b == '/' || b == '(')
{
return '<';
}
return '>';
}
else if (a == '-')
{
if (b == '*' || b == '/' || b == '(')
{
return '<';
}
return '>';
}
else if (a == '*')
{
if (b == '(')
{
return '<';
}
return '>';
}
else if (a == '/')
{
if (b == '(')
{
return '<';
}
return '>';
}
else if (a == '(')
{
if (b == ')')
{
return '=';
}
else if (b == '#')
{
return '!';
}
return '<';
}
else if (a == ')')
{
if (b == '(')
{
return '!';
}
return '>';
}
else if (a == '#')
{
if (b == ')')
{
return '!';
}
else if (b == '#')
{
return '=';
}
return '<';
}
else
{
return '!';
}
}
double operate(double left, double right, char operaor)
{
double result;
switch (operaor)
{
case '+':
result = left + right;
break;
case '-':
result = left - right;
break;
case '*':
result = left * right;
break;
case '/':
result = left / right;
break;
default:
result = 0.0;
break;
}
return result;
}
void EvaluateExpression() {
// 初始化栈
OPTRStack *optr = (OPTRStack*)malloc(sizeof(OPTRStack));
optr->data = '#';
optr->next = NULL;
OPNDStack *opnd = NULL;
char *str = (char *)malloc(sizeof(char)*MAXSIZE);
// scanf("%s", str);
str = "3*(7-2)#";
int index = 0;
char operator;
int error = 0;
while(str[index] != '\0')
{
char ch = str[index];
if (error == 1) {
break;
}
if (isOPTR(ch) != 1)
{
// 操作数入栈
OPNDStack *opndNode = (OPNDStack*)malloc(sizeof(OPNDStack));
opndNode->data = ch - '0';
opndNode->next = opnd;
opnd = opndNode;
index++;
continue;
}
char cede = precede(getOptr(optr), ch);
switch (cede)
{
case '<':
{
OPTRStack *optrNode = (OPTRStack*)malloc(sizeof(OPTRStack));
optrNode->data = ch;
optrNode->next = optr;
optr = optrNode;
index++;
break;
}
case '>':
{
optr = popOptr(optr, &operator);
double left, right;
opnd = popOpnd(opnd, &right);
opnd = popOpnd(opnd, &left);
opnd = pushOpnd(opnd, operate(left, right, operator));
break;
}
case '=':
{
optr = popOptr(optr, &operator);
index++;
break;
}
default:
{
printf("Syntax Error!");
error = 1;
break;
}
}
}
if (error != 1)
{
printf("结果为:%lf\n", opnd->data);
} else {
printf("表达式错误!!!\n");
}
}