Condivisione della tecnologia

Stack della struttura dei dati

2024-07-12

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

Titolo

Ciao! Ciao amici! Impariamo insieme la struttura dei dati dello stack oggi!

1. Impilare

1.1 Concetti base di stack

Stack: uno speciale elenco lineare che consente solo operazioni di inserimento e cancellazione ad un'estremità fissa. L'estremità che entra nelle operazioni di inserimento ed eliminazione dei dati è chiamata la parte superiore dello stack, mentre l'altra estremità è chiamata la parte inferiore dello stack.Gli elementi dati nello stack sono conformiLIFO (Last In First Out). Possiamo immaginarlo come mangiare spiedini di montone,Mettilo primaI pezzi di montone vengono pressatimetter il fondo a，l'ultimoCi sono i pezzi di montoneSulla cimaDi.

Push dello stack: l'operazione di inserimento dello stack è chiamata push/push/push.Inserisci i dati dalla cima dello stack。

Pop: L'operazione di cancellazione dello stack è detta popping.Anche i dati in uscita si trovano in cima allo stack。

1.2 Implementazione dello stack

Lo stack può generalmente essere implementato utilizzando un array per implementare lo stack o utilizzando un elenco collegato per implementare lo stack, a seconda di quale sia il migliore, relativamente parlandostruttura dell'arrayL'implementazione dello stack è più semplice ed efficiente.

Perché nell'implementazione dell'interfaccia di aggiunta, cancellazione, modifica e query della tabella di sequenza precedente (tabella di sequenza della struttura dei dati) Per noi è molto comodo utilizzare la struttura dell'array per inserire ed eliminare dalla fine, quindi nell'implementazione dello stack definiamo la fine dell'array come la parte superiore dello stack e la testa come la parte inferiore dello la pila.

2. Implementazione dell'interfaccia stack

Lo stack, come l'elenco di sequenze, può essere progettato come uno stack statico a lunghezza fissa o come uno stack a crescita dinamica.Poiché lo stack a lunghezza fissa presenta grandi limitazioni e non è pratico nella pratica, implementiamo principalmente il supportoStack in crescita dinamica。

Come per la precedente implementazione dell'interfaccia elenco sequenze/elenco collegato, creiamo prima un file di intestazione "Stack.h" e due file sorgente "Stack.c" e "Test.c".

Pila.hDefinizione dello stack, riferimento al file di intestazione e dichiarazione della funzione dell'interfaccia
Pila.cImplementazione delle funzioni di interfaccia
Prova.cTestare ogni funzione

Mostriamo prima il codice completo di "Stack.h", non dimenticare di citare "Stack.h" nei 2 file sorgente

  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);//销毁栈

Tra questi, il significato di "top" è determinato dal valore iniziale, che verrà spiegato in dettaglio di seguito. Successivamente iniziamo a implementare l'interfaccia.

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

Per facilità di comprensione, nella struttura intendiamo approssimativamente top come il pedice dell'array.Se inizializziamo top a 0 durante l'inizializzazione dello stack, non ci sono dati nello stack e top punta alla posizione successiva dei dati top nello stack.

Se inizializziamo top a -1, top punterà alla posizione dei dati principali nello stack. È meglio per noi inizializzarlo su 0 qui perché è conveniente aggiungere elementi ed eliminare elementi.

(2) Spingere nella pila
  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. }

Poiché esiste una differenza tra lo stack e la tabella di sequenza, non possiamo attraversare e stampare direttamente. Pertanto, se vogliamo stampare gli elementi nello stack, dobbiamo utilizzare la funzione StackEmpty e la funzione StackPop, di cui parleremo più avanti. .

(3) Esci
  1. //出栈
  2. void StackPop(Stack* ps) {
  3. 	assert(ps);			//断言,防止传入空指针
  4. 	assert(ps->top);	//断言,防止栈中没有元素,却还在执行删除
  5. 	ps->top--;			//top指针往前挪动一位(相当于这个位置被覆盖了)
  6. }
(4) Prendi l'elemento in cima alla pila
  1. //获取栈顶元素
  2. ElemType StackTop(Stack* ps) {
  3. 	assert(ps);				//断言,防止传入空指针
  4. 	assert(ps->top);		//断言,防止栈为空
  5. 	return ps->arr[ps->top - 1];//top-1为栈顶元素的位置,返回其值
  6. }
(5) Ottieni il numero di elementi validi nello stack
  1. //获取栈中有效元素的个数
  2. int StackSize(Stack* ps) {
  3. 	assert(ps);				//断言,防止传入空指针
  4. 	return ps->top;			//top即为有效元素的个数
  5. }
(6) Controllare se lo stack è vuoto
  1. //检测栈是否为空,如果为空返回非零结果,如果不为空返回0
  2. int StackEmpty(Stack* ps) {
  3. 	assert(ps);				//断言,防止传入空指针
  4. 	return ps->top == 0;	//如果top==0, 说明栈为空
  5. }

Questo è il motivo per cui è necessario aggiungere StackEmpty nell'affermazione precedenteoperatore logico di negazioneIl motivo è che se lo stack è vuoto, StackEmpty restituisce true e la negazione di false può dimostrare che ci sono elementi nello stack.

(7) Distruggi la pila
  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. }

Dopo aver completato tutte le interfacce, testiamo il codice in Test.c:

Proviamolo ancora un po':

Nessun problema. Congratulazioni per aver completato l'implementazione dell'interfaccia stack. Quello che segue è il codice completo del file "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. }

Sezione esercizi

1. Quale delle seguenti affermazioni sugli stack è corretta ( )

R. Lo stack è una struttura dati "first in first out".

B. Lo stack può essere implementato utilizzando un elenco collegato o un elenco di sequenze

C. Lo stack può inserire dati solo nella parte inferiore dello stack

D. Lo stack non può eliminare i dati

risposta corretta: B

Errore A: lo stack è una struttura dati last-in-first-out e la coda è first-in, first-out.

B è corretto: sia gli elenchi di sequenze che gli elenchi collegati possono essere utilizzati per implementare gli stack, ma gli elenchi di sequenze vengono generalmente utilizzati perché lo stack è considerato una versione castrata dell'elenco di sequenze. Solo le operazioni di inserimento ed eliminazione della coda della tabella di sequenza lo sono utilizzato e viene utilizzato l'inserimento della coda della tabella di sequenza. L'eliminazione della coda e l'eliminazione della coda non richiedono lo spostamento di elementi e sono molto efficienti, quindi vengono generalmente implementate utilizzando tabelle sequenziali.

Errore C: lo stack può eseguire solo operazioni di inserimento ed eliminazione di input nella parte superiore dello stack

Errore D: lo stack ha operazioni push e pop. Pop consiste nell'eliminare un elemento dallo stack.

2. La sequenza di push di uno stack è ABCDE e la sequenza di pop impossibile è ( )

A.ABCDE

B. EDCBA

C.DCEBA

D.ECDBA

risposta corretta: D

Se E esce per primo, significa che ABCDE è stato tutto messo in pila. Dopo che E è stato tolto dallo stack, l'elemento in cima alla pila è D. Se viene tolto di nuovo, dovrebbe essere D, non C. .

Pertanto, è opportuno selezionare D

3. Rispetto allo stack sequenziale, gli ovvi vantaggi dello stack a catena sono ( )

R. L'operazione di inserimento è più conveniente

B. L'operazione di cancellazione è più conveniente

C. Non è necessaria alcuna espansione quando si inserisce nella pila

risposta corretta: C

Errore A. Se si tratta di uno stack concatenato richiede in genere operazioni di inserimento o cancellazione di testa, mentre uno stack sequenziale generalmente esegue operazioni di inserimento e cancellazione di coda. Il funzionamento di una lista concatenata è più complicato di una tabella sequenziale, quindi lo è più semplice utilizzare una struttura sequenziale per implementare uno stack.

B ha torto, fare riferimento ad A per il motivo.

C è corretto Quando lo stack è implementato in una struttura a catena, ogni inserimento nello stack equivale a inserire un nodo in testa alla lista concatenata.

4. Quale delle seguenti affermazioni sull'utilizzo degli stack per implementare le code è errata ( )

R. Utilizzando la simulazione dello stack per implementare una coda è possibile utilizzare due stack, uno stack simula l'ingresso nella coda e uno stack simula l'uscita dalla coda.

B. Ogni volta che si rimuove dalla coda, è necessario importare tutti gli elementi di uno stack in un altro stack e quindi estrarli.

C. Quando si entra in coda è sufficiente memorizzare gli elementi direttamente nello stack che simula l'ingresso in coda.

D. La complessità temporale dell'operazione in coda è O(1)

risposta corretta: B

Nell'opzione B, uno stack simula l'ingresso nella coda e un altro stack simula l'eliminazione dalla coda, l'elemento superiore dello stack di rimozione dalla coda simulato viene visualizzato direttamente. Quando lo stack è vuoto, tutti gli elementi nello stack della coda simulata vengono importati Gli elementi devono essere importati ogni volta, quindi è un errore

Nell'opzione A, le caratteristiche degli stack e delle code sono opposte. Uno stack non può implementare una coda.

Nell'opzione C, uno stack simula l'ingresso nella coda e l'altro stack simula l'uscita dalla coda. Quando si entra nella coda, gli elementi vengono memorizzati direttamente nello stack che simula l'ingresso nella coda.

Nell'opzione D, accodare significa mettere elementi in pila, quindi la complessità temporale è O(1)

Fine

Oggi abbiamo imparato a conoscere la struttura dei dati di uno stack Non è molto più semplice di una lista concatenata Hahahahaha, spero che questo articolo sia utile ai miei amici!!!

elemosinareMetti mi piace, aggiungi ai preferiti e segui!!!

grazie a tutti! ! !

Profilo personale

Si dedica alla ricerca tecnologica da più di 30 anni ed è esperto in vari linguaggi come Java, Linux, Javascript, php, css, ecc. Ha dato numerosi contributi nel campo dell'open source stazione di documentazione per gli sviluppatori per condividere alcuni problemi nello sviluppo della tecnologia per riferimento futuro

le mie informazioni di contatto

Posta