作者 | 寫代碼的籃球球癡
1.什么是數(shù)據(jù)結(jié)構(gòu)？
數(shù)據(jù)結(jié)構(gòu)是什么？要了解數(shù)據(jù)結(jié)構(gòu)，我們要先明白數(shù)據(jù)和結(jié)構(gòu)，數(shù)據(jù)就是一些int char 這樣的變量，這些就是數(shù)據(jù)，如果你是一個籃球愛好者，那么你的球鞋就是你的數(shù)據(jù)，結(jié)構(gòu)就是怎么把這些數(shù)據(jù)排列組合，怎么把數(shù)據(jù)擺放好才能方便你找到這些數(shù)據(jù)，把數(shù)據(jù)和結(jié)構(gòu)合在一起理解就是所謂的數(shù)據(jù)結(jié)構(gòu)，簡單點，就是處理數(shù)據(jù)的方式方法。
平時在家里面，你有沒有隨便擺放自己的鞋子，然后要找鞋子的時候要花費非常多是時間，可能你老婆也很生氣，每天都亂擺鞋子導(dǎo)致她打掃衛(wèi)生非常麻煩，然后有一天，你買了一個非常酷的鞋架，有了這個鞋架之后，你的鞋子終于有家了，這個鞋架就是起到處理鞋子的作用了。
2.什么是棧？
棧可以理解為數(shù)據(jù)結(jié)構(gòu)中的一種，這種數(shù)據(jù)結(jié)構(gòu)的特點是先進(jìn)去的人「數(shù)據(jù)」后出來，就像下面的圖片一樣，如果棧是一個洞，人「數(shù)據(jù)」只能從洞的一個口進(jìn)去，然后出來也只能從一個口出來，而且洞的寬度就只能容納一個人「數(shù)據(jù)」，好了，那先進(jìn)去的那個人「數(shù)據(jù)」最傻逼了，一定要等后面進(jìn)來的人「數(shù)據(jù)」都先出去了才能出去。
用%20C%20語言實現(xiàn)一個棧
我寫代碼是很水的，之前有一個同學(xué)寫了一個棧讓我檢查，我看了下，好像我寫代碼的能力比他厲害一些，代碼比較簡單，然后講一下幾個比較重要的函數(shù)，希望大家在面試的時候，隨手就甩出一個棧“砸死”面試官，哈哈。
#include%20"stdio.h"
#include%20"stdlib.h"
struct%20List{
int%20data;
struct%20List%20*%20next;
};
struct%20Stack{
struct%20List%20*head;
int%20size;
};
struct%20Stack%20*%20StackInit(void)
{
struct%20Stack%20*stack%20=%20;
stack%20=%20(struct%20Stack*)malloc(sizeof(struct%20Stack));
stack->head%20=%20(struct%20List%20*)malloc(sizeof(struct%20List));
stack->head->next%20=%20;
stack->size%20=%200;
return%20stack;
}
int%20StackPush(struct%20Stack%20*stack,int%20data)
{
struct%20List%20*tmp%20=%20(struct%20List%20*)malloc(sizeof(struct%20List));
tmp->data%20=%20data;
tmp->next%20=%20stack->head->next;
stack->head->next%20=%20tmp;
stack->size++;
//printf("push:%d%20n",data);
return%200;
}
int%20IsStackEmpty(struct%20Stack%20*stack)
{
/*如果頭指針指向下一個為空，說明棧為空*/
if(stack->head->next%20==%20)
return%201;
else
return%200;
}
int%20StackPop(struct%20Stack%20*stack,int%20*data)
{
struct%20List%20*tmp%20=%20;
if(IsStackEmpty(stack))
return%20-1;
tmp%20=%20stack->head->next;
*data%20=%20tmp->data;
stack->head->next%20=%20tmp->next;
stack->size--;
free(tmp);
//printf("pop:%d%20n",*data);
return%200;
}
int%20main(void)
{
int%20i%20=%200;
struct%20Stack%20*stack%20=%20;
stack%20=%20StackInit;
for(i%20=%200;i<5;i++)
{
StackPush(stack,i);
}
for(i%20=%200;i<5;i++)
{
int%20data%20=%200;
StackPop(stack,&data);
printf("%d%20",data);
}
printf("n");
return%200;
}
1-棧頭部
棧頭部，也就是棧頂指針，我們用指針單鏈表實現(xiàn)一個棧，一定要知道這個棧頂?shù)闹羔槪蓄^就有棧，沒有頭，這個棧也就跨了。
struct%20Stack%20*stack%20=%20;
stack%20=%20StackInit;
這個就是定義一個棧，也就是malloc出來一個內(nèi)存，專門存這個棧頂?shù)摹?/p>
2-出棧
出棧的方法跟我之前說的差不多，只不過出棧代碼上需要做判斷。
int StackPop(struct Stack *stack,int *data)
{
struct List *tmp = ;
if(IsStackEmpty(stack))
return -1;
tmp = stack->head->next;
*data = tmp->data;
stack->head->next = tmp->next;
stack->size--;
free(tmp);
//printf("pop:%d n",*data);
return 0;
}
先判斷這個棧是不是空的，是不是空的判斷方法就是通過判斷head->next的指針是否為空。
然后把head->next 這個位置的數(shù)據(jù)取出來，取出來后，再把head->next的指針指向 取出來這個位置 的next 位置。
然后再記得free掉。就Ok了。
3-入棧
入棧的操作和出棧的操作剛好相反，就是改變一下位置和指針的指向。
int StackPush(struct Stack *stack,int data)
{
struct List *tmp = (struct List *)malloc(sizeof(struct List));
tmp->data = data;
tmp->next = stack->head->next;
stack->head->next = tmp;
stack->size++;
//printf("push:%d n",data);
return 0;
}
4.用數(shù)組來實現(xiàn)一個棧
數(shù)組本身是一種數(shù)據(jù)結(jié)構(gòu)，使用數(shù)組實現(xiàn)一個棧也是非常簡單方便的，大家請看。
#include "stdio.h"
#include "stdlib.h"
/*棧的大小*/
#define LENGHT (100)
struct Stack{
int stack_array[LENGHT];
unsigned int size;//棧動態(tài)長度
};
struct Stack * StackInit(void)
{
struct Stack *stack = ;
stack = (struct Stack*)malloc(sizeof(struct Stack));
stack->size = 0;
return stack;
}
int StackPush(struct Stack *stack,int data)
{
if(stack->size >= LENGHT)
{
printf("stack is fulln");
return (-1);
}
stack->stack_array[stack->size] = data;
stack->size++;
//printf("push:%d size:%dn",data,stack->size);
return 0;
}
int IsStackEmpty(struct Stack *stack)
{
/*如果頭指針指向下一個為空，說明棧為空*/
if(stack->size == 0)
return 1;
else
return 0;
}
int StackPop(struct Stack *stack,int *data)
{
stack->size--;
if(IsStackEmpty(stack))
return -1;
*data = stack->stack_array[stack->size];
//printf("pop:%d size:%dn",*data,stack->size);
return 0;
}
int main(void)
{
int i = 0;
struct Stack *stack = ;
stack = StackInit;
for(i = 0;i<20;i++)
{
StackPush(stack,i);
}
for(i = 0;i<21;i++)
{
int data = 0;
StackPop(stack,&data);
printf("%d n",data);
}
printf("n");
return 0;
}
5.總結(jié)
既然有棧，就會有和棧不一樣的數(shù)據(jù)結(jié)構(gòu)，有一種數(shù)據(jù)結(jié)構(gòu)叫做隊列，棧的數(shù)據(jù)結(jié)構(gòu)特點是先進(jìn)后出，隊列的數(shù)據(jù)結(jié)構(gòu)特點是先進(jìn)先出，有點意思，棧和隊列做驅(qū)動的同學(xué)很少需要自己寫代碼實現(xiàn)，正常情況下都是SDK集成了方法，直接調(diào)用接口就好了，但是寫應(yīng)用的同學(xué)，經(jīng)常要自己實現(xiàn)一個棧或者隊列，特別是大企業(yè)面試，這些算是非常基礎(chǔ)的題目，最好是閉著眼睛就能寫出來的那種。
【End】
