3.队列和栈

栈

后进先出（Last In First Out，LIFO）的线性序列，称为“栈”。栈也是一种线性表，只不过它是操作受限的线性表，只能在一端进出操作。进出的一端称为栈顶（top），另一端称为栈底（base）。栈可以用顺序存储，也可以用链式存储，分别称为顺序栈和链栈。

静态分配

初始化

入栈

出栈

取栈顶

链栈

入栈

出栈

取栈顶

栈实现（数组）

#include <stdio.h>

#define MAXSIZE 100

// 数组实现栈

typedef struct Stack {
  // 保存数据
  int data[MAXSIZE];
  // 指向栈顶的下标
  int top;
} Stack;

int isEmpty(Stack *qstack) {
  if(qstack->top == 0) {
    return 1;
  }
  return 0;
}

// 入栈
void push(Stack *qstack, int val) {
  if(qstack->top >= MAXSIZE) {
    printf("栈满\n");
    return;
  }
  qstack->data[qstack->top] = val;
  qstack->top ++;
}

void pop(Stack *qstack) {
  if(qstack->top == 0) {
    printf("栈为空\n");
    return;
  }
  qstack->top --;
}

int top(Stack *qstack) {
  if(qstack->top == 0) {
    printf("栈为空\n");
    return -1;
  }
  return qstack->data[qstack->top-1];
}

int main(int argc, char *argv[])
{
  Stack s;
  s.top = 0;

  push(&s, 1);
  push(&s, 2);
  printf("top : %d \n", top(&s));
  push(&s, 3);
  printf("top : %d \n", top(&s));
  push(&s, 4);
  printf("top : %d \n", top(&s));
  push(&s, 5);
  printf("top : %d \n", top(&s));
  pop(&s);
  printf("top : %d \n", top(&s));
  pop(&s);
  printf("top : %d \n", top(&s));
  pop(&s);
  printf("top : %d \n", top(&s));
  pop(&s);
  printf("top : %d \n", top(&s));
  pop(&s);
  printf("top : %d \n", top(&s));
  return 0;
}

栈实现（栈链）

#include <stdio.h>
#include <stdlib.h>

typedef struct Stack {
  int val;
  struct Stack *next;
} *Stack;

// 最顶部不保存数据
Stack initialStack() {
  Stack s = (Stack) malloc(sizeof(Stack));
  if(!s) return NULL;
  s->next = NULL;
  return s;
}

int isEmpty(Stack s) {
  return s->next == NULL;
}

void push(Stack s, int val) {
  Stack elem = (Stack) malloc(sizeof(Stack));
  elem->val = val;
  elem->next = s->next;
  s->next = elem;
}

void pop(Stack s) {
  if(!isEmpty(s)) {
    Stack temp = s->next;
    s->next = temp->next;
    free(temp);
  }
}

int top(Stack s) {
  if(!isEmpty(s)) {
    return s->next->val;
  }
  printf("stack is empty.\n");
  return -1;
}

void printStack(Stack s) {
  if(isEmpty(s)) {
    printf("stack is empty.\n");
    return;
  }
  Stack p = s->next;
  while(p) {
    printf("%d\t", p->val);
    p = p->next;
  }
  printf("\n");
}

int main(int argc, char *argv[])
{
  Stack s = initialStack();
  printStack(s);
  push(s, 1);
  push(s, 2);
  push(s, 3);
  push(s, 4);
  printStack(s);
  pop(s);
  pop(s);
  printStack(s);
  printf("top: %d \n", top(s));
  return 0;
}

队列

先进先出（First In First Out，FIFO）的线性序列，称为“队列”。队列也是一种线性表，只不过它是操作受限的线性表，只能在两端操作：一端进，一端出。进的一端称为队尾（rear），出的一端称为队头（front）。队列可以用顺序存储，也可以用链式存储。

顺序队列

动态分配

静态分配

初始化

入对

循环队列

对空时：Q.front==Q.rear

对满时：(Q.rear+1)%Maxsize=Q.front

循环队列入对

Q.base[Q.rear]=x;    //将元素x放入Q.rear所指空间
Q.rear=(Q.rear+1) %Maxsize; //Q.rear后移一位

链队

队列实现（链对）

#include <stdio.h>
#include <stdlib.h>

typedef struct Queue {
  int val;
  struct Queue *next;
} *Queue;

// 最顶部不保存数据
Queue initialStack() {
  Queue q = (Queue) malloc(sizeof(Queue));
  if(!q) return NULL;
  q->next = NULL;
  return q;
}

int isEmpty(Queue q) {
  return q->next == NULL;
}

void enQueue(Queue q, int val) {
  Queue p = q;
  while(p->next) {
    p = p->next;
  }
  Queue elem = (Queue) malloc(sizeof(Queue));
  elem->val = val;
  p->next = elem;
}

void deQueue(Queue q) {
  if(!isEmpty(q)) {
    Queue temp = q->next;
    q->next = temp->next;
    free(temp);
  }
}

int getHead(Queue q) {
  if(isEmpty(q)) {
    printf("queue is empty.\n");
    return -1;
  }
  return q->next->val;
}

void printQueue(Queue q) {
  if(isEmpty(q)) {
    printf("queue is empty.\n");
    return;
  }
  Queue p = q->next;
  while(p) {
    printf("%d\t", p->val);
    p = p->next;
  }
  printf("\n");
}

int main(int argc, char *argv[])
{
  Queue q = initialStack();
  enQueue(q, 1);
  enQueue(q, 2);
  enQueue(q, 3);
  enQueue(q, 4);
  printQueue(q);
  deQueue(q);
  deQueue(q);
  printQueue(q);
  printf("the head is %d \n", getHead(q));
  return 0;
}