什么是數據結構？

數據結構是什么？要了解數據結構，我們要先明白數據和結構，數據就是一些int char 這樣的變量，這些就是數據，如果你是一個籃球愛好者，那么你的球鞋就是你的數據，結構就是怎么把這些數據排列組合，怎么把數據擺放好才能方便你找到這些數據，把數據和結構合在一起理解就是所謂的數據結構，簡單點，就是處理數據的方式方法。

平時在家里面，你有沒有隨便擺放自己的鞋子，然后要找鞋子的時候要花費非常多是時間，可能你老婆也很生氣，每天都亂擺鞋子導致她打掃衛生非常麻煩，然后有一天，你買了一個非常酷的鞋架，有了這個鞋架之后，你的鞋子終于有家了，這個鞋架就是起到處理鞋子的作用了。

什么是棧？

棧可以理解為數據結構中的一種，這種數據結構的特點是先進去的人「數據」后出來，就像下面的圖片一樣，如果棧是一個洞，人「數據」只能從洞的一個口進去，然后出來也只能從一個口出來，而且洞的寬度就只能容納一個人「數據」，好了，那先進去的那個人「數據」最傻逼了，一定要等后面進來的人「數據」都先出去了才能出去。

 

 

用C 語言實現一個棧

我寫代碼是很水的，之前有一個同學寫了一個棧讓我檢查，我看了下，好像我寫代碼的能力比他厲害一些，代碼比較簡單，然后講一下幾個比較重要的函數，希望大家在面試的時候，隨手就甩出一個棧砸死面試官，哈哈。

#include "stdio.h"
#include "stdlib.h"

struct List{
	int data;
	struct List * next;
};

struct Stack{
	struct List *head;
	int size;
};


struct Stack * StackInit(void)
{
	struct Stack *stack = NULL;
	stack =  (struct Stack*)malloc(sizeof(struct Stack));
	stack->head = (struct List *)malloc(sizeof(struct List));
	stack->head->next = NULL;
	stack->size = 0;
	return stack;
}

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;
}

int IsStackEmpty(struct Stack *stack)
{
	/*如果頭指針指向下一個為空，說明棧為空*/
	if(stack->head->next == NULL)
		return 1;
	else
		return 0;
}

int StackPop(struct Stack *stack,int *data)
{
	struct List *tmp = NULL;
	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;
}


int main(void)
{
	int i = 0;
	struct Stack *stack = NULL;
	stack = StackInit();
	for(i = 0;i<5;i++)
	{
		StackPush(stack,i);
	}
	for(i = 0;i<5;i++)
	{
		int data = 0;
		StackPop(stack,&data);
		printf("%d ",data);
	}
	printf("\n");
	return 0;
}  
  

1-棧頭部

棧頭部，也就是棧頂指針，我們用指針單鏈表實現一個棧，一定要知道這個棧頂的指針，有頭就有棧，沒有頭，這個棧也就跨了。

struct Stack *stack = NULL;
	stack = StackInit();

這個就是定義一個棧，也就是malloc出來一個內存，專門存這個棧頂的。

    

2-出棧

出棧的方法跟我之前說的差不多，只不過出棧代碼上需要做判斷。

int StackPop(struct Stack *stack,int *data)
{
	struct List *tmp = NULL;
	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 這個位置的數據取出來，取出來后，再把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;
}
  
  

用數組來實現一個棧

數組本身是一種數據結構，使用數組實現一個棧也是非常簡單方便的，大家請看。

#include "stdio.h"
#include "stdlib.h"

/*棧的大小*/
#define LENGHT (100)

struct Stack{
	int stack_array[LENGHT];
	unsigned int size;//棧動態長度
};


struct Stack * StackInit(void)
{
	struct Stack *stack = NULL;
	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 full\n");
		return (-1);
	}
	stack->stack_array[stack->size] = data;
	stack->size++;
	//printf("push:%d size:%d\n",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:%d\n",*data,stack->size);
	return 0;
}


int main(void)
{
	int i = 0;
	struct Stack *stack = NULL;
	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;
}