Compartilhamento de tecnologia

Pilha de estrutura de dados

2024-07-12

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Título

Olá! Olá amigos! Vamos aprender a estrutura de dados da pilha hoje!

1. Pilha

1.1 Conceitos básicos de pilha

Pilha: Uma lista linear especial que permite apenas operações de inserção e exclusão em um final fixo. A extremidade que entra nas operações de inserção e exclusão de dados é chamada de topo da pilha e a outra extremidade é chamada de parte inferior da pilha.Os elementos de dados na pilha estão em conformidade comLIFO Princípio (último a entrar, primeiro a sair). Podemos imaginar isso como comer espetadas de carneiro,Coloque primeiroOs pedaços de carneiro são prensadosfundo，o últimoOs pedaços de carneiro estão emNo topode.

Empurrando a pilha: A operação de inserção da pilha é chamada push/push/push.Inserir dados do topo da pilha。

Pop: A operação de exclusão da pilha é chamada de popping.Os dados de saída também estão no topo da pilha。

1.2 Implementação de pilha

A pilha geralmente pode ser implementada usando um array para implementar a pilha ou usando uma lista vinculada para implementar a pilha, o que for melhor, relativamente falando, usar.estrutura de matrizImplementar a pilha é mais simples e eficiente.

Porque na implementação da interface de adição, exclusão, modificação e consulta da tabela de sequência anterior (tabela de sequência de estrutura de dados) É muito conveniente para nós usarmos a estrutura do array para inserir e excluir do final, portanto, na implementação da pilha, definimos o final do array como o topo da pilha e a cabeça como a parte inferior de a pilha.

2. Implementação da interface de pilha

A pilha, assim como a lista de sequências, pode ser projetada como uma pilha estática de comprimento fixo ou como uma pilha de crescimento dinâmico.Como a pilha de comprimento fixo tem grandes limitações e não é prática na prática, implementamos principalmente suportePilha de crescimento dinâmico。

Da mesma forma que a implementação anterior da interface de lista de sequências/lista vinculada, primeiro criamos um arquivo de cabeçalho "Stack.h" e dois arquivos de origem "Stack.c" e "Test.c".

Pilha.hDefinição de pilha, referência de arquivo de cabeçalho e declaração de função de interface
Pilha.cImplementação de funções de interface
Teste.cTeste cada função

Vamos mostrar primeiro o código completo de "Stack.h", não esqueça de citar "Stack.h" nos 2 arquivos fonte

  1. #pragma once				//防止头文件被二次引用
  2. #include<stdio.h>
  3. #include<stdlib.h>
  4. #include<assert.h>
  5.  
  6. typedef int ElemType;		//如果要修改存储的数据类型可直接在此修改
  7. typedef struct Stack {
  8. 	ElemType* arr;			//动态数组
  9. 	int top;				//栈顶
  10. 	int capacity;			//容量
  11. }Stack;
  12.  
  13.  
  14. void StackInit(Stack* ps);//初始化栈
  15.  
  16. void StackPush(Stack* ps, ElemType x);//入栈
  17.  
  18. void StackPop(Stack* ps);//出栈
  19.  
  20. ElemType StackTop(Stack* ps);//获取栈顶元素
  21.  
  22. int StackSize(Stack* ps);//获取栈中有效元素的个数
  23.  
  24. int StackEmpty(Stack* ps);//检测栈是否为空,如果为空返回非零结果,如果不为空返回0
  25.  
  26. void StackDestroy(Stack* ps);//销毁栈

Dentre eles, o significado de “topo” é determinado pelo valor inicial, que será explicado detalhadamente a seguir. Em seguida, começamos a implementar a interface.

(1) Pilha de inicialização
  1. //初始化栈
  2. void StackInit(Stack* ps) {
  3. 	assert(ps);		//断言,防止传入空指针
  4. 	ps->arr = NULL; //初始化数组,置空
  5. 	ps->capacity = 0;//top指向栈顶元素的下一个位置
  6. 	ps->top = 0;	 //初始化容量
  7. }

Para facilitar a compreensão, entendemos aproximadamente o topo da estrutura como o subscrito da matriz.Se inicializarmos top com 0 ao inicializar a pilha, não há dados na pilha e top aponta para a próxima posição dos dados do topo da pilha.

Se inicializarmos top com -1, top apontará para a localização dos dados superiores na pilha. É melhor inicializá-lo com 0 aqui porque é conveniente adicionar e excluir elementos.

(2) Empurre para dentro da pilha
  1. //入栈
  2. void StackPush(Stack* ps, ElemType x) {
  3. 	//扩容
  4. 	if (ps->capacity == ps->top) //容量已满,需要扩容
  5. 	{
  6. 		//如果容量为0,则扩容到4; 否则扩大2倍
  7. 		int newCapacity = ps->capacity == 0 ? 4 : 2 * (ps->capacity);
  8. 		//创建一个临时指针变量来存储新空间地址,防止开辟失败
  9. 		ElemType* temp = realloc(ps->arr, newCapacity * sizeof(ElemType));
  10. 		if (temp == NULL) //防止开辟失败出现空指针
  11. 		{
  12. 			perror("realloc fail!n");
  13. 			exit(1);
  14. 		}
  15. 		ps->arr = temp;	  //将临时指针变量中存放的新空间地址赋给arr
  16. 		ps->capacity = newCapacity;//空间容量更新
  17. 	}
  18. 	ps->arr[ps->top] = x;//将数据存放进栈顶元素的下一个位置
  19. 	ps->top++;//位置更新
  20. }

Como há uma diferença entre a pilha e a tabela de sequência, não podemos percorrer e imprimir diretamente. Portanto, se quisermos imprimir os elementos da pilha, precisamos usar a função StackEmpty e a função StackPop, que serão discutidas mais adiante. .

(3) Sair
  1. //出栈
  2. void StackPop(Stack* ps) {
  3. 	assert(ps);			//断言,防止传入空指针
  4. 	assert(ps->top);	//断言,防止栈中没有元素,却还在执行删除
  5. 	ps->top--;			//top指针往前挪动一位(相当于这个位置被覆盖了)
  6. }
(4) Obtenha o elemento superior da pilha
  1. //获取栈顶元素
  2. ElemType StackTop(Stack* ps) {
  3. 	assert(ps);				//断言,防止传入空指针
  4. 	assert(ps->top);		//断言,防止栈为空
  5. 	return ps->arr[ps->top - 1];//top-1为栈顶元素的位置,返回其值
  6. }
(5) Obtenha o número de elementos válidos na pilha
  1. //获取栈中有效元素的个数
  2. int StackSize(Stack* ps) {
  3. 	assert(ps);				//断言,防止传入空指针
  4. 	return ps->top;			//top即为有效元素的个数
  5. }
(6) Verifique se a pilha está vazia
  1. //检测栈是否为空,如果为空返回非零结果,如果不为空返回0
  2. int StackEmpty(Stack* ps) {
  3. 	assert(ps);				//断言,防止传入空指针
  4. 	return ps->top == 0;	//如果top==0, 说明栈为空
  5. }

É por isso que StackEmpty na afirmação anterior precisa ser adicionadooperador de negação lógicaA razão é que se a pilha estiver vazia, StackEmpty retornará verdadeiro e a negação de falso pode provar que existem elementos na pilha.

(7) Destrua a pilha
  1. //销毁栈
  2. void StackDestroy(Stack* ps) {
  3. 	assert(ps);				//断言,防止传入空指针
  4. 	if (ps->arr)			//如果动态数组有效
  5. 	{
  6. 		free(ps->arr);		//释放arr
  7. 		ps->arr = NULL;		//将arr置空
  8. 	}
  9. 	ps->capacity = 0;		//数组的容量为0
  10. 	ps->top = 0;			//数组的栈顶top为0
  11.  
  12. }

Depois que todas as interfaces forem concluídas, vamos testar o código em Test.c:

Vamos testar mais um pouco:

Não há problema nenhum. Parabéns por concluir a implementação da interface da pilha. A seguir está o código completo do arquivo "Stack.c":

  1. #include"Stack.h"
  2.  
  3. //初始化栈
  4. void StackInit(Stack* ps) {
  5. 	assert(ps);		//断言,防止传入空指针
  6. 	ps->arr = NULL; //初始化数组,置空
  7. 	ps->capacity = 0;//top指向栈顶元素的下一个位置
  8. 	ps->top = 0;	 //初始化容量
  9. }
  10.  
  11. //入栈
  12. void StackPush(Stack* ps, ElemType x) {
  13. 	//扩容
  14. 	if (ps->capacity == ps->top) //容量已满,需要扩容
  15. 	{
  16. 		//如果容量为0,则扩容到4; 否则扩大2倍
  17. 		int newCapacity = ps->capacity == 0 ? 4 : 2 * (ps->capacity);
  18. 		//创建一个临时指针变量来存储新空间地址,防止开辟失败
  19. 		ElemType* temp = realloc(ps->arr, newCapacity * sizeof(ElemType));
  20. 		if (temp == NULL) //防止开辟失败出现空指针
  21. 		{
  22. 			perror("realloc fail!n");
  23. 			exit(1);
  24. 		}
  25. 		ps->arr = temp;	  //将临时指针变量中存放的新空间地址赋给arr
  26. 		ps->capacity = newCapacity;//空间容量更新
  27. 	}
  28. 	ps->arr[ps->top] = x;//将数据存放进栈顶元素的下一个位置
  29. 	ps->top++;//位置更新
  30. }
  31.  
  32. //出栈
  33. void StackPop(Stack* ps) {
  34. 	assert(ps);			//断言,防止传入空指针
  35. 	assert(ps->top);	//断言,防止栈中没有元素,却还在执行删除
  36. 	ps->top--;			//top指针往前挪动一位(相当于这个位置被覆盖了)
  37. }
  38.  
  39. //获取栈顶元素
  40. ElemType StackTop(Stack* ps) {
  41. 	assert(ps);				//断言,防止传入空指针
  42. 	assert(ps->top);		//断言,防止栈为空
  43. 	return ps->arr[ps->top - 1];//top-1为栈顶元素的位置,返回其值
  44. }
  45.  
  46. //获取栈中有效元素的个数
  47. int StackSize(Stack* ps) {
  48. 	assert(ps);				//断言,防止传入空指针
  49. 	return ps->top;			//top即为有效元素的个数
  50. }
  51.  
  52. //检测栈是否为空,如果为空返回非零结果,如果不为空返回0
  53. int StackEmpty(Stack* ps) {
  54. 	assert(ps);				//断言,防止传入空指针
  55. 	return ps->top == 0;	//如果top==0, 说明栈为空
  56. }
  57.  
  58. //销毁栈
  59. void StackDestroy(Stack* ps) {
  60. 	assert(ps);				//断言,防止传入空指针
  61. 	if (ps->arr)			//如果动态数组有效
  62. 	{
  63. 		free(ps->arr);		//释放arr
  64. 		ps->arr = NULL;		//将arr置空
  65. 	}
  66. 	ps->capacity = 0;		//数组的容量为0
  67. 	ps->top = 0;			//数组的栈顶top为0
  68.  
  69. }

Seção de exercícios

1. Qual das seguintes afirmações sobre pilhas está correta ( )

A. A pilha é uma estrutura de dados do tipo "primeiro a entrar, primeiro a sair"

B. A pilha pode ser implementada usando uma lista vinculada ou uma lista de sequência

C. A pilha só pode inserir dados na parte inferior da pilha

D. A pilha não pode excluir dados

resposta correta: B

Erro A: A pilha é uma estrutura de dados do tipo último a entrar, primeiro a sair e a fila é o primeiro a entrar, primeiro a sair.

B está correto: tanto as listas de sequências quanto as listas vinculadas podem ser usadas para implementar pilhas, mas as listas de sequências são geralmente usadas porque a pilha é considerada uma versão castrada da lista de sequências. Somente as operações de inserção e exclusão da cauda da tabela de sequências são. usado, e a inserção final da tabela de sequência é usada. A exclusão final e a exclusão final não requerem elementos móveis e são muito eficientes, portanto, geralmente são implementadas usando tabelas sequenciais.

Erro C: a pilha só pode realizar operações de inserção e exclusão de entrada no topo da pilha

Erro D: A pilha tem operações push e pop. Pop serve para excluir um elemento da pilha.

2. A sequência push de uma pilha é ABCDE, e a sequência pop impossível é ()

A.ABCDE

Bacharel em Educação Física e Ciências Contábeis (BED)

C.DCEBA

D.ECDBA

resposta correta: E

Se E sair primeiro, significa que ABCDE foi todo colocado na pilha. Depois que E for retirado da pilha, o elemento superior da pilha será D. Se for retirado novamente, deverá ser D, não C. .

Portanto, D deve ser selecionado

3. Em comparação com a pilha sequencial, as vantagens óbvias da pilha em cadeia são ( )

A. A operação de inserção é mais conveniente

B. A operação de exclusão é mais conveniente

C. Nenhuma expansão é necessária ao inserir na pilha

resposta correta: C

Erro A. Se for uma pilha vinculada, geralmente requer operações de inserção ou exclusão de cabeçalho, enquanto uma pilha sequencial geralmente executa operações de inserção e exclusão de cauda. A operação de uma lista vinculada é mais complicada do que uma tabela sequencial, portanto é. mais simples usar uma estrutura sequencial para implementar uma pilha.

B está errado, consulte A para saber o motivo.

C está correto. Quando a pilha é implementada em uma estrutura de cadeia, cada push na pilha é equivalente a inserir um nó no topo da lista vinculada.

4. Qual das seguintes afirmações sobre o uso de pilhas para implementar filas está incorreta ( )

A. Usar a simulação de pilha para implementar uma fila pode usar duas pilhas, uma pilha simula a entrada na fila e uma pilha simula a saída da fila.

B. Cada vez que você desenfileira, você precisa importar todos os elementos de uma pilha para outra pilha e, em seguida, retirá-la.

C. Ao entrar na fila, basta armazenar os elementos diretamente na pilha que simula a entrada na fila.

D. A complexidade de tempo da operação da fila é O(1)

resposta correta: B

Na opção B, uma pilha simula a entrada na fila e uma pilha simula a retirada da fila. Ao desenfileirar, o elemento superior da pilha de retirada da fila simulada é exibido diretamente. Quando a pilha está vazia, todos os elementos da pilha da fila simulada são importados. . Os elementos precisam ser importados sempre, então é um erro.

Na opção A, as características das pilhas e das filas são opostas. Uma pilha não pode implementar uma fila.

Na opção C, uma pilha simula a entrada na fila e uma pilha simula a saída da fila. Ao entrar na fila, os elementos são armazenados diretamente na pilha que simula a entrada na fila.

Na opção D, enfileirar significa colocar elementos na pilha, então a complexidade de tempo é O(1)

Final

Hoje aprendemos sobre a estrutura de dados de uma pilha. Não é muito mais simples que uma lista vinculada Hahahahaha, espero que este artigo seja útil para meus amigos!!!

implorarCurta, favorite e siga!!!

obrigado a todos!

Perfil pessoal

Ele se dedica à pesquisa de tecnologia há mais de 30 anos e é proficiente em diversas linguagens como java, linux, javascript, php, css, etc. estação de documentação do desenvolvedor para compartilhar alguns problemas no desenvolvimento de tecnologia para referência futura.

minhas informações de contato

Correspondência