剑指offer 第二天

面试题5 从尾到头打印链表
打印 不需要反转链表 遍历链表从前向后 输出从后向前 先进后出 所以要用到栈
思路 遍历链表 把节点压入栈中，遍历完成以后，把栈中元素弹出并打印。
代码如下

#include <stdio.h>
#include <stdlib.h>
struct stack{
int data[100];
int top;
};
struct node{
int data;
struct node *next;
};
struct node * create(){
struct node *head,*p,*s;
head=(struct node *)malloc(sizeof(struct node));
p=head;
int x,cycle=1;
while (cycle) {
    scanf("%d",&x);
    if (x!=0) {
        s=(struct node *)malloc(sizeof(struct node));
        s->data=x;
        p->next=s;
        p=s;
    }else{
        cycle=0;
    }
}
p->next=NULL;
head=head->next;
return head;
}
void reversePrint(struct node *head,struct stack *sp){
struct node *p=head;
while (p) {
    sp->data[sp->top]=p->data;
    sp->top++;
    p=p->next;
    
}
sp->top--;
while (sp->top>=0) {
    printf("%d",sp->data[sp->top]);
    sp->top--;
}
}
int main(int argc, const char * argv[]) {
struct stack s;
s.top=0;
struct stack *sp=&s;
struct node *head=create();
reversePrint(head, sp);
return 0;
}

递归代码如下

void diguiPrint(struct node *head){
if (head!=NULL) {
    struct node *p=head;
    diguiPrint(p->next);
    printf("%d",p->data);
}
}

面试题7 用两个栈实现队列 实现尾部增加和头部删除的函数
举一个具体的例子
插入时都是在数组后面插入
删除时 要删除先进去的元素 此时如果我们把s1的元素都压到s2中 那么s2中就是符合队列特征的
综上 删除时 如果s2里有元素 那么直接删s2的 没有 就把s1的元素压入s2
代码如下

void appendTail(struct stack *s1,int x){
s1->top++;
s1->data[s1->top]=x;
}
void deleteHead(struct stack *s1,struct stack *s2){
  if (s2->top==-1) {
    //s2为空 把s1中元素压入s2
    while (s1->top!=-1) {
        int temp=s1->data[s1->top];
        s1->top--;
        s2->top++;
        s2->data[s2->top]=temp;
    }
}
//s2不为空 删除s2栈顶元素
printf("%d",s2->data[s2->top]);
s2->top--;
}

本题总结 栈的相关操作
初始化栈顶指针

s->top=-1

判断栈空

if (s2->top==-1)

入栈

s2->top++;
s2->data[s2->top]=temp;

出栈

int temp=s1->data[s1->top];
        s1->top--;