Berbagi teknologi

Tumpukan struktur data

2024-07-12

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

Judul

Hai! Halo teman-teman! Mari kita pelajari struktur data tumpukan bersama-sama hari ini! Apakah Anda siap untuk memulai?

1. Tumpukan

1.1 Konsep dasar tumpukan

Tumpukan: Daftar linier khusus yang hanya mengizinkan operasi penyisipan dan penghapusan pada ujung yang tetap. Ujung yang memasuki operasi penyisipan dan penghapusan data disebut bagian atas tumpukan, dan ujung lainnya disebut bagian bawah tumpukan.Elemen data dalam tumpukan mematuhiLIFO Prinsip (Terakhir Masuk Pertama Keluar). Kita bisa membayangkannya seperti makan kebab daging kambing,Pakai duluPotongan daging kambing ditekandasar，yang terakhirPotongan daging kambing sudah masukDi atasdari.

Mendorong tumpukan: Operasi penyisipan tumpukan disebut push/push/push.Masukkan data dari atas tumpukan。

Pop: Operasi penghapusan tumpukan disebut popping.Data keluar juga ada di tumpukan teratas。

1.2 Implementasi tumpukan

Tumpukan umumnya dapat diimplementasikan dengan menggunakan array untuk mengimplementasikan tumpukan atau menggunakan daftar tertaut untuk mengimplementasikan tumpukan, mana yang lebih baik, secara relatif, gunakanstruktur susunanMenerapkan tumpukan lebih sederhana dan efisien.

Karena dalam implementasi penambahan, penghapusan, modifikasi dan query antarmuka tabel urutan sebelumnya (tabel urutan struktur data) Sangat mudah bagi kita untuk menggunakan struktur array untuk menyisipkan dan menghapus dari akhir, jadi dalam implementasi tumpukan, kita mendefinisikan akhir array sebagai bagian atas tumpukan dan kepala sebagai bagian bawah dari tumpukan.

2. Implementasi antarmuka tumpukan

Tumpukan, seperti daftar urutan, dapat dirancang sebagai tumpukan statis dengan panjang tetap atau tumpukan yang berkembang secara dinamis.Karena tumpukan dengan panjang tetap memiliki keterbatasan besar dan tidak praktis dalam praktiknya, kami terutama menerapkan dukunganTumpukan yang tumbuh secara dinamis。

Sama seperti implementasi antarmuka daftar urutan/daftar tertaut sebelumnya, pertama-tama kita membuat file header "Stack.h" dan dua file sumber "Stack.c" dan "Test.c".

Tumpukan.hDefinisi tumpukan, referensi file header, dan deklarasi fungsi antarmuka
Tumpukan.cImplementasi fungsi antarmuka
Tes.cUji setiap fungsi

Mari kita tampilkan kode lengkap "Stack.h" terlebih dahulu, jangan lupa untuk mengutip "Stack.h" di 2 file sumber

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

Diantaranya, arti “atas” ditentukan oleh nilai awal yang akan dijelaskan secara rinci di bawah ini. Selanjutnya kita mulai mengimplementasikan antarmuka.

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

Untuk memudahkan pemahaman, kira-kira kita memahami bagian atas struktur sebagai subskrip dari array.Jika kita menginisialisasi top ke 0 saat menginisialisasi tumpukan, tidak ada data di tumpukan, dan top menunjuk ke posisi berikutnya dari data teratas di tumpukan.

Jika kita menginisialisasi top ke -1, top akan menunjuk ke lokasi data teratas di stack. Lebih baik kita menginisialisasinya ke 0 di sini karena akan lebih mudah untuk menambahkan elemen dan menghapus elemen.

(2) Dorong ke dalam tumpukan
  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. }

Karena ada perbedaan antara stack dan tabel sequence, kita tidak bisa langsung traverse dan print. Oleh karena itu, jika kita ingin mencetak elemen yang ada di stack, kita perlu menggunakan fungsi StackEmpty dan fungsi StackPop yang akan dibahas nanti. .

(3) Keluar
  1. //出栈
  2. void StackPop(Stack* ps) {
  3. 	assert(ps);			//断言,防止传入空指针
  4. 	assert(ps->top);	//断言,防止栈中没有元素,却还在执行删除
  5. 	ps->top--;			//top指针往前挪动一位(相当于这个位置被覆盖了)
  6. }
(4) Dapatkan elemen teratas tumpukan
  1. //获取栈顶元素
  2. ElemType StackTop(Stack* ps) {
  3. 	assert(ps);				//断言,防止传入空指针
  4. 	assert(ps->top);		//断言,防止栈为空
  5. 	return ps->arr[ps->top - 1];//top-1为栈顶元素的位置,返回其值
  6. }
(5) Dapatkan jumlah elemen valid dalam tumpukan
  1. //获取栈中有效元素的个数
  2. int StackSize(Stack* ps) {
  3. 	assert(ps);				//断言,防止传入空指针
  4. 	return ps->top;			//top即为有效元素的个数
  5. }
(6) Periksa apakah tumpukannya kosong
  1. //检测栈是否为空,如果为空返回非零结果,如果不为空返回0
  2. int StackEmpty(Stack* ps) {
  3. 	assert(ps);				//断言,防止传入空指针
  4. 	return ps->top == 0;	//如果top==0, 说明栈为空
  5. }

Inilah mengapa StackEmpty pada pernyataan sebelumnya perlu ditambahkanoperator negasi logisAlasannya adalah jika tumpukan kosong, StackEmpty mengembalikan nilai true, dan negasi dari false dapat membuktikan bahwa ada elemen di dalam tumpukan.

(7) Hancurkan tumpukan
  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. }

Setelah semua antarmuka selesai, mari kita uji kode di Test.c:

Mari kita uji lagi:

Tidak ada masalah sama sekali. Selamat telah menyelesaikan implementasi antarmuka stack! Berikut kode lengkap 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. }

Bagian latihan

1. Pernyataan berikut tentang tumpukan yang benar ( )

A. Tumpukan adalah struktur data "masuk pertama keluar pertama".

B. Tumpukan dapat diimplementasikan menggunakan daftar tertaut atau daftar urutan

C. Tumpukan hanya dapat memasukkan data di bagian bawah tumpukan

D. Tumpukan tidak dapat menghapus data

jawaban yang benar: B

Kesalahan A: Tumpukan adalah struktur data yang masuk terakhir keluar pertama, dan antriannya masuk pertama, keluar pertama.

B benar: Daftar urutan dan daftar tertaut dapat digunakan untuk mengimplementasikan tumpukan, tetapi daftar urutan umumnya digunakan karena tumpukan dianggap sebagai versi daftar urutan yang dikebiri. Hanya operasi penyisipan ekor dan penghapusan ekor dari tabel urutan digunakan, dan penyisipan ekor dari tabel urutan digunakan. Penghapusan ekor dan penghapusan ekor tidak memerlukan elemen bergerak dan sangat efisien, sehingga umumnya diimplementasikan menggunakan tabel sekuensial.

Kesalahan C: Tumpukan hanya dapat melakukan operasi penyisipan dan penghapusan input di bagian atas tumpukan

Kesalahan D: Tumpukan memiliki operasi push dan pop. Pop adalah menghapus elemen dari tumpukan.

2. Urutan push tumpukan adalah ABCDE, dan urutan pop yang mustahil adalah ( )

A.ABCDE

B.EDCBA

C.DCEBA

D.ECDBA

jawaban yang benar: D

Jika E keluar lebih dulu, berarti ABCDE sudah terdorong semua ke tumpukan. Setelah E dikeluarkan dari tumpukan, elemen teratas tumpukan adalah D. Jika dikeluarkan lagi, seharusnya D, bukan C. .

Oleh karena itu, D harus dipilih

3. Dibandingkan dengan tumpukan sekuensial, keuntungan nyata dari tumpukan rantai adalah ( )

A. Operasi penyisipan lebih nyaman

B. Operasi penghapusan lebih nyaman

C. Tidak diperlukan pemuaian saat mendorong ke dalam tumpukan

jawaban yang benar: C

Kesalahan A. Jika ini adalah tumpukan tertaut, biasanya memerlukan operasi penyisipan kepala atau penghapusan kepala, sedangkan tumpukan berurutan umumnya melakukan operasi penyisipan ekor dan penghapusan ekor. Pengoperasian daftar tertaut lebih rumit daripada tabel berurutan, jadi memang begitu lebih mudah untuk menggunakan struktur berurutan untuk mengimplementasikan tumpukan.

B salah, silakan rujuk A untuk alasannya.

C benar. Ketika tumpukan diimplementasikan dalam struktur rantai, setiap dorongan ke dalam tumpukan sama dengan memasukkan node ke dalam kepala daftar tertaut.

4. Pernyataan berikut tentang penggunaan tumpukan untuk mengimplementasikan antrian yang salah ( )

A. Menggunakan simulasi tumpukan untuk mengimplementasikan antrian dapat menggunakan dua tumpukan, satu tumpukan mensimulasikan memasuki antrian, dan satu tumpukan mensimulasikan meninggalkan antrian.

B. Setiap kali Anda melakukan dequeue, Anda perlu mengimpor semua elemen dalam satu tumpukan ke tumpukan lain dan kemudian mengeluarkannya.

C. Saat memasuki antrian, cukup simpan elemen langsung di tumpukan yang mensimulasikan memasuki antrian.

D. Kompleksitas waktu operasi antrian adalah O(1)

jawaban yang benar: B

Dalam opsi B, satu tumpukan mensimulasikan memasuki antrian, dan satu tumpukan mensimulasikan dequeuing. Saat melakukan dequeuing, elemen teratas dari tumpukan dequeuing yang disimulasikan langsung muncul. Ketika tumpukan kosong, semua elemen dalam tumpukan antrian yang disimulasikan diimpor No .Elemen perlu diimpor setiap saat, jadi ini kesalahan

Pada opsi A, karakteristik tumpukan dan antrian adalah kebalikannya.

Pada opsi C, satu tumpukan disimulasikan memasuki antrian, dan satu tumpukan disimulasikan keluar dari antrian. Saat memasuki antrian, elemen langsung disimpan di tumpukan yang disimulasikan memasuki antrian.

Pada pilihan D, antrian berarti meletakkan elemen pada tumpukan, sehingga kompleksitas waktunya adalah O(1)

Akhir

Hari ini kita belajar tentang struktur data stack. Bukankah lebih sederhana dari linked list? Hahahahaha, semoga artikel ini bermanfaat bagi teman-teman!!!

mengemisSukai, favoritkan, dan ikuti!!!

Terima kasih semua! ! !

Profil pribadi

Ia telah mengabdikan dirinya untuk meneliti teknologi selama lebih dari 30 tahun, dan mahir dalam berbagai bahasa seperti java, linux, javascript, php, css, dll. "Saya telah memberikan banyak kontribusi di bidang dokumentasi pengembang stasiun sumber terbuka untuk berbagi beberapa masalah dalam pengembangan teknologi untuk referensi di masa mendatang. Semua orang memeriksanya

informasi kontak saya

Surat