数据结构(3) 栈和队列

栈

栈：只允许在一端进行插入或删除操作的线性表。

栈顶：允许插入和删除的一端。栈底：固定的，不允许插入和删除的一端。

特性：先进后出。

栈的顺序存储结构

#define MaxSize 50
typedef struct{
    ElemType data[MaxSize];//存放栈中元素
    int top;//栈顶指针 空栈 top=-1
} Stack;

#初始化
void initStack(Stack &s){
    s.top = -1;
}
#判断栈空
bool stackEmpty(Stack &s){
    if(s.top == -1)
        return true;
    else
        return false;
}
#进栈
bool push(Stack &s,ElemType x){
    if(s.top == MaxSize-1)
        return false;
    s.data[++s.top] = x;
    return true;
}
#出栈
bool pop(Stack &s,ElemType &x){
    if(s.top == -1)
        return false;
    x = s.data[s.top--];
    return true;
}
#读取栈顶元素
bool getTop(Stack &s,ElemType &x){
    if(s.top == -1)
        return false;
    x = s.data[s.top];
    return true;
}

栈的链式存储

typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
} *LinkStack;

队列

队列：只允许在表的一端进行插入，在表的另一端进行删除。

队头：允许删除的一端。队尾：允许插入的一端。

特性：先进先出

队列的顺序存储结构

#define MaxSize 50
typedef struct{
    ElemType data[MaxSize];//存放队列元素
    int front,rear;//队头指针、队尾指针
}Queue;

循环队列

#初始化
void InitQueue(Queue &queue){
    queue.rear = queue.front = 0;
}
#判断队列空
bool isEmpty(Queue queue){
    if(queue.rear == queue.front)
        return true;
    else
        return false;
}
#入队
bool enQueue(Queue &queue,ElemType x){
    if((queue.rear+1)%MaxSize == queue.front)
        return false;//队列满
    queue.data[queue.rear] = x;
    queue.rear = (queue.rear+1) % MaxSize;
    return true;
}
#出队
bool deQueue(Queue &queue,ElemType &x){
    if(queue.rear+1 == queue.front)
        return false;//队列空
    x = queue.data[queue.font];
    queue.front = (queue.front+1) % MaxSize;
    return true;
}

队列的链式存储结构

typedef struct{
    ElemType data;
    struct LinkNode *next
}LinkNode;
typedef struct{
    LinkNode *front,*rear;
}LinkQueue;

#初始化
void InitQueue(LinkQueue &queue){
    queue.front = queue.rear=(LinkNode*)malloc(sizeof(LinkNode));
    queue.front.next = null;
}
#判断队列空
bool isEmpty(LinkQueue queue){
    if(queue.front == queue.rear)
        return true;
    else
        return false;
}
#入队
void enQueue(LinkQueue &queue,ElemType x){
    s = (LinkNode *)malloc(sizeof(LinkNode));
    s->data = x;
    s->next = null;
    queue.rear->next = s;
    queue.rear = s;
}
#出队
bool deQueue(LinkQueue &queue,ElemType &x){
    if(queue.front == queue.rear)
        return false;
    p = queue.front->next;
    x = p->data;
    queue.front->next = p->next;
    if(queue.rear == p)
        queue.rear = queue.front;
    free(p);
    return true;
}

栈和队列的应用