前言：在前面的文章中，我們講解了順序表，單鏈表，雙向鏈表。而我們今天要分享的棧則是基于之前的數(shù)據(jù)結構上搭建的，但是相較于順序表和鏈表來說，棧的實現(xiàn)就非常簡單了。
目錄
一.棧(Stack)的概念
二.棧的數(shù)據(jù)結構
三.棧的實現(xiàn)
判斷棧已滿
判斷棧非空
入棧push
出棧pop
查看棧頂元素
完整代碼
Java版本
c語言版
一.棧(Stack)的概念
棧是一種先進后出（LIFO）的數(shù)據(jù)結構，在其中元素的的添加（稱為“入棧”）和刪除（稱為“出?！保﹥H在棧的頂部進行。因此，最后一個插入到棧中的元素是第一個從棧中刪除的元素。
它通常有兩個主要操作：
- push：在棧的頂部插入一個元素。
- pop：從棧的頂部移除一個元素。
棧的push入棧圖解：
棧的pop出棧圖解 ：
我們可以看見對于棧的操作，我們都是在棧頂上操作的，先進來的元素會被后面的元素覆蓋，而最后一個進來的元素也就是棧頂，因此我們稱為先進后出（LIFO）
像傳統(tǒng)的狙擊步槍的彈夾就屬于是一種棧的結構?
二.棧的數(shù)據(jù)結構
對于棧的實現(xiàn)，我們通常使用數(shù)組，當然也可以使用鏈表，不過相對而言數(shù)組的實現(xiàn)是更容易的。
而對于一個棧的數(shù)據(jù)結構，他首先得有存放元素的位置，我們這里選擇用數(shù)組來存放，其次還得有棧內(nèi)元素個數(shù)的記錄：
public class MyStack {
public int[] elem;
public int usedSize;
}
三.棧的實現(xiàn)
對于一個棧，他應該有以下這些功能：
- 入棧
- 出棧
- 判斷棧是否為空
- 判斷棧已滿
- 查看棧頂元素
判斷棧已滿
當已經(jīng)使用的數(shù)組的大小等于數(shù)組本身的大小的時候，棧就相當于滿了
public boolean isFull() {
return usedSize == elem.length;
}判斷棧非空
當數(shù)組內(nèi)一個元素都沒有，也就是已經(jīng)使用的數(shù)組大小為0的時候，棧就是空的
public boolean isEmpety() {
return usedSize == 0;
}入棧push
當我們要將元素放入棧內(nèi)的時候，先進行判斷，只有在棧內(nèi)還有剩余空間的情況下，我們才會進行入棧操作，如果沒有剩余空間，我們就進行擴容
public void push(int val) {
if (isFull()) {
//擴容
elem = Arrays.copyOf(elem, elem.length * 2);
}
elem[usedSize++] = val;
}出棧pop
出棧前要先進行判斷，如果棧內(nèi)一個元素都沒有，那自然是不能進行出棧操作的，我們就拋出一個自定義異常然后拋出；對于正常的出棧操作，我們拿出棧頂?shù)脑?，然后讓記錄?shù)組的個數(shù)減一
public int pop() {
if (isEmpety()) {
//棧為空，無法出棧
throw new EmptyStackException("棧為空，無法彈出");
}
int popNumber = elem[usedSize-1];
usedSize--;
return popNumber;
}查看棧頂元素
和出棧不一樣的是，查看棧頂元素只是將元素拿出來展示，并沒有實際上刪除這個元素
public int peek() {
if (isEmpety()) {
//棧為空，無法出棧
throw new EmptyStackException("棧為空，無法彈出");
}
return elem[usedSize - 1];
}完整代碼
棧的整體實現(xiàn)相較于順序表和鏈表是非常簡單的，這里附上完整代碼文章來源：http://www.zghlxwxcb.cn/news/detail-754320.html
Java版本
import java.util.Arrays;
public class MyStack {
public int[] elem;
public int usedSize;
public static int DEFULT_SIZE = 10;
public MyStack() {
this.elem = new int[DEFULT_SIZE];
}
public void push(int val) {
if (isFull()) {
//擴容
elem = Arrays.copyOf(elem, elem.length * 2);
}
elem[usedSize++] = val;
}
public int pop() {
if (isEmpety()) {
//棧為空，無法出棧
throw new EmptyStackException("棧為空，無法彈出");
}
int popNumber = elem[usedSize-1];
usedSize--;
return popNumber;
}
public int peek() {
if (isEmpety()) {
//棧為空，無法出棧
throw new EmptyStackException("棧為空，無法彈出");
}
return elem[usedSize - 1];
}
public boolean isFull() {
return usedSize == elem.length;
}
public boolean isEmpety() {
return usedSize == 0;
}
}
c語言版
#include <stdio.h>
#include <stdlib.h>
#define STACK_SIZE 10
// 定義棧結構體
typedef struct {
int data[STACK_SIZE]; // 存放數(shù)據(jù)的數(shù)組
int top; // 棧頂指針
} Stack;
// 初始化棧
void init_stack(Stack *s) {
s->top = -1; // 棧頂初始化為-1
}
// 判斷棧是否為空
int is_empty(Stack *s) {
return s->top == -1;
}
// 判斷棧是否已滿
int is_full(Stack *s) {
return s->top == STACK_SIZE-1;
}
// 入棧
void push(Stack *s, int value) {
if (is_full(s)) {
printf("Stack overflow\n");
exit(1);
}
s->data[++s->top] = value; // 棧頂指針先加1，再將元素入棧
}
// 出棧
int pop(Stack *s) {
if (is_empty(s)) {
printf("Stack underflow\n");
exit(1);
}
return s->data[s->top--]; // 先將元素出棧，再將棧頂指針減1
}
// 獲取棧頂元素
int peek(Stack *s) {
if (is_empty(s)) {
printf("Stack underflow\n");
exit(1);
}
return s->data[s->top];
}
?
?本次的分享就到此為止了，希望我的分享能給您帶來幫助，也歡迎大家三連支持，你們的點贊就是博主更新最大的動力！
如有不同意見，歡迎評論區(qū)積極討論交流，讓我們一起學習進步！
有相關問題也可以私信博主，評論區(qū)和私信都會認真查看的，我們下次再見文章來源地址http://www.zghlxwxcb.cn/news/detail-754320.html
到了這里，關于數(shù)據(jù)結構：棧(Stack)的各種操作（入棧，出棧，判斷棧非空，判斷棧已滿，附源碼）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
