前言

使用自定义链表实现栈，自定义链表的实现：自定义链表

具体实现

• 栈接口

public interface Stack<T> {

    /**
     * 添加元素
     * @param t
     */
    void push (T t);

    /**
     * 元素出栈
     * @return
     */
    T pop();

    /**
     * 查看栈顶元素
     * @return
     */
    T peek();

    /**
     * 获取大小
     * @return
     */
    int getSize();

    /**
     * 是否为空
     * @return
     */
    boolean isEmpty();

}

• 实现类

public class LinkedListStack<T> implements Stack<T> {

    /**
     * 链表
     */
    private LinkedList<T> list;

    /**
     * 构造方法
     */
    public LinkedListStack() {
        list = new LinkedList<>();
    }

    /**
     * 添加元素
     * @param t
     */
    @Override
    public void push(T t) {
        list.addFirst(t);
    }

    /**
     * 元素出栈
     * @return
     */
    @Override
    public T pop() {
        return list.removeFirst();
    }

    /**
     * 获取栈顶元素
     * @return
     */
    @Override
    public T peek() {
        return list.getFirst();
    }

    /**
     * 获取大小
     * @return
     */
    @Override
    public int getSize() {
        return list.getSize();
    }

    /**
     * 是否为空
     * @return
     */
    @Override
    public boolean isEmpty() {
        return list.isEmpty();
    }

    /**
     * 重写toString方法
     * @return
     */
    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append("Stack: top ");
        res.append(list);
        return res.toString();
    }

    public static void main(String[] args) {
        LinkedListStack<Integer> stack = new LinkedListStack<>();

        for (int i = 0; i < 5; i++) {
            stack.push(i);
            System.out.println(stack);
        }

        stack.pop();
        System.out.println(stack);
    }

}

C语言数据结构之栈(链表实现)

tips:前些天学习了单链表的增删改查，对于双向链表和循环链表而言，无非就是对单链表的指针进行稍微的变换。今天来看看c语言数据结构之栈的实现以及栈的各种操作。

栈的特点是先进后出，后进先出，因此我们很容易联想到去使用单链表的头插法，和头部删除法去实现入栈和出栈的操作。

• 创建栈中元素的结构体

typedef struct tag 
{
	int val;//栈(链表)的值，即数据域部分
	struct  tag *pNext;//后继指针
}Node,*pNode;

• 创建栈的结构体

typedef struct tagStack
{
	pNode phead;//链表(tag)的头指针
	int size;//栈的大小（栈中元素个数）
}Stack,*pStack;

• 准备打印输出函数

//打印栈元素
void print_stack(pStack p)
{
	pNode pcur = p->phead;//工具人保存当前结点信息
	while (pcur!=NULL)
	{
		printf("%d\n",pcur->val);
		pcur = pcur->pNext;
	}

	printf("---------------------------------\n");
}

1、入栈(push)
思路：

• 为链表创建新结点，并将其初始化；
• 采用头插法为链表添加新结点入栈；
• 入栈操作完成后，将栈的size+1；

具体实现：

//入栈
void push(pStack p, int val)
{
	pNode pnew = (pNode)malloc(sizeof(Node));//申请新结点空间(申请的是tag)

	//新结点初始化
	pnew->val = val;
	pnew->pNext = NULL;

	//入栈，头插法
	if (p->phead == NULL)//判断链表是否为空,为空，头指针指向新结点
	{
		p->phead = pnew;
	}
	else //不为空，则头插法
	{
		//新结点变成新的头结点
		pnew->pNext = p->phead;
		p->phead = pnew;
	}
	p->size++;
}

2、出栈(pop)
思路：

• 采用头部删除法，删除链表第一个结点（即栈顶元素），完成出栈；
• 出栈操作完成后，将栈的size-1；

具体实现：

//出栈,头部删除法
void pop(pStack p)
{
	pNode pcur = p->phead;//工具人保存当前结点信息
	//判断链表是否为空
	if (p->phead == NULL)
	{
		printf("该链表为空!\n");
	}
	else
	{
		//头部删除法
		p->phead = pcur->pNext;
		free(pcur);
		p->size--;
	}
}

3、返回栈顶元素(top)
思路：

• 当栈为空时直接返回EOF；
• 当栈不为空时，直接返回链表头结点的val（即栈顶元素的值）；

具体实现：

//返回栈顶元素
int top(pStack p)
{
	//判断链表是否为空
	if (p->phead == NULL)
	{
		return EOF;
	}
	else
	{
		//返回栈顶元素
		return p->phead->val;
	}

}

4、判断栈是否为空(empty)
思路：

• 当链表头指针为空时，栈即为空；
• （或者）当栈的size==0时，栈为空；

总之判断方法很多，大家可以尽情发挥。

具体实现：

//判断栈是否为空
int empty(pStack p)
{
	//判断链表是否为空
	if (p->phead == NULL)
	{
		return 0;
	}
	else
	{
		return 1;
	}
}

5、返回栈中元素个数(size)
思路：

• 当链表为空时，返回0；
• 当链表不为空时，返回栈的size；

这个实现方法很多，大家可以尽情发挥。

具体实现：

//返回栈中元素个数
int size(pStack p)
{
	//判断链表是否为空
	if (p->phead == NULL)
	{
		return 0;
	}
	else
	{
		return p->size;
	}
}

至此栈的基本操作我们已经全部实现了，接下来我们在main()函数中测试一下：

int main()
{
	//栈的操作，链表实现栈stack
	
	Stack s;//定义一个栈
	int i;//入栈的值
	char panduan;//用来判断是否弹栈

	//使用memset初始化结点（栈）
	memset(&s, 0, sizeof(Stack));//栈的初始化,初始化为0

	while (scanf("%d", &i) != EOF)
	{
		//入栈
		push(&s, i);		
	}
	//打印栈元素
	printf("栈里面元素为：\n");
	print_stack(&s);

	//打印栈顶元素
	printf("栈顶元素为：%d\n", top(&s));

	//判断栈是否为空
	if (empty(&s))
	{
		printf("栈不为空！\n");
	}
	else
	{
		printf("栈为空！\n");
	}
	//栈中元素个数
	printf("栈中元素个数为：%d\n", size(&s));

	printf("---------------------------------\n");

	while (printf("是否弹栈？y/n："),scanf("%c", &panduan) != NULL)
	{
		if (panduan == 'y')
		{
			//出栈
			pop(&s);

			//打印栈元素
			print_stack(&s);


			//打印栈顶元素
			printf("栈顶元素为：%d\n", top(&s));

			//判断栈是否为空
			if (empty(&s))
			{
				printf("栈不为空！\n");
			}
			else
			{
				printf("栈为空！\n");
			}
			//栈中元素个数
			printf("栈中元素个数为：%d\n", size(&s));

			printf("---------------------------------\n");
		}
		else if(panduan == 'n')
		{
			break;
		}
	
	}

	return 0;
}

实现结果：

栈的操作到目前来说已经实现，希望对大家学习有所帮助，加油！

tips：瞄准天上的星星，或许你永远也射不到，但却比你瞄准树梢射得高远。

通讯录管理系统是链表的常用应用，也是我们必须要掌握的一个用链表实现的小项目制作。
下面来看代码

#include <stdio.h>
#include <stdlib.h>
typedef struct  //定义每个人员信息结构体 
{
	char num[5]; //编号 
	char name[9];//姓名 
	char sex[3]; //性别 
	char phone[13]; //电话 
	char addr[31]; //地址 
 }DataType;
 typedef struct node  //定义链表类型 
 {
 	DataType data; //数据域 
 	struct node *next; //指针域 
  }ListNode;
typedef ListNode *LinkList;
void CreateList(LinkList &L,int m)//通讯录链表的建立 
{ int i;
  LinkList s,r;
  L=(LinkList)malloc(sizeof(ListNode));
  L->next=NULL;
  r=L; //尾节点 

  for(i=0;i<m;i++)
  {  s=(LinkList)malloc(sizeof(ListNode)); //新建的节点 
     printf("输入第%d位编号:",i+1);
     scanf("%s",&s->data.num);
     printf("\n输入姓名:");
     scanf("%s",&s->data.name);
     printf("\n输入性别:");
     scanf("%s",&s->data.sex);
     printf("\n输入电话:");
     scanf("%s",&s->data.phone);
     printf("\n输入地址:");
     scanf("%s",&s->data.addr);
     s->next=NULL;  
	 r->next=s; //插入尾节点之后 
	 r=s;
	 
  }	

}
int ListLength(LinkList L) //求通讯录链表的长度 
{ LinkList p;
  int length=0;
  p=L->next;
  while(p)
  { length++;
    p=p->next;
  }
  return length;	
 } 
int ListInsert(LinkList &L,int i,DataType d)  //通讯录链表的插入 
{ LinkList p,s;
  int length;
  length=ListLength(L); 
  p=L->next;
  int j=1;
  if(!p||i>length+1) //如果是空表或者查询位置不符合要求 
  return 0;
  while(p&&j<i-1)  //使p指向要添加位置的前一个元素 
  {
  	p=p->next;
  	j++;
  }
  s=(LinkList)malloc(sizeof(LinkList));
  s->data=d;
  s->next=p->next;
  p->next=s;
  return 1; 
}
int ListDelete(LinkList &L,int i)
{ LinkList p,q;//p为要删除的前一个节点，q为要删除的节点 
  p=L;
  int j=0;
  int length;
  length=ListLength(L); 
  if(!p||i>length) //如果是空表或者查询位置不符合要求 
  return 0;
  while(p&&j<i-1) //使p指向要删除位置的前一个元素 
  { p=p->next;
  	j++;
  }
  q=p->next; //q指向后一个元素  
  printf("\n被删除的人员信息为：\n");
  printf("\n编号:%s  姓名:%s  性别:%s  电话:%s 地址:%s",q->data.num,q->data.name,q->data.sex,q->data.phone,q->data.addr);
  p->next=q->next; 
  return 1; 	
 } 
int GetElem(LinkList L,int i,DataType &d) //查询第i个成员信息 
{ LinkList p;
  p=L->next;
  int j=1;
  int length;
  length=ListLength(L); 
  if(!p||i>length) //如果是空表或者查询位置不符合要求 
  return 0;
  while(j<i)
  {p=p->next;
   j++;
  }
  d=p->data;
  return 1;
	
}

void print(LinkList L) //打印通讯录人员信息 
{ LinkList p;
  p=L->next;
  while(p)
  {
  	printf("\n编号:%s  姓名:%s  性别:%s  电话:%s 地址:%s",p->data.num,p->data.name,p->data.sex,p->data.phone,p->data.addr);
  	p=p->next;
  }
	
 } 
 void menu()
 { printf("--------------------------------------------1.通讯录链表的建立----------------------------------------------------------");
   printf("\n--------------------------------------------2.通讯者节点的插入----------------------------------------------------------");
   printf("\n--------------------------------------------3.通讯者节点的查询----------------------------------------------------------");
   printf("\n--------------------------------------------4.通讯者节点的删除----------------------------------------------------------");
   printf("\n--------------------------------------------5.通讯录链表的输出----------------------------------------------------------");
   printf("\n--------------------------------------------0.退出管理系统--------------------------------------------------------------");
 }
 int main()
 {
 	LinkList L;
 	DataType d,d1;
 	int m,location,length,choose;
 	menu();
 	p:
 	printf("\n请输入你的选项：");
 	scanf("%d",&choose);
 	switch(choose)
 	{ case 1:printf("请输入通讯录人数:");scanf("%d",&m);CreateList(L,m);goto p;
 	  case 2:printf("\n输入要插入的位置：");scanf("%d",&location);printf("输入插入人员的编号："); scanf("%s",&d.num);printf("\n输入姓名:"); scanf("%s",&d.name); printf("\n输入性别:");scanf("%s",&d.sex);printf("\n输入电话:");scanf("%s",&d.phone);printf("\n输入地址:");scanf("%s",&d.addr);ListInsert(L,location,d);goto p;
	  case 3:printf("\n请输入查询位置");scanf("%d",&location);GetElem(L,location,d); printf("查询到的人员信息为：\n");printf("\n编号:%s  姓名:%s  性别:%s  电话:%s 地址:%s",d.num,d.name,d.sex,d.phone,d.addr);goto p;
	  case 4:printf("\n输入要删除的位置：");scanf("%d",&location);ListDelete(L,location);goto p; 
	  case 5:print(L);goto p;
	  case 0:printf("系统已退出。");exit(0);
	  default:printf("输入错误,请重新输入");goto p;
	 }
 	return 0;
 }

下面是运行结果图