简介
某种程度上来说，栈和队列也是线性表，只是它们是操作受限制的线性表。
栈
栈是一种只能在表尾进行插入或者删除的线性表，通常称为表尾端为栈顶，表头端为栈底。它是一种先进后出的线性表，既只能在表尾端插入和删除元素，分别称为入栈和出栈。如下图：
栈.png
栈也有顺序存储结构和链式存储结构两种表示方法，这两种表示方法实现类似，我们这里讲解一下顺序存储结构的代码实现：
#include <iostream>
#include <cstdlib>
using namespace std;
//栈的顺序存储实现
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define INIT_SIZE 20
#define INCREMENT_SIZE 5
typedef int SElemType;
typedef int Status;
//存储结构
typedef struct {
SElemType *base;
SElemType *top;
int size;
}SqStack;
//初始化栈
Status initStack(SqStack &S) {
S.base = (SElemType *)malloc(INIT_SIZE* sizeof(SElemType));
if(!S.base) {
exit(OVERFLOW);
}
S.top = S.base;
S.size = INIT_SIZE;
return OK;
}
//销毁栈
Status destroyStack(SqStack &S) {
free(S.base);
S.base = NULL;
S.top = NULL;
S.size = 0;
return OK;
}
//清空栈
Status clearStack(SqStack &S) {
S.top = S.base;
return OK;
}
//判断栈是否为空
Status isEmpty(SqStack S) {
if(S.top == S.base) {
return TRUE;
} else {
return FALSE;
}
}
//获取栈的长度
int getStackLength(SqStack S) {
return S.top - S.base;
}
//获取栈顶元素
Status getTopElement(SqStack S, SElemType &e) {
if(S.top > S.base) {
//栈中存在元素
e = *(S.top - 1);
return OK;
} else {
return ERROR;
}
}
//元素入栈
Status push(SqStack &S, SElemType e) {
if((S.top - S.base) / sizeof(SElemType) >= S.size) {
//申请新的存储空间
S.base = (SElemType *)realloc(S.base,(S.size + INCREMENT_SIZE)* sizeof(SElemType));
if(!S.base) {
exit(OVERFLOW);
}
S.top = S.base + S.size;
S.size += INCREMENT_SIZE;
}
*S.top = e;
S.top++;
return OK;
}
//元素出栈
Status pop(SqStack &S, SElemType &e) {
if(S.base == S.top) {
return ERROR;
}
S.top --;
e = *S.top;
return OK;
}
//访问元素
void visit(SElemType e) {
cout << e << " ";
}
//遍历栈
Status traveseStack(SqStack S,void (*visit)(SElemType)) {
SElemType *base = S.base;
while (S.top > base) {
visit(*base);
base ++;
}
return OK;
}
栈可以解决很多问题，例如数值转换、括号匹配、迷宫求解、表达式求值和汉诺塔等等问题。
队列
队列刚好和栈相反，它是一种先进先出的线性表，只能在一端插入元素，在另一端删除元素，如下图所示，允许插入元素的一端称为队尾，允许删除元素的一端称为队头。
队列.png
队列的链式存储结构如下：
#include <iostream>
#include <cstdlib>
using namespace std;
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int QElemType;
typedef int Status;
//存储结构
typedef struct QNode{
//队列中的每个节点
QElemType data;
struct QNode *next;
}QNode, *QueuePtr;
typedef struct {
//指向队列头
QueuePtr front;
//指向队列尾
QueuePtr rear;
}LinkQueue;
//初始化队列
Status initQueue(LinkQueue &q) {
//申请一个节点的空间
q.front = q.rear = (QueuePtr)malloc(sizeof(QNode));
if(!q.front) {
//申请失败
exit(OVERFLOW);
}
q.front->next = NULL;
return OK;
}
//销毁队列
Status destroyQueue(LinkQueue &q) {
while (q.front) {
q.rear = q.front->next;
free(q.front);
q.front = q.rear;
}
return OK;
}
//清空队列
Status clearQueue(LinkQueue &q) {
destroyQueue(q);
initQueue(q);
return OK;
}
//判断队列是否为空
Status isEmpty(LinkQueue q) {
if(q.front->next == NULL) {
return TRUE;
} else {
return FALSE;
}
}
//获取队列长度
int getLength(LinkQueue q) {
int i = 0;
QueuePtr p = q.front;
while (p != q.rear) {
i++;
p = p->next;
}
return i;
}
//获取队头元素
Status getHead(LinkQueue q,QElemType &e) {
QueuePtr p;
if(q.front == q.rear) {
return ERROR;
}
p = q.front->next;
e = p->data;
return OK;
}
//入队
Status enQueue(LinkQueue &q, QElemType e) {
QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
if(!p) {
exit(OVERFLOW);
}
p->data = e;
p->next = NULL;
q.rear->next = p;
q.rear = p;
return OK;
}
//出队
Status deQueue(LinkQueue &q, QElemType &e) {
QueuePtr p;
if(q.front == q.rear) {
return ERROR;
}
p = q.front->next;
e = p->data;
q.front->next = p->next;
if(q.rear == p) {
q.rear = q.front;
}
free(p);
return OK;
}
//访问元素
void visit(QElemType e) {
cout << e << " ";
}
//遍历队列
Status treaverseQueue(LinkQueue q, void(*visit)(QElemType)) {
QueuePtr p = q.front->next;
while (p) {
visit(p->data);
p = p->next;
}
return OK;
}
上面实现的是链式存储结构，使用顺序存储结构可以实现循环队列。
应用
1、把一个十进制的数转换为一个二进制的数，例如9转换为二进制是1001，可以使用栈来实现。
进制转换可以采用栈来实现，将余数入栈，然后统一出栈即可。
int main() {
SqStack stack;
int number;
cin >> number;
if (initStack(stack))
{
while (number > 0) {
push(stack,number%2);
number /= 2;
}
//出栈
while (!isEmpty(stack)) {
int e;
pop(stack,e);
cout << e << " ";
}
}
return 0;
}
2、用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
队列的push和pop操作是先入先出，元素入队时将元素压入栈1，出队时先将栈1中的元素依次压入栈2，再进行出栈。
int main() {
SqStack stack1,stack2;
int number;
cin>>number;
if (initStack(stack1)&&initStack(stack2))
{
int e, count = number;
while (count > 0) {
cin>>e;
push(stack1, e);
count --;
}
count = number;
while (count > 0) {
pop(stack1,e);
push(stack2,e);
count--;
}
//出栈
while (!isEmpty(stack2)) {
pop(stack2,e);
cout << e << " ";
}
}
return 0;
}
