栈 & 队列

栈 Stack

• 栈顶 栈底
• 后进先出
• 初始化 base == top

顺序栈

• SElemType *base; SElemType *top; int stacksize;
• 初始化
  • 分配数组空间
  • 赋值 stacksize
• 最好预先得知容量

链栈

• ElemType data; struct StackNode *next;
• 不需要头结点
• 递归 ⇒ 边界 + 递推结构 链表自身即可递归 调用函数进栈
• 递归工作栈

队列

• 在头部删除
• 先进先出

循环队列

• QElemType *base; int front; int rear;
• 顺序表示
• 初始化 front = rear = 0;
• 长度 (rear - front + MAXQSIZE) % MAXQSIZE
• 插入 ⇒ rear + 1 删除 ⇒ front + 1
• 假溢出
• 循环队列 rear = (rear + 1)%MAXQSIZE

• 区分 满 vs. 空
  • 少一个元素空间 front == rear ⇒ 空 (rear + 1)%MAXQSIZE == front ⇒ 满
  • tag 区分 在进栈和出栈的前后判断 tag

链队

• 初始化 front = rear = new QNode;
• 其他操作基本相似

Tips

• e = *S.top++/-- ⇒ 指针改变 & 赋值 e = *(S.top - 1) ⇒ 仅赋值
• 循环队列 +1 时要 %MAXSIZE
• 判断
  • 空 满
  • 链队出队 判断是否最后一个元素 ⇒ 赋 rear = front 以免丢失尾指针

程序实现

// 顺序栈
typedef struct {
   int base;
   int top;
   int arr[MAX];
} SqStack;
​
void InitStack(SqStack *s) {
   s->top = 0;
   s->base = 0;
}
​
void push(SqStack *s, int val) {
   s->arr[s->top] = val;
   s->top++;
}
​
int pop(SqStack *s) {
   if(s->base == s->top) {
       return -1;
  }
   s->top--;
   return s->arr[s->top];
}
​
int CalcSum(SqStack *s) {
   int x;
   int len = 0;
   int sum = 0;
   while(1) {
       scanf("%d", &x);
       if(x == 0) break;
       len++;
       push(s, x);
       sum += len*x;
  }
   return sum;
}
​
void PrintStack(SqStack *s) {
   for(int i = 0; ; i++) {
       int x = pop(s);
       if(x == -1) break;
       else printf("%d ", x);
  }
}

// 链栈
typedef struct StackNode {
   ElemType data;
   struct StackNode *next;
} StackNode, *LinkStack;
​
LinkStack InitStack() {
   StackNode *s;
   s = NULL;
   return s;
}
​
int GetTop(LinkStack s) {
   if(s == NULL) return -1;
   return s->data;
}
​
LinkStack push(LinkStack s, char val) {
   StackNode *p = (StackNode *) malloc(sizeof(StackNode));
   p->data = val;
   p->next = s;
   s = p;
   return s;
}
​
LinkStack pop(LinkStack s, int *val) {
   *val = s->data;
   s = s->next;
   return s;
}
​
LinkStack CreateStack(LinkStack s) {
   char x[1000];
   scanf("%s", x);
   int len = strlen(x);
   StackNode *p = s;
   for(int i = 0; i < len; i++) {
       s = push(s, x[i]);
  }
   return s;
}

// 队列
typedef struct {
   QElemType *base;
   int front;
   int rear;
}SqQueue;
​
void InitQueue(SqQueue *Q) {
   Q->base = (QElemType *)malloc(MAX * sizeof(QElemType));
   Q->front = Q->rear = 0;
}
​
void EnQueue(SqQueue *Q,QElemType e) {
   if ((Q->rear + 1) % MAX == Q->front) return;
   Q->base[Q->rear] = e;
   Q->rear = (Q->rear + 1) % MAX;
}
​
void DeQueue(SqQueue *Q, QElemType *e) {
   if (Q->front == Q->rear) return;
   *e = Q->base[Q->front];
   Q->front = (Q->front + 1) % MAX;
}
​
int Top(SqQueue *Q) {
   return Q->base[Q->front];
}
​
int length(SqQueue *Q) {
   return (Q->rear - Q->front + MAX) % MAX;
}